Audrey St. John |
## RigidityI am interested in problems relating to the rigidity ofgeometric constraint systems.
We motivate the concepts in rigidity theory by starting with the most well-studied model of 2D bar-and-joint.
Note that, while an elegant combinatorial characterization exists for 2D, such a characterization for
3D bar-and-joint rigidity remains one of the biggest open problems in rigidity theory! What is known about
3D is a result for a different type of model, called body-and-bar structures.
Coming soon -- more definitions and examples, including pinning (via sliders) and directional ("parallel redrawings") rigidity! ## 2D bar-and-joint rigidityConsider a structure composed of universal joints connected by fixed-length bars in the plane. Such a structure may be rigid or flexible:For example, a triangle is rigid once its edge lengths are fixed; the only motion in the
plane that would maintain the distance constraints are trivial motions (translation and rotation).
On the other hand, a four-bar structure is flexible and admits a non-trivial motion; we
say such a structure has one "internal degree of freedom." When counting "degrees of freedom," the trivial
degrees are often taken into account, meaning that the triangle would have 3 degrees of freedom, whereas
the four-bar structure has 4. To gain more intuitions as to how bar-and-joint structures in the plane
move, try the 2D motion simulation demo.So-called "generic" rigidity for 2D bar-and-joint structures was characterized by Laman in 1970 with a counting property, stated as follows: Theorem [Laman, 19070]: A graph with n vertices and m edges is (generically) minimally rigid
if and only if
- m = 2n - 3
- for all subsets of n' vertices, m' <= 2n' - 3, where m' is the number of edges spanned by that vertex set
## 3D body-and-bar/hinge rigidityConsider a structure composed of rigid bodies in 3-space, connected by fixed-length bars and hinges. A bar is rigidly attached at its endpoints to the bodies by universal joints, imposing a distance constraint. A hinge is shared among two bodies and imposes both a distance and an angle constraint; the only motion allowed is rotation about the hinge axis.
Both Examples 1 and 2 above are minimally rigid structures, but how can we tell? In 1984, Tay characterized minimally (generically) rigid body-and-bar structures as follows: Theorem[Tay, 1984]:
Given a 3D body-and-bar structure, associate a graph by mapping bodies to vertices and bars to edges.
The original structure is rigid if and only if the associated graph is the edge-disjoint union of 6 spanning trees.
Tay's Theorem also applies to body-and-hinge and body-and-bar/hinge structures, given the observation that a hinge is equivalent to 5 bars [Tay, Whiteley]. A famous result of Nash-Williams and Tutte (independently) characterizes those graphs that are the edge-disjoint union of k spanning trees with a counting property: Theorem[Nash-Williams, Tutte]: A graph with m edges and n vertices
is the edge-disjoint union of k spanning trees if and only if:
- m = kn-k
- for all subsets of n' vertices, m' <= kn'-k, where m' is the number of edges spanned by the vertex set
(k, k)-tightness property.For instance, here we see the two graphs associated with Examples 1 and 2; note that the graph for Example 1 is colored to see 6 edge-disjoint spanning trees. Both examples satisfy the counting property of (6,6)-tightness.
Because Tay's result relates 3D body-and-bar/hinge rigidity to (6,6)-tight graphs, the (6,6)-pebble game can be used for solving (generic) rigidity problems in this model. |