Geometric rigidity
In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system (GCS) has finitely many formula_1-dimensional solutions, or frameworks, in some metric space. A framework of a GCS is rigid in formula_1-dimensions, for a given formula_1 if it is an isolated solution of the GCS, factoring out the set of trivial motions, or isometric group, of the metric space, e.g. translations and rotations in Euclidean space. In other words, a rigid framework formula_4 of a GCS has no nearby framework of the GCS that is reachable via a non-trivial continuous motion  of formula_4 that preserves the constraints of the GCS. Structural rigidity is another theory of rigidity that concerns generic frameworks, i.e., frameworks whose rigidity properties are representative of all frameworks with the same constraint graph. Results in geometric rigidity apply to all frameworks; in particular, to non-generic frameworks. Geometric rigidity was first explored by Euler, who conjectured that all polyhedra in formula_6-dimensions are rigid. Much work has gone into proving the conjecture, leading to many interesting results discussed below. However, a counterexample was eventually found. There are also some generic rigidity results with no combinatorial components, so they  are related to both geometric and structural rigidity. Definitions. The definitions below, which can be found in, are with respect to bar-joint frameworks in formula_1-dimensional Euclidean space, and will be generalized for other frameworks and metric spaces as needed. Consider a linkage formula_8, i.e. a constraint graph formula_9 with distance constraints formula_10 assigned to its edges, and the configuration space formula_11 consisting of frameworks formula_4 of formula_8. The frameworks in formula_11 consist of maps formula_15 that satisfy formula_16 for all edges formula_17 of formula_18. In other words, formula_19 is a placement of the vertices of formula_18 as points  in formula_1-dimensions that satisfy all distance constraints formula_10. The configuration space formula_11 is an algebraic set. Continuous and trivial motions. A continuous motion is a continuous path in formula_11 that describes the physical motion between two frameworks of formula_8 that preserves all constraints. A trivial motion is a continuous motion resulting from the formula_26 Euclidean isometries, i.e. translations and rotations. In general, any metric space has a set of trivial motions coming from the isometric group of the space. Local rigidity. A framework of a GCS is locally rigid, or just rigid, if all its continuous motions are trivial . Testing for local rigidity is co-NP hard. Rigidity map. The rigidity map formula_27 takes a framework formula_4 and outputs the squared-distances formula_29 between all pairs of points that are connected by an edge. Rigidity matrix. The Jacobian, or derivative, of the rigidity map yields a system of linear equations of the form formula_30 for all edges formula_17 of formula_18. The rigidity matrix formula_33 is an formula_34 matrix that encodes the information in these equations. Each edge of formula_18 corresponds to a row of formula_33 and each vertex corresponds to formula_1 columns of formula_33. The row corresponding to the  edge formula_17 is defined as follows. formula_40 Infinitesimal motion. An infinitesimal motion is an assignment formula_41 of velocities to the vertices of a framework formula_4 such that formula_43. Hence, the kernel of the rigidity matrix is the space of infinitesimal motions. A trivial infinitesimal motion is defined analogously to a trivial continuous motion. Stress. A stress is an assignment formula_44 to the edges of a framework formula_4. A stress is proper if its entries are nonnegative and is a self stress if it satisfies formula_46. A stress satisfying this equation is also called a resolvable stress, equilibrium stress, prestress, or  sometimes just a stress. Stress Matrix. For a stress formula_47 applied to the edges of a framework formula_4 with the constraint graph formula_9, define the formula_50 stress matrix formula_51 as formula_52 It is easily verified that for any two formula_53 and any stress formula_47, formula_55 The rigidity matrix as a linear transformation. The information in this section can be found in. The rigidity matrix can be viewed as a linear transformation from formula_56 to formula_57. The domain of this transformation is the set of formula_58 column vectors, called velocity or displacements vectors, denoted by formula_59, and the image is the  set of formula_60 edge distortion vectors, denoted by formula_61. The entries of the vector formula_59 are velocities assigned to the vertices of a framework formula_4, and the equation formula_64 describes how the edges are compressed or stretched as a result of these velocities. The dual linear transformation leads to a different physical interpretation. The codomain of the linear transformation is the set of formula_60 column vectors, or stresses, denoted by formula_47, that apply a stress formula_67 to each edge formula_17 of a framework formula_4. The stress formula_67 applies forces to the vertices of formula_17 that are equal in magnitude but  opposite in direction, depending on whether formula_17 is being compressed or stretched by formula_67. Consider the equation formula_74 where formula_75 is a formula_58 vector. The terms on the left corresponding to the formula_1 columns of a vertex formula_78 in formula_79 yield the entry in formula_75 that is the net force formula_81 applied to formula_78 by the stresses on edges incident to formula_78. Hence, the domain of the dual linear transformation is the set of stresses on edges and the image is the set of net forces on vertices. A net force formula_75 can be viewed as being able to counteract , or resolve, the force formula_85, so the image of the dual linear transformation is really the set of resolvable forces. The relationship between these dual linear transformations is described by the work done by a velocity vector formula_59 under a net force formula_75: formula_88 where formula_47 is a stress and formula_61 is an edge distortion. In terms of the stress matrix, this equation above becomes formula_91. Types of rigidity. This section covers the various types of rigidity and how they are related.  For more information, see. Infinitesimal rigidity. Infinitesimal rigidity is the strongest form of rigidity that restricts a framework  from admitting even non-trivial infinitesimal motions. It is also called first-order rigidity because of its relation to the rigidity matrix. More precisely, consider the linear equations formula_92 resulting from the equation formula_43. These equations state that the projections of the velocities formula_94 and formula_95 onto the edge formula_17 cancel out. Each of the following are statements is sufficient for a formula_1-dimensional framework to be infinitesimally rigid in formula_1-dimensions: In general, any type of framework is infinitesimally rigid in formula_1-dimensions if space of its infinitesimal motions is the space of trivial infinitesimal motions of the metric  space. The following theorem by Asimow and Roth relates infinitesimal rigidity and rigidity. Theorem. If a framework is infinitesimally rigid, then it is rigid. The converse of this theorem is not true in general; however, it is true for generic rigid frameworks (with respect to infinitesimal rigidity), see combinatorial characterizations of generically rigid graphs. Static rigidity. A formula_1-dimensional framework formula_4 is statically rigid in formula_1-dimensions if every force vector formula_75 on the vertices of formula_4 that is orthogonal to the trivial motions can be resolved by the net force of some proper stress formula_47; or written mathematically, for  every such force vector formula_75 there exists a proper stress formula_47 such that formula_112 Equivalently, the rank of formula_79 must be formula_102. Static rigidity is equivalent to infinitesimal rigidity. Second-order rigidity. Second-order rigidity is weaker than infinitesimal and static rigidity. The second derivative of the rigidity map consists of equations of the form formula_115 The vector formula_116 assigns an acceleration to each vertex of a framework formula_4. These equations can be written in terms of matrices: formula_118, where formula_119 is defined similarly to the rigidity matrix. Each of the following statements are sufficient for a formula_1-dimensional framework  to be second-order rigid in formula_1-dimensions: The third statement shows that for each such formula_59, formula_130 is not in the column span of formula_79, i.e., it is not an edge distortion resulting from formula_59. This follows from the Fredholm alternative: since the column span of formula_79 is orthogonal to the kernel of formula_134, i.e., the set of equilibrium stresses, either formula_118 for some acceleration formula_116 or there is an equilibrium stress formula_47 satisfying the third condition. The third condition can be written in terms of the stress matrix: formula_138. Solving for formula_47 is a non-linear problem in  formula_59 with no known efficient algorithm. Prestress stability. Prestress stability is weaker than infinitesimal and static rigidity but stronger than second-order rigidity. Consider the third sufficient condition for second-order rigidity. A formula_1-dimensional framework formula_4 is prestress stable if there exists an equilibrium stress formula_47 such that for all non-trivial velocities formula_59, formula_138. Prestress stability can be verified via semidefinite programming techniques. Global rigidity. A formula_1-dimensional framework formula_4 of a linkage formula_8 is globally rigid in formula_1-dimensions if all frameworks in the configuration space formula_11 are equivalent up to trivial motions, i.e., factoring out the  trivial motions, there is only one framework of formula_8. Theorem. Global rigidity is a generic property of graphs. Minimal rigidity. A formula_1-dimensional framework formula_4 is minimally rigid in formula_1-dimensions if formula_4 is rigid and removing any edge from formula_4 results in a framework that is not rigid. Redundant rigidity. There are two types of redundant rigidity: vertex-redundant and edge-redundant rigidity. A formula_1-dimensional framework formula_4 is edge-redundantly rigid in formula_1-dimensions if formula_4 is rigid and removing any edge from formula_4 results in another rigid framework. Vertex-redundant rigidity is defined analogously. Rigidity for various  types of frameworks. Polyhedra. This section concerns the rigidity of polyhedra in formula_6-dimensions, see polyhedral systems for a definition of this type of GCS. A polyhedron is rigid if its underlying bar-joint framework is rigid. One of the earliest results for rigidity was a conjecture by Euler in 1766. Conjecture. A closed spatial figure allows no changes, as long as it is not ripped apart. Much work has gone into proving this conjecture, which has now been proved false by counterexample. The first major result is by Cauchy in 1813 and is known as Cauchy's theorem. Cauchy 's Theorem. If there is an isometry between the surfaces of two strictly convex polyhedra which is an isometry on each of the faces, then the two polyhedra are congruent. There were minor errors with Cauchy's proof. The first complete proof was given in, and a slightly generalized result was given in. The following corollary of Cauchy's theorem relates this result to rigidity. Corollary. The 2-skeleton of a strictly convex polyhedral framework in formula_6-dimensions is rigid. In other words, if we treat the convex polyhedra as a set of rigid plates, i.e., as a variant of  a body-bar-hinge framework, then the framework is rigid. The next result, by Bricard in 1897, shows that the strict convexity condition can be dropped for formula_164-skeletons of the octahedron. Theorem. The formula_164-skeleton of any polyhedral framework of the octahedron in formula_6-dimensions is rigid. However, there exists a framework of the octahedron whose formula_167-skeleton is not rigid in formula_6-dimensions. The proof of the latter part of this theorem shows that these flexible frameworks exist due to self-intersections. Progress on Eurler's conjecture did not pick up again until the late 19th century. The  next theorem and corollary concern triangulated polyhedra. Theorem. If vertices are inserted in the edges of a strictly convex polyhedron and the faces are triangulated, then the formula_167-skeleton of the resulting polyhedron is infinitesimally rigid. Corollary. If a convex polyhedron in formula_6-dimensions has the property that the collection of faces containing a given vertex do not all lie in the same plane, then the formula_164-skeleton of that polyhedron is infinitesimally rigid. The following result shows that the triangulation condition in the above theorem is necessary. Theorem. The formula_167-skeleton of a strictly convex polyhedron embedded in formula_6 -dimensions which has at least one non-triangluar face is not rigid. The following conjecture extends Cauchy's result to more general polyhedra. Conjecture. Two combinatorially equivalent polyhedra with equal corresponding dihedral angles are isogonal. This conjecture has been proved for some special cases. The next result applies in the generic setting, i.e., to almost all polyhedra with the same combinatorial structure, see structural rigidity. Theorem. Every closed simply connected polyhedral surface with a formula_6-dimensional framework is generically rigid. This theorem demonstrates that Euler's conjecture is true for almost all polyhedra. However, a non-generic polyhedron was found  that is not rigid in formula_6-dimensions, disproving the conjecture. This polyhedra is topologically a sphere, which shows that the generic result above is optimal. Details on how to construct this polyhedra can be found in. An interesting property of this polyhedra is that its volume remains constant along any continuous motion path, leading to the following conjecture. Bellows Conjecture. Every orientable closed polyhedral surface flexes with constant volume. This conjecture was first proven for spherical polyhedra and then in general. Tensegrities. This section concerns the rigidity of tensegrities, see tensegrity systems for a definition of this type of GCS . Definitions. The definitions below can be found in. Infinitesimal motion. An infinitesimal motion of a tensegrity framework formula_4 is a velocity vector formula_41 such that for each edge formula_17 of the framework, Second-order motion. A second-order motion of a tensegrity framework formula_4 is a solution formula_122 to the following constraints: Global rigidity.’ A formula_1-dimensional tensegrity framework formula_4 of a tensegrity GCS is globally rigid in formula_1-dimensions if every other formula_1-dimensional framework formula_199 of the same GCS that is dominated by formula_4 can be obtained via a trivial motion of formula_4. Universal rigidity. A formula_1-dimensional  tensegrity framework formula_4 of a tensegrity GCS is universally rigid if it is globally rigid in any dimension. Dimensional rigidity. A formula_1-dimensional tensegrity framework formula_4 of a tensegrity GCS is dimensionally rigid in formula_1-dimensions if any other formula_207-dimensional tensegrity framework formula_199, for any formula_207 satisfying the constraints of the GCS, has an affine span of dimension at most formula_1. Super stable. A formula_1-dimensional tensegrity framework formula_4 is super stable in formula_1-dimensions if is rigid in formula_1-dimensions as a bar-joint framework and has a proper equilibrium stress formula_47 such that the stress matrix formula_51  is positive semidefinite and has rank formula_217. Rigidity theorems. Generic results. Infinitesimal rigidity is not a generic property of tensegrities, see structural rigidity. In other words, not all generic tensegrities with the same constraint graph have the same infinitesimal rigidity properties. Hence, some work has gone into identifying specific classes of graphs for which infinitesimal rigidity is a generic property of tensegrities. Graphs satisfying this condition are called strongly rigid. Testing a graph for strong rigidity is NP-hard, even for formula_167-dimension. The following result equates generic redundant rigidity of graphs to infinitesimally rigid tensegrities. Theorem. A graph formula_18  has an infinitesimally rigid tensegrity framework in formula_1-dimensions, for some partition of the edges of formula_18 into bars, cables, and struts if and only if formula_18 is generically edge-redundantly rigid in formula_1-dimensions. The first result demonstrates when rigidity and infinitesimal rigidity of tensegrities are equivalent. Theorem. Let formula_4 be a formula_1-dimensional tensegrity framework where: the vertices of formula_18 are realized as a strictly convex polygon; the bars form a Hamilton cycle on the boundary of this polygon; and there are no struts. Then, formula_4 is rigid in formula_1-dimensions if and only if it is infinitesimally  rigid in formula_1-dimensions. The following is a necessary condition for rigidity. Theorem. Let formula_4 be a formula_1-dimensional tensegrity framework with at least one cable or strut. If formula_4 is rigid in formula_1-dimensions, then it has a non-zero proper equilibrium stress. Rigidity of tensegrities can also be written in terms of bar-joint frameworks as follows. Theorem. Let formula_4 be a formula_1-dimensional tensegrity framework with at least one cable or strut. Then formula_4 is infinitesimally rigid in formula_1-dimensions if it is rigid in formula_1-dimensions as a bar-joint framework and has a strict proper  stress. The following is a sufficient condition for second-order rigidity. Theorem. Let formula_4 be a formula_1-dimensional tensegrity framework. If for all non-trivial infinitesimal motions formula_59 of formula_4, there exists a proper equilibrium stress formula_47 such that formula_244 then formula_4 is second-order rigid. An interesting application of tensegrities is in sphere-packings in polyhedral containers. Such a packing can be modelled as a tensegrity with struts between pairs of tangent spheres and between the boundaries of the container and the spheres tangent to them. This model has been studied to compute local maximal densities of these packings . The next result demonstrates when tensegrity frameworks have the same equilibrium stresses. Theorem. Let formula_4 be a formula_1-dimensional tensegrity framework with a proper stress formula_47 such that the stress matrix formula_51 is positive semidefinite. Then, formula_47 is a proper stress of all formula_1-dimensional tensegrity frameworks dominated by formula_4. Global rigidity theorems. The following is a sufficient condition for global rigidity of generic tensegrity frameworks based on stress matrices. Theorem. Let formula_4 be a formula_1-dimensional generic tensegrity framework with a proper equilibrium stress formula_47. If the stress matrix formula_51 has rank formula_217, then formula_4 is globally rigid in  formula_1 dimensions. While this theorem is for the generic setting, it does not offer a combinatorial characterization of generic global rigidity, so it is not quite a result of structural rigidity. Universal and dimensional rigidity. Let formula_4 be a formula_1-dimensional generic tensegrity framework, such that the affine span of formula_19 is formula_263, with a proper equilibrium stress formula_47 and the stress matrix formula_51. A finite set of non-zero vectors in formula_263 lie on a conic at infinity if, treating them as points in formula_267-dimensional projective space, they lie on a conic. Consider the following three statements: If  Statements 1 and 2 hold, then formula_4 is dimensionally rigid in formula_1-dimensions, and if Statement 3 also holds, then formula_4 is universally rigid in formula_1-dimensions.