Geometric rigidity

For rigid geometry, see Rigid analytic space. For other notions of rigidity in geometry, see Mostow rigidity theorem and Rigidity (mathematics).

In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system (GCS) has finitely many $d$-dimensional solutions, or frameworks, in some metric space. A framework of a GCS is rigid in $d$-dimensions, for a given $d$ 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 $(G,p)$ of a GCS has no nearby framework of the GCS that is reachable via a non-trivial continuous motion of $(G,p)$ 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 $\mathbb {R} ^{2}$. Assigning the edge $(b,d)$ the distance $0$ 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 $3$-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 $d$-dimensional Euclidean space, and will be generalized for other frameworks and metric spaces as needed. Consider a linkage $(G,\delta )$, i.e. a constraint graph $G=(V,E)$ with distance constraints $\delta$ assigned to its edges, and the configuration space ${\mathcal {C}}(G,\delta )$ consisting of frameworks $(G,p)$ of $(G,\delta )$. The frameworks in ${\mathcal {C}}(G,\delta )$ consist of maps $p:V\rightarrow \mathbb {R} ^{d|V|}$ that satisfy

$\|p(u)-p(v)\|^{2}=\delta _{uv},$

for all edges $(u,v)$ of $G$. In other words, $p$ is a placement of the vertices of $G$ as points in $d$-dimensions that satisfy all distance constraints $\delta$. The configuration space ${\mathcal {C}}(G,\delta )$ is an algebraic set.

Continuous and trivial motions. A continuous motion is a continuous path in ${\mathcal {C}}(G,\delta )$ that describes the physical motion between two frameworks of $(G,\delta )$ that preserves all constraints. A trivial motion is a continuous motion resulting from the $d+1 \choose 2$ 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 $\rho :\mathbb {R} ^{d|V|}\rightarrow \mathbb {R} ^{|E|}$ takes a framework $(G,p)$ and outputs the squared-distances $\|p(u)-p(v)\|^{2}$ 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

$(p(u)-p(v))\cdot (p'(v)-p'(u))=0,$

for all edges $(u,v)$ of $G$. The rigidity matrix $R(G,p)$ is an $|E|\times d|V|$ matrix that encodes the information in these equations. Each edge of $G$ corresponds to a row of $R(G,p)$ and each vertex corresponds to $d$ columns of $R(G,p)$. The row corresponding to the edge $(u,v)$ is defined as follows.

${\begin{bmatrix}\,&\dots &{\text{columns for }}u&\dots &{\text{columns for }}v&\dots \\\vdots &\,&\,&\vdots &\,&\,\\{\text{row for }}(u,v)&0\dots 0&p(u)-p(v)&0\dots 0&p(v)-p(u)&0\dots 0\\\vdots &\,&\,&\vdots &\,&\,\end{bmatrix}}$

Infinitesimal motion. An infinitesimal motion is an assignment $p':V\rightarrow \mathbb {R} ^{d}$ of velocities to the vertices of a framework $(G,p)$ such that $R(G,p)p'=0$. 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 $\omega :E\rightarrow \mathbb {R}$ to the edges of a framework $(G,p)$. A stress is proper if its entries are nonnegative and is a self stress if it satisfies $\omega R(G,p)=0$. A stress satisfying this equation is also called a resolvable stress, equilibrium stress, prestress, or sometimes just a stress.

Stress Matrix. For a stress $\omega$ applied to the edges of a framework $(G,p)$ with the constraint graph $G=(V,E)$, define the $|V|\times |V|$ stress matrix $\Omega$ as

$\Omega _{uv}={\begin{cases}-\omega _{uv}&{\text{if }}u\neq v\\\sum _{v\in V}{\omega _{uv}}&{\text{otherwise}}\end{cases}}$ .

It is easily verified that for any two $p,q\in \mathbb {R} ^{d|V|}$ and any stress $\omega$,

$\omega R(p)q=p^{T}\Omega q.$

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 $\mathbb {R} ^{d|V|}$ to $\mathbb {R} ^{|E|}$. The domain of this transformation is the set of $1\times d|V|$ column vectors, called velocity or displacements vectors, denoted by $p'$, and the image is the set of $1\times |E|$ edge distortion vectors, denoted by $e'$. The entries of the vector $p'$ are velocities assigned to the vertices of a framework $(G,p)$, and the equation $R(G,p)p'=e'$ 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 $1\times |E|$ column vectors, or stresses, denoted by $\omega$, that apply a stress $\omega _{uv}$ to each edge $(u,v)$ of a framework $(G,p)$. The stress $\omega _{uv}$ applies forces to the vertices of $(u,v)$ that are equal in magnitude but opposite in direction, depending on whether $(u,v)$ is being compressed or stretched by $\omega _{uv}$. Consider the equation $\omega ^{T}R(p)=f,$ where $f$ is a $1\times d|V|$ vector. The terms on the left corresponding to the $d$ columns of a vertex $v$ in $R(p)$ yield the entry in $f$ that is the net force $f_{v}$ applied to $v$ by the stresses on edges incident to $v$. 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 $f$ can be viewed as being able to counteract, or resolve, the force $-f$, 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 $p'$ under a net force $f$:

