Geometric rigidity

In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system 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.
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

The definitions below, which can be found in, 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

The information in this section can be found in. 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

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
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. 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, see combinatorial characterizations of generically rigid graphs.

Static rigidity

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

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.

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 -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.

Global rigidity

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

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

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

Polyhedra

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.
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 -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. 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. 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. 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. 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 -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. 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.