A 2D rigidity circuit is a minimal graph G=(V,E) supporting a non-trivial stress in any generic placement of its vertices in the Euclidean plane. All 2D rigidity circuits can be constructed from K4 graphs using combinatorial resultant (CR) operations. A combinatorial resultant tree (CR-tree) is a rooted binary tree capturing the structure of such a construction. The CR operation has a specific algebraic interpretation, where an essentially unique circuit polynomial is associated to each circuit graph. Performing Sylvester resultant operations on these polynomials is in one-to-one correspondence with CR operations on circuit graphs. This mixed combinatorial/algebraic approach led recently to an effective algorithm for computing circuit polynomials. Its complexity analysis remains an open problem, but it is known to be influenced by the depth and shape of CR-trees in ways that have only partially been investigated. In this paper, we present an effective algorithm for enumerating all the CR-trees of a given circuit with n vertices. Our algorithm has been fully implemented in Mathematica and allows for computational experimentation with various optimality criteria in the resulting, potentially exponentially large collections of CR-trees.

Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid associated to the Cayley-Menger ideal for $n$ points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from $K_4$ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.

Pebble game rigidity analysis is a combinatorial method, implemented in our free web server KinariWeb, for extracting protein rigidity and flexibility information without performing costly molecular dynamics simulations. Due to the idiosynchrasies of the data in the Protein Data Bank (PDB), Kinari succeeds only on a fraction of the available files. Motivated by large scale applications, aiming at processing almost all the PDB files, we have recently developed a faster and more robust version, the phased pebble game algorithm. It is specifically designed to take advantage of the sequential structure of biopolymers. However, the structural data available in the Protein Data Bank for proteins solved with X-ray crystallography is very rarely complete: missing residues induce gaps in the atom sequence, leading to incomplete rigidity analysis results. In this paper, we describe the pre-processing component of the new version Kinari-2, which fixes such gaps for the purpose of producing a valid input for the phased pebble game algorithm described in [19].

Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell--Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

We formulate and prove a periodic analog of Maxwell's theorem relating stressed planar frameworks and their liftings to polyhedral surfaces with spherical topology. We use our lifting theorem to prove rigidity-theoretic properties for planar periodic pseudo-triangulations, generalizing their finite counterparts. These properties are then applied to questions originating in mathematical crystallography and materials science, concerning planar periodic auxetic structures and ultrarigid periodic frameworks.

BACKGROUND: Protein rigidity analysis is an efficient computational method for extracting flexibility information from static, X-ray crystallography protein data. Atoms and bonds are modeled as a mechanical structure and analyzed with a fast graph-based algorithm, producing a decomposition of the flexible molecule into interconnected rigid clusters. The result depends critically on noncovalent atomic interactions, primarily on how hydrogen bonds and hydrophobic interactions are computed and modeled. Ongoing research points to the stringent need for benchmarking rigidity analysis software systems, towards the goal of increasing their accuracy and validating their results, either against each other and against biologically relevant (functional) parameters. We propose two new methods for modeling hydrogen bonds and hydrophobic interactions that more accurately reflect a mechanical model, without being computationally more intensive. We evaluate them using a novel scoring method, based on the B-cubed score from the information retrieval literature, which measures how well two cluster decompositions match. RESULTS: To evaluate the modeling accuracy of KINARI, our pebble-game rigidity analysis system, we use a benchmark data set of 20 proteins, each with multiple distinct conformations deposited in the Protein Data Bank. Cluster decompositions for them were previously determined with the RigidFinder method from Gerstein's lab and validated against experimental data. When KINARI's default tuning parameters are used, an improvement of the B-cubed score over a crude baseline is observed in 30% of this data. With our new modeling options, improvements were observed in over 70% of the proteins in this data set. We investigate the sensitivity of the cluster decomposition score with case studies on pyruvate phosphate dikinase and calmodulin. CONCLUSION: To substantially improve the accuracy of protein rigidity analysis systems, thorough benchmarking must be performed on all current systems and future extensions. We have measured the gain in performance by comparing different modeling methods for noncovalent interactions. We showed that new criteria for modeling hydrogen bonds and hydrophobic interactions can significantly improve the results. The two new methods proposed here have been implemented and made publicly available in the current version of KINARI (v1.3), together with the benchmarking tools, which can be downloaded from our software's website, http://kinari.cs.umass.edu.

