Geometric rigidity
![]() | This article reads like a textbook. (November 2021) |
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Generic_vs_not.jpg/220px-Generic_vs_not.jpg)
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]
![](http://upload.wikimedia.org/wikipedia/commons/7/74/Types_rigidity.jpg)
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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle R(p) p' ' = -R(p')p'} , 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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Gcs_polyhedron.jpg/220px-Gcs_polyhedron.jpg)
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c5/Gcs_tensegrities.jpg/440px-Gcs_tensegrities.jpg)
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:
- is positive semidefinite.
- .
- 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]- ^ 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) - ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Cauchy, A. L. (1813). "Recherche sur les polyèdres – premier mémoire". Journal de l'École Polytechnique. 9: 66–86.
- ^ 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) - ^ 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) - ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Connelly, Robert (1978-09-01). "A flexible sphere". The Mathematical Intelligencer. 1 (3): 130–131. doi:10.1007/BF03023258. ISSN 0343-6993. S2CID 123071778.
- ^ Connelly, Robert (1978). "Conjectures and open questions in rigidity". Proc. Intern. Congress Helsinki.
- ^ 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.
- ^ Connelly, R.; Sabitov, I.; Walz, A. (1997). "The Bellows Conjecture". Contributions to Algebra and Geometry. 38: 1–10.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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