In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system (GCS) has finitely many -dimensional solutions, or frameworks, in some metric space. A framework of a GCS is rigid in -dimensions, for a given 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 of a GCS has no nearby framework of the GCS that is reachable via a non-trivial continuous motion of 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.

Left: a generically rigid graph in . Assigning the edge the distance results in a family of non-generic flexible bar-joint systems. Right: a flexible framework of such a system.

Geometric rigidity was first explored by Euler, who conjectured that all polyhedra in -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

edit

The definitions below, which can be found in,[1] are with respect to bar-joint frameworks in  -dimensional Euclidean space, and will be generalized for other frameworks and metric spaces as needed. Consider a linkage  , i.e. a constraint graph   with distance constraints   assigned to its edges, and the configuration space   consisting of frameworks   of  . The frameworks in   consist of maps   that satisfy

 

for all edges   of  . In other words,   is a placement of the vertices of   as points in  -dimensions that satisfy all distance constraints  . The configuration space   is an algebraic set.

Continuous and trivial motions. A continuous motion is a continuous path in   that describes the physical motion between two frameworks of   that preserves all constraints. A trivial motion is a continuous motion resulting from the   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   takes a framework   and outputs the squared-distances   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

 

for all edges   of  . The rigidity matrix   is an   matrix that encodes the information in these equations. Each edge of   corresponds to a row of   and each vertex corresponds to   columns of  . The row corresponding to the edge   is defined as follows.

 

Infinitesimal motion. An infinitesimal motion is an assignment   of velocities to the vertices of a framework   such that  . 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   to the edges of a framework  . A stress is proper if its entries are nonnegative and is a self stress if it satisfies  . A stress satisfying this equation is also called a resolvable stress, equilibrium stress, prestress, or sometimes just a stress.

Stress Matrix. For a stress   applied to the edges of a framework   with the constraint graph  , define the   stress matrix   as

  .

It is easily verified that for any two   and any stress  ,

 

The rigidity matrix as a linear transformation

edit

The information in this section can be found in.[1] The rigidity matrix can be viewed as a linear transformation from   to  . The domain of this transformation is the set of   column vectors, called velocity or displacements vectors, denoted by  , and the image is the set of   edge distortion vectors, denoted by  . The entries of the vector   are velocities assigned to the vertices of a framework  , and the equation   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   column vectors, or stresses, denoted by  , that apply a stress   to each edge   of a framework  . The stress   applies forces to the vertices of   that are equal in magnitude but opposite in direction, depending on whether   is being compressed or stretched by  . Consider the equation   where   is a   vector. The terms on the left corresponding to the   columns of a vertex   in   yield the entry in   that is the net force   applied to   by the stresses on edges incident to  . 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   can be viewed as being able to counteract, or resolve, the force  , 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   under a net force  :

 

where   is a stress and   is an edge distortion. In terms of the stress matrix, this equation above becomes  .

Types of rigidity

edit

This section covers the various types of rigidity and how they are related.  For more information, see.[1]

 
The rigidity hierarchy.

Infinitesimal rigidity

edit

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

 

resulting from the equation  . These equations state that the projections of the velocities   and   onto the edge   cancel out. Each of the following statements is sufficient for a  -dimensional framework to be infinitesimally rigid in  -dimensions:

  • all its infinitesimal motions are trivial;
  • the dimension of the kernel of   is  ; or
  • the rank of   is  .

In general, any type of framework is infinitesimally rigid in  -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. [2][3] 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

edit

A  -dimensional framework   is statically rigid in  -dimensions if every force vector   on the vertices of   that is orthogonal to the trivial motions can be resolved by the net force of some proper stress  ; or written mathematically, for every such force vector   there exists a proper stress   such that

 

Equivalently, the rank of   must be  . Static rigidity is equivalent to infinitesimal rigidity.

Second-order rigidity

edit

Second-order rigidity is weaker than infinitesimal and static rigidity. The second derivative of the rigidity map consists of equations of the form

 

The vector   assigns an acceleration to each vertex of a framework  . These equations can be written in terms of matrices:  , where   is defined similarly to the rigidity matrix. Each of the following statements are sufficient for a  -dimensional framework to be second-order rigid in  -dimensions:

  • every solution pair   to the equation above consists of a trivial infinitesimal motion  ;
  • for every non-trivial infinitesimal motion  , there is no acceleration   satisfying the equation above; or
  • for each non-trivial infinitesimal motion  , there is some equilibrium stress   such that  .

The third statement shows that for each such  ,   is not in the column span of  , i.e., it is not an edge distortion resulting from  . This follows from the Fredholm alternative: since the column span of   is orthogonal to the kernel of  , i.e., the set of equilibrium stresses, either   for some acceleration   or there is an equilibrium stress   satisfying the third condition. The third condition can be written in terms of the stress matrix:  . Solving for   is a non-linear problem in   with no known efficient algorithm.[4]

Prestress stability

edit

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  -dimensional framework   is prestress stable if there exists an equilibrium stress   such that for all non-trivial velocities  ,  . Prestress stability can be verified via semidefinite programming techniques.[4]

Global rigidity

edit

A  -dimensional framework   of a linkage   is globally rigid in  -dimensions if all frameworks in the configuration space   are equivalent up to trivial motions, i.e., factoring out the trivial motions, there is only one framework of  .

Theorem. Global rigidity is a generic property of graphs.

Minimal rigidity

edit

A  -dimensional framework   is minimally rigid in  -dimensions if   is rigid and removing any edge from   results in a framework that is not rigid.

Redundant rigidity

edit

There are two types of redundant rigidity: vertex-redundant and edge-redundant rigidity. A  -dimensional framework   is edge-redundantly rigid in  -dimensions if   is rigid and removing any edge from   results in another rigid framework. Vertex-redundant rigidity is defined analogously.

Rigidity for various types of frameworks

edit

Polyhedra

edit

This section concerns the rigidity of polyhedra in  -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.[5]

Conjecture. [5] 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.[6] The first major result is by Cauchy in 1813 and is known as Cauchy's theorem.

Cauchy's Theorem. [7] 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,[8] and a slightly generalized result was given in.[9] The following corollary of Cauchy's theorem relates this result to rigidity.

 
A strictly convex polyhedral framework whose  -skeleton is rigid.

Corollary. The 2-skeleton of a strictly convex polyhedral framework in  -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  -skeletons of the octahedron.

Theorem. [10] The  -skeleton of any polyhedral framework of the octahedron in  -dimensions is rigid. However, there exists a framework of the octahedron whose  -skeleton is not rigid in  -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. [9] If vertices are inserted in the edges of a strictly convex polyhedron and the faces are triangulated, then the  -skeleton of the resulting polyhedron is infinitesimally rigid.

Corollary. If a convex polyhedron in  -dimensions has the property that the collection of faces containing a given vertex do not all lie in the same plane, then the  -skeleton of that polyhedron is infinitesimally rigid.

The following result shows that the triangulation condition in the above theorem is necessary.

Theorem. [2] The  -skeleton of a strictly convex polyhedron embedded in  -dimensions which has at least one non-triangluar face is not rigid.

The following conjecture extends Cauchy's result to more general polyhedra.

Conjecture. [11] Two combinatorially equivalent polyhedra with equal corresponding dihedral angles are isogonal.

This conjecture has been proved for some special cases.[12] The next result applies in the generic setting, i.e., to almost all polyhedra with the same combinatorial structure, see structural rigidity.

Theorem. [13] Every closed simply connected polyhedral surface with a  -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  -dimensions, disproving the conjecture.[6] 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.[14] An interesting property of this polyhedra is that its volume remains constant along any continuous motion path, leading to the following conjecture.

Bellows Conjecture. [15] Every orientable closed polyhedral surface flexes with constant volume.

This conjecture was first proven for spherical polyhedra[16] and then in general.[17]

Tensegrities

edit

This section concerns the rigidity of tensegrities, see tensegrity systems for a definition of this type of GCS.

Definitions

edit

The definitions below can be found in.[1]

Infinitesimal motion. An infinitesimal motion of a tensegrity framework   is a velocity vector   such that for each edge   of the framework,

  •  , if   is a bar;
  •  , if   is a cable; and
  •  , if   is a strut.

Second-order motion. A second-order motion of a tensegrity framework   is a solution   to the following constraints:

  • Bar constraint:   and  ;
  • Cable constraint:   and   or  ; and
  • Cable constraint:   and   or  .

Global rigidity.’ A  -dimensional tensegrity framework   of a tensegrity GCS is globally rigid in  -dimensions if every other  -dimensional framework   of the same GCS that is dominated by   can be obtained via a trivial motion of  .

Universal rigidity. A  -dimensional tensegrity framework   of a tensegrity GCS is universally rigid if it is globally rigid in any dimension.

Dimensional rigidity. A  -dimensional tensegrity framework   of a tensegrity GCS is dimensionally rigid in  -dimensions if any other  -dimensional tensegrity framework  , for any   satisfying the constraints of the GCS, has an affine span of dimension at most  .

Super stable. A  -dimensional tensegrity framework   is super stable in  -dimensions if is rigid in  -dimensions as a bar-joint framework and has a proper equilibrium stress   such that the stress matrix   is positive semidefinite and has rank  .

Rigidity theorems

edit

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  -dimension.[18] The following result equates generic redundant rigidity of graphs to infinitesimally rigid tensegrities.

Theorem. [19] A graph   has an infinitesimally rigid tensegrity framework in  -dimensions, for some partition of the edges of   into bars, cables, and struts if and only if   is generically edge-redundantly rigid in  -dimensions.

 
Two infinitesimally rigid tensegrities with their struts (marked edges) and cables (dashed edges) swapped.[1]

The first result demonstrates when rigidity and infinitesimal rigidity of tensegrities are equivalent.

Theorem. [20] Let   be a  -dimensional tensegrity framework where: the vertices of   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,   is rigid in  -dimensions if and only if it is infinitesimally rigid in  -dimensions.

The following is a necessary condition for rigidity.

Theorem. [21] Let   be a  -dimensional tensegrity framework with at least one cable or strut. If   is rigid in  -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. [22] Let   be a  -dimensional tensegrity framework with at least one cable or strut. Then   is infinitesimally rigid in  -dimensions if it is rigid in  -dimensions as a bar-joint framework and has a strict proper stress.

The following is a sufficient condition for second-order rigidity.

Theorem. [20] Let   be a  -dimensional tensegrity framework. If for all non-trivial infinitesimal motions   of  , there exists a proper equilibrium stress   such that

 

then   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.[23][24]

The next result demonstrates when tensegrity frameworks have the same equilibrium stresses.

Theorem. [25] Let   be a  -dimensional tensegrity framework with a proper stress   such that the stress matrix   is positive semidefinite. Then,   is a proper stress of all  -dimensional tensegrity frameworks dominated by  .

Global rigidity theorems

edit

The following is a sufficient condition for global rigidity of generic tensegrity frameworks based on stress matrices.

Theorem. [26] Let   be a  -dimensional generic tensegrity framework with a proper equilibrium stress  . If the stress matrix   has rank  , then   is globally rigid in   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

edit

Let   be a  -dimensional generic tensegrity framework, such that the affine span of   is  , with a proper equilibrium stress   and the stress matrix  . A finite set of non-zero vectors in   lie on a conic at infinity if, treating them as points in  -dimensional projective space, they lie on a conic. Consider the following three statements:

  1.   is positive semidefinite.
  2.  .
  3. The edge directions of   with a non-zero stress, and bars, do not lie on a conic at infinity.

If Statements 1 and 2 hold, then   is dimensionally rigid in  -dimensions,[25] and if Statement 3 also holds, then   is universally rigid in  -dimensions.[27]

References

edit
  1. ^ a b c d e Sitharam, Meera (20 July 2018). Handbook of geometric constraint systems principles. St. John, Audrey,, Sidman, Jessica. Boca Raton. ISBN 978-1-4987-3892-7. OCLC 1046084888.{{cite book}}: CS1 maint: location missing publisher (link)
  2. ^ a b Asimow, L.; Roth, B. (1978). "The rigidity of graphs". Transactions of the American Mathematical Society. 245: 279–289. doi:10.1090/S0002-9947-1978-0511410-9. ISSN 0002-9947.
  3. ^ Asimow, L; Roth, B (1979-03-01). "The rigidity of graphs, II". Journal of Mathematical Analysis and Applications. 68 (1): 171–190. doi:10.1016/0022-247X(79)90108-2. ISSN 0022-247X.
  4. ^ a b Holmes‐Cerfon, Miranda; Theran, Louis; Gortler, Steven J. (2020). "Almost-Rigidity of Frameworks". Communications on Pure and Applied Mathematics. 74 (10): 2185–2247. arXiv:1908.03802. doi:10.1002/cpa.21971. ISSN 1097-0312. S2CID 199543753.
  5. ^ a b Euler, Leonhard; Fuss, Nikola Ivanovich; Fuss, Paul Heinrich von (1862). Opera postuma mathematica et physica anno 1844 detecta quae Academiae scientiarum petropolitanae obtulerunt ejusque auspicus ediderunt auctoris pronepotes Paulus Henricus Fuss et Nicolaus Fuss. Petropoli: Eggers et Socius. doi:10.5962/bhl.title.24416.
  6. ^ a b Connelly, Robert (1977-12-01). "A counterexample to the rigidity conjecture for polyhedra". Publications Mathématiques de l'Institut des Hautes Études Scientifiques. 47 (1): 333–338. doi:10.1007/BF02684342. ISSN 1618-1913. S2CID 122968997.
  7. ^ Cauchy, A. L. (1813). "Recherche sur les polyèdres – premier mémoire". Journal de l'École Polytechnique. 9: 66–86.
  8. ^ Steinitz, Ernst 1871-1928 (7 March 2013). Vorlesungen über die Theorie der Polyeder unter Einschluß der Elemente der Topologie. Rademacher, Hans 1892-1969. Berlin, Heidelberg. ISBN 978-3-642-65609-5. OCLC 863787946.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: numeric names: authors list (link)
  9. ^ a b Aleksandrov, A. D. (Aleksandr Danilovich), 1912-1999. (2005). Convex polyhedra. Berlin: Springer. ISBN 3-540-23158-7. OCLC 62750601.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
  10. ^ Bricard, Raoul (1897). "Mémoire sur la théorie de l'octaèdre articulé". Journal de Mathématiques Pures et Appliquées. 3: 113–148.
  11. ^ Stoker, J. J. (1968). "Geometrical problems concerning polyhedra in the large". Communications on Pure and Applied Mathematics. 21 (2): 119–168. doi:10.1002/cpa.3160210203. ISSN 1097-0312.
  12. ^ Karcher, Hermann (1968). "Remarks on polyhedra with given dihedral angles". Communications on Pure and Applied Mathematics. 21 (2): 169–174. doi:10.1002/cpa.3160210204. ISSN 1097-0312.
  13. ^ Gluck, Herman (1975). "Almost all simply connected closed surfaces are rigid". In Glaser, Leslie Curtis; Rushing, Thomas Benjamin (eds.). Geometric Topology. Lecture Notes in Mathematics. Vol. 438. Berlin, Heidelberg: Springer. pp. 225–239. doi:10.1007/BFb0066118. ISBN 978-3-540-37412-1.
  14. ^ Connelly, Robert (1978-09-01). "A flexible sphere". The Mathematical Intelligencer. 1 (3): 130–131. doi:10.1007/BF03023258. ISSN 0343-6993. S2CID 123071778.
  15. ^ Connelly, Robert (1978). "Conjectures and open questions in rigidity". Proc. Intern. Congress Helsinki.
  16. ^ Sabitov, I Kh (1995-04-30). "On the problem of invariance of the volume of a flexible polyhedron". Russian Mathematical Surveys. 50 (2): 451–452. Bibcode:1995RuMaS..50..451S. doi:10.1070/RM1995v050n02ABEH002095. ISSN 0036-0279. S2CID 250898116.
  17. ^ Connelly, R.; Sabitov, I.; Walz, A. (1997). "The Bellows Conjecture". Contributions to Algebra and Geometry. 38: 1–10.
  18. ^ Jackson, Bill; Jordán, Tibor; Király, Csaba (2013-05-01). "Strongly rigid tensegrity graphs on the line". Discrete Applied Mathematics. 161 (7–8): 1147–1149. doi:10.1016/j.dam.2012.12.009. ISSN 0166-218X.
  19. ^ Jordán, Tibor; Recski, András; Szabadka, Zoltán (2009-11-01). "Rigid tensegrity labelings of graphs". European Journal of Combinatorics. 30 (8): 1887–1895. doi:10.1016/j.ejc.2008.12.014. ISSN 0195-6698.
  20. ^ a b Connelly, Robert; Whiteley, Walter (1996). "Second-Order Rigidity and Prestress Stability for Tensegrity Frameworks". SIAM Journal on Discrete Mathematics. 9 (3): 453–491. doi:10.1137/S0895480192229236. ISSN 0895-4801.
  21. ^ Connelly, Robert (1982-02-01). "Rigidity and energy". Inventiones Mathematicae. 66 (1): 11–33. Bibcode:1982InMat..66...11C. doi:10.1007/BF01404753. ISSN 1432-1297. S2CID 2887038.
  22. ^ Roth, B.; Whiteley, W. (1981). "Tensegrity frameworks". Transactions of the American Mathematical Society. 265 (2): 419–446. doi:10.1090/S0002-9947-1981-0610958-6. ISSN 0002-9947.
  23. ^ Connelly, Robert (2008-11-01). "Rigidity of packings". European Journal of Combinatorics. 29 (8): 1862–1871. doi:10.1016/j.ejc.2008.01.009. ISSN 0195-6698.
  24. ^ Connelly, Robert; Dickinson, William (2014-02-13). "Periodic planar disc packings". Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 372 (2008): 20120039. doi:10.1098/rsta.2012.0039. PMID 24379429. S2CID 7704606.
  25. ^ a b Alfakih, A.Y.; Nguyen, Viet-Hang (2013-11-15). "On affine motions and universal rigidity of tensegrity frameworks". Linear Algebra and Its Applications. 439 (10): 3134–3147. arXiv:1305.5955. doi:10.1016/j.laa.2013.08.016. ISSN 0024-3795. S2CID 119709339.
  26. ^ Connelly, Robert (2005-04-01). "Generic Global Rigidity". Discrete & Computational Geometry. 33 (4): 549–563. doi:10.1007/s00454-004-1124-4. ISSN 1432-0444. S2CID 1009906.
  27. ^ Connelly, Robert (2013), Senechal, Marjorie (ed.), "Tensegrities and Global Rigidity", Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, New York, NY: Springer, pp. 267–278, doi:10.1007/978-0-387-92714-5_21, ISBN 978-0-387-92714-5, retrieved 2021-01-24