We initiate in silico rigidity-theoretical studies of biological assemblies and small crystals for protein structures. The goal is to determine if, and how, the interactions among neighboring cells and subchains affect the flexibility of a molecule in its crystallized state. We use experimental X-ray crystallography data from the Protein Data Bank (PDB). The analysis relies on an effcient graph-based algorithm. Computational experiments were performed using new protein rigidity analysis tools available in the new release of our KINARI-Web server http://kinari.cs.umass.edu . We provide two types of results: on biological assemblies and on crystals. We found that when only isolated subchains are considered, structural and functional information may be missed. Indeed, the rigidity of biological assemblies is sometimes dependent on the count and placement of hydrogen bonds and other interactions among the individual subchains of the biological unit. Similarly, the rigidity of small crystals may be affected by the interactions between atoms belonging to different unit cells. We have analyzed a dataset of approximately 300 proteins, from which we generated 982 crystals (some of which are biological assemblies). We identified two types of behaviors. (a) Some crystals and/or biological assemblies will aggregate into rigid bodies that span multiple unit cells/asymmetric units. Some of them create substantially larger rigid cluster in the crystal/biological assembly form, while in other cases, the aggregation has a smaller effect just at the interface between the units. (b) In other cases, the rigidity properties of the asymmetric units are retained, because the rigid bodies did not combine. We also identified two interesting cases where rigidity analysis may be correlated with the functional behavior of the protein. This type of information, identified here for the first time, depends critically on the ability to create crystals and biological assemblies, and would not have been observed only from the asymmetric unit. For the Ribonuclease A protein (PDB file 5RSA), which is functionally active in the crystallized form, we found that the individual protein and its crystal form retain the flexibility parameters between the two states. In contrast, a derivative of Ribonuclease A (PDB file 9RSA), has no functional activity, and the protein in both the asymmetric and crystalline forms, is very rigid. For the vaccinia virus D13 scaffolding protein (PDB file 3SAQ), which has two biological assemblies, we observed a striking asymmetry in the rigidity cluster decomposition of one of them, which seems implausible, given its symmetry. Upon careful investigation, we tracked the cause to a placement decision by the Reduce software concerning the hydrogen atoms, thus affecting the distribution of certain hydrogen bonds. The surprising result is that the presence or lack of a very few, but critical, hydrogen bonds, can drastically affect the rigid cluster decomposition of the biological assembly. The rigidity analysis of a single asymmetric unit may not accurately reflect the protein's behavior in the tightly packed crystal environment. Using our KINARI software, we demonstrated that additional functional and rigidity information can be gained by analyzing a protein's biological assembly and/or crystal structure. However, performing a larger scale study would be computationally expensive (due to the size of the molecules involved). Overcoming this limitation will require novel mathematical and computational extensions to our software.

Flexibility studies of macromolecules modeled as mechanical frameworks rely on computationally expensive, yet numerically imprecise simulations. Much faster approaches for degree-of-freedom counting and rigid component calculations are known for finite structures characterized by theorems of Maxwell-Laman type, but such results are exceedingly rare and difficult to obtain. The situation is even more complex for infinite, periodic structures such as those appearing in the study of crystalline materials. Here, an adequate rigidity theoretical formulation has been proposed only recently, opening the way to a combinatorial treatment.

We present a Java implementation of Lang's Universal Molecule algorithm, alongside with a visualization of its interconnected structures: the input metric tree and compatible convex polygon, whose 2D crease pattern and 3D uniaxial base are computed by the algorithm. The Java applet, the video, as well as further references and accompanying materials are available on our web site http://linkage.cs.umass.edu/origamiLang. We also include a recent example, found with the help of this implementation, of a Universal Molecule crease pattern which, as a flat-faced origami, is completely rigid; in particular, its corresponding uniaxial base cannot be reached through continuous folding without bending of the paper.

Given a 3D polygonal chain with fixed edge lengths and fixed angles between consecutive edges (shortly, a revolute-jointed chain or robot arm), the Extremal Reaches Problem asks for those configurations where the distance between the endpoints attains a global maximum or minimum value. In this paper, we solve it with a polynomial time algorithm.

We present the first exact, combinatorial, polynomial time algorithm for computing the description of the workspace boundary for the class of revolute jointed robot arms arising from polygonal orthogonal chains in 3D. Copyright 2011 ACM.

The problem of computing the maximum reach configurations of a 3D revolute-jointed manipulator is a long-standing open problem in robotics. In this paper we present an optimal algorithmic solution for orthogonal polygonal chains. This appears as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available, with no guarantee of obtaining the global maximum. In fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. We present elementary and efficient (mostly linear) algorithms for four fundamental problems: (1) finding the maximum reach value, (2) finding a maximum reach configuration (or enumerating all of them), (3) folding a given chain to a given maximum position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. The algorithms rely on our recent theoretical results characterizing combinatorially the maximum of panel-and-hinge chains. They allow us to reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar carpenter's rule problem.

A single-vertex origami is a piece of paper with straight-line rays called creases emanating from a fold vertex placed in its interior or on its boundary. The Single-Vertex Origami Problem asks whether it is always possible to reconfigure the creased paper from any configuration compatible with the metric, to a flat position, in such a way that the paper is not torn, stretched and, for rigid origami, not bent anywhere except along the given creases.

How many pair-wise distances must be prescribed between an unknown set of points, and how should they be distributed, to determine only a discrete set of possible solutions? These questions, and related generalizations, are central in a variety of applications. Combinatorial rigidity shows that in two-dimensions one can get the answer, generically, via an efficiently testable sparse graph property.

A well studied geometric problem, with applications ranging from molecular structure determination to sensor networks, asks for the reconstruction of a set P of n unknown points from a finite set of pairwise distances (up to Euclidean isometries). We are concerned here with a related problem: which sets of distances are minimal with the property that they allow for the reconstruction of P, up to a finite set of possibilities? In the planar case, the answer is known generically via the landmark Maxwell-Laman Theorem from Rigidity Theory, and it leads to a combinatorial answer: the underlying structure of such a generic minimal collection of distances is a minimally rigid (or Laman) graph, for which very efficient combinatorial decision algorithms exist. For non-generic cases the situation appears to be dramatically different, with the best known algorithms relying on exponential-time Gröbner base methods, and some specific instances known to be NP-hard. Understanding what makes a point set generic emerges as an intriguing geometric question with practical algorithmic consequences.

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

(MATH) Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study first the number of distinct planar embeddings of rigid graphs with n vertices. We show that, modulo planar rigid motions, this number is at most $2n-4\choose n-2 \approx 4n. We also exhibit several families which realize lower bounds of the order of 2n, 2.21n and 2.88n.(MATH) For the upper bound we use techniques from complex algebraic geometry, based on the (projective) Cayley-Menger variety CM 2,n(C)\subset P_n\choose 2-1(C)$ over the complex numbers C. In this context, point configurations are represented by coordinates given by squared distances between all pairs of points. Sectioning the variety with 2n-4 hyperplanes yields at most deg(CM 2,n) zero-dimensional components, and one finds this degree to be D 2,n =\frac122n-4\choose n-2$. The lower bounds are related to inductive constructions of minimally rigid graphs via Henneberg sequences.(MATH) The same approach works in higher dimensions. In particular we show that it leads to an upper bound of 2 D^3,n= \frac2^n-3n-2n-6\choosen-3$ for the number of spatial embeddings with generic edge lengths of the $1$-skeleton of a simplicial polyhedron, up to rigid motions.

We propose a combinatorial approach to plan noncolliding motions for a polygonal bar-and-joint framework. Our approach yields very efficient deterministic algorithms for a category of robot arm motion planning problems with many degrees of freedom, where the known general roadmap techniques would give exponential complexity. It is based on a novel class of one-degree-of-freedom mechanisms induced by pseudo triangulations of planar point sets, for which we provide several equivalent characterization and exhibit rich combinatorial and rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter's rule problem: convexify a simple bar-and-joint planar polygonal linkage using only non self-intersecting planar motions. A step in the convexification motion consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At that point, a local alteration restores the pseudo triangulation. The motion continues for O(n/sup 2/) steps until all the points are in convex position.

We present advances on the open problem of characterizing vertex-edge visibility graphs (ve-graphs), reduced by results of O'Rourke and Streinu to a stretchability question for pseudo-polygons. We introduce star-like pseudo-polygons as a special subclass containing all the known instances of non-stretchable pseudo-polygons. We give a complete combinatorial characterization and a linear-time decision procedure for star-like pseudo-polygon stretchability and star-like ve-graph recognition. To the best of our knowledge, this is the first problem in computational geometry for which a combinatorial characterization was found by first isolating the oriented matroid substructure and then separately solving the stretchability question. It is also the first class (as opposed to isolated examples) of oriented matroids for which an efficient stretchability decision procedure based on combinatorial criteria is given. The difficulty of the general stretchability problem implied by Mnev's Universality Theorem makes this a result of independent interest in the theory of oriented matroids.

We extend the notion of polygon visibility graphs to pseud~polygons defined on genemlized conjigumtions Of points.We consider both vertex-to-vertex, as well as vertex-to-edge visibility in pseudo-polygons.We study the characterization and recognition problems for vertex-edge pseudo-visibility graphs.Given a bipart.itegraph G satisfying three simple properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertexedge pseudo-visibility graph is G. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial-time algorithm for the decision problem. It also implies that the decision problem for vertex visibilitygraphs of pseud~polygons is in NP(as opposed to the same problem with straight-edge visibility, which is only known to be in PSPACE). 1 Introduction Characterizing visibility graphs has remained an elusive problem [0'R93].Ghosh [Gho88, Gho97] pro posed a set of necessary conditions as a starting point. Everett ~ve90] proved their insufficiency and proposed new conditions. She also placed the recognition problem in PSPACE by reducing it to the existential theory of the reals. Abello and Kumar [AK95]expanded the set of conditions and first related the problem with oriented matroid theory.Their conditions, plus realizability (stretchability) of a certain "

We solve two open problems posed by Goodman and Pollack[GP84] about sets of signed circular permutations (clusters of stars) arising from generalized configurations of points: recognition and efficient reconstruction (drawing).As a biproduct we get an (7(n2 ) space data structure constructible in 0(n2 ) time, representing the order type of a (generalized) configuration of points and from which the orientation of each tride can be found in constant time.a moblem Dosed in '~HNJ.