$W=fp'=(\omega R(p))p'=\omega (R(p)p')=\omega e',$

where $\omega$ is a stress and $e'$ is an edge distortion. In terms of the stress matrix, this equation above becomes $W=p^{T}\Omega p'$.

Types of rigidity

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

The rigidity hierarchy.

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

$(p(u)-p(v))\cdot (p'(u)-p'(v))=0$

resulting from the equation $R(G,p)p'=0$. These equations state that the projections of the velocities $p'(u)$ and $p'(v)$ onto the edge $(u,v)$ cancel out. Each of the following statements is sufficient for a $d$-dimensional framework to be infinitesimally rigid in $d$-dimensions:

• all its infinitesimal motions are trivial;
• the dimension of the kernel of $R(p)$ is $d+1 \choose 2$; or
• the rank of $R(p)$ is $d|V|-{d+1 \choose 2}$.

In general, any type of framework is infinitesimally rigid in $d$-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 $d$-dimensional framework $(G,p)$ is statically rigid in $d$-dimensions if every force vector $f$ on the vertices of $(G,p)$ that is orthogonal to the trivial motions can be resolved by the net force of some proper stress $\omega$; or written mathematically, for every such force vector $f$ there exists a proper stress $\omega$ such that

$f+\omega R(p)=0.$

Equivalently, the rank of $R(p)$ must be $d|V|-{d+1 \choose 2}$. 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

$(p(u)-p(v))\cdot (p''(u)-p''(v))+(p'(u)-p'(v))\cdot (p'(u)-p'(v))=0.$

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

• every solution pair $(p',p'')$ to the equation above consists of a trivial infinitesimal motion $p'$;
• for every non-trivial infinitesimal motion $p'$, there is no acceleration $p''$ satisfying the equation above; or
• for each non-trivial infinitesimal motion $p'$, there is some equilibrium stress $\omega$ such that $\omega ^{T}R(p')p'>0$.

The third statement shows that for each such $p'$, $R(p')p'$ is not in the column span of $R(p)$, i.e., it is not an edge distortion resulting from $p'$. This follows from the Fredholm alternative: since the column span of $R(p)$ is orthogonal to the kernel of $R(p)^{T}$, i.e., the set of equilibrium stresses, either $R(p)p''=-R(p')p'$ for some acceleration $p''$ or there is an equilibrium stress $\omega$ satisfying the third condition. The third condition can be written in terms of the stress matrix: $p'^{T}\Omega p'>0$. Solving for $\omega$ is a non-linear problem in $p'$ 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 $d$-dimensional framework $(G,p)$ is prestress stable if there exists an equilibrium stress $\omega$ such that for all non-trivial velocities $p'$, $p'^{T}\Omega p'>0$. Prestress stability can be verified via semidefinite programming techniques.

Global rigidity

A $d$-dimensional framework $(G,p)$ of a linkage $(G,\delta )$ is globally rigid in $d$-dimensions if all frameworks in the configuration space ${\mathcal {C}}(G,\delta )$ are equivalent up to trivial motions, i.e., factoring out the trivial motions, there is only one framework of $(G,\delta )$.

Theorem. Global rigidity is a generic property of graphs.

Minimal rigidity

A $d$-dimensional framework $(G,p)$ is minimally rigid in $d$-dimensions if $(G,p)$ is rigid and removing any edge from $(G,p)$ results in a framework that is not rigid.

Redundant rigidity

There are two types of redundant rigidity: vertex-redundant and edge-redundant rigidity. A $d$-dimensional framework $(G,p)$ is edge-redundantly rigid in $d$-dimensions if $(G,p)$ is rigid and removing any edge from $(G,p)$ 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 $3$-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.

A strictly convex polyhedral framework whose $2$-skeleton is rigid.

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

Theorem. The $2$-skeleton of any polyhedral framework of the octahedron in $3$-dimensions is rigid. However, there exists a framework of the octahedron whose $1$-skeleton is not rigid in $3$-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 $1$-skeleton of the resulting polyhedron is infinitesimally rigid.

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

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

Theorem. The $1$-skeleton of a strictly convex polyhedron embedded in $3$-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 $3$-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 $3$-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 $(G,p)$ is a velocity vector $p':V\rightarrow \mathbb {R} ^{d}$ such that for each edge $(u,v)$ of the framework,

• $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})=0$, if $(u,v)$ is a bar;
• $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})\leq 0$, if $(u,v)$ is a cable; and
• $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})\geq 0$, if $(u,v)$ is a strut.

Second-order motion. A second-order motion of a tensegrity framework $(G,p)$ is a solution $(p',p'')$ to the following constraints:

• Bar constraint: $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})=0$ and $\|p'_{u}-p'_{v}\|^{2}+(p_{u}-p_{v})\cdot (p''_{u}-p''_{v})=0$;
• Cable constraint: $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})=0$ and $\|p'_{u}-p_{v}\|^{2}+(p_{u}-p_{v})\cdot (p''_{u}-p'_{v})\leq 0$ or $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})<0$; and
• Cable constraint: $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})=0$ and $\|p'_{u}-p_{v}\|^{2}+(p_{u}-p_{v})\cdot (p''_{u}-p'_{v})\geq 0$ or $(p_{u}-p_{v})\cdot (p'_{u}-p'_{v})>0$.

Global rigidity.’ A $d$-dimensional tensegrity framework $(G,p)$ of a tensegrity GCS is globally rigid in $d$-dimensions if every other $d$-dimensional framework $(G,q)$ of the same GCS that is dominated by $(G,p)$ can be obtained via a trivial motion of $(G,p)$.

Universal rigidity. A $d$-dimensional tensegrity framework $(G,p)$ of a tensegrity GCS is universally rigid if it is globally rigid in any dimension.

Dimensional rigidity. A $d$-dimensional tensegrity framework $(G,p)$ of a tensegrity GCS is dimensionally rigid in $d$-dimensions if any other $D$-dimensional tensegrity framework $(G,q)$, for any $D$ satisfying the constraints of the GCS, has an affine span of dimension at most $d$.

Super stable. A $d$-dimensional tensegrity framework $(G,p)$ is super stable in $d$-dimensions if is rigid in $d$-dimensions as a bar-joint framework and has a proper equilibrium stress $\omega$ such that the stress matrix $\Omega$ is positive semidefinite and has rank $|V|-d-1$.

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

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

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

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

Theorem. Let $(G,p)$ be a $d$-dimensional tensegrity framework where: the vertices of $G$ 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, $(G,p)$ is rigid in $d$-dimensions if and only if it is infinitesimally rigid in $d$-dimensions.

The following is a necessary condition for rigidity.

Theorem. Let $(G,p)$ be a $d$-dimensional tensegrity framework with at least one cable or strut. If $(G,p)$ is rigid in $d$-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 $(G,p)$ be a $d$-dimensional tensegrity framework with at least one cable or strut. Then $(G,p)$ is infinitesimally rigid in $d$-dimensions if it is rigid in $d$-dimensions as a bar-joint framework and has a strict proper stress.

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

Theorem. Let $(G,p)$ be a $d$-dimensional tensegrity framework. If for all non-trivial infinitesimal motions $p'$ of $(G,p)$, there exists a proper equilibrium stress $\omega$ such that

$\sum _{u,v\in V}\omega _{uv}(p'_{u}-p'_{v})\cdot (p'_{u}-p'_{v})>0,$

then $(G,p)$ 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 $(G,p)$ be a $d$-dimensional tensegrity framework with a proper stress $\omega$ such that the stress matrix $\Omega$ is positive semidefinite. Then, $\omega$ is a proper stress of all $d$-dimensional tensegrity frameworks dominated by $(G,p)$.

Global rigidity theorems

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

Theorem. Let $(G,p)$ be a $d$-dimensional generic tensegrity framework with a proper equilibrium stress $\omega$. If the stress matrix $\Omega$ has rank $|V|-d-1$, then $(G,p)$ is globally rigid in $d$ 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 $(G,p)$ be a $d$-dimensional generic tensegrity framework, such that the affine span of $p$ is $\mathbb {R} ^{d}$, with a proper equilibrium stress $\omega$ and the stress matrix $\Omega$. A finite set of non-zero vectors in $\mathbb {R} ^{d}$ lie on a conic at infinity if, treating them as points in $(d-1)$-dimensional projective space, they lie on a conic. Consider the following three statements:

1. $\Omega$ is positive semidefinite.
2. $rank(\Omega )=|V|-d-1$.
3. The edge directions of $(G,p)$ with a non-zero stress, and bars, do not lie on a conic at infinity.

If Statements 1 and 2 hold, then $(G,p)$ is dimensionally rigid in $d$-dimensions, and if Statement 3 also holds, then $(G,p)$ is universally rigid in $d$-dimensions.