Feature Column from the AMS

Linkages (Part II) - Old Wine in New Bottles

Breakthrough

3. Breakthrough

In 2000, Robert Connelly (Cornell), Eric Demaine (now at MIT), and Günter Rote (Berlin) announced that they had resolved the problem of straightening chain linkages and convexifying simple plane polygons when penetration of links is not permitted.

Robert Connelly

Erik Demaine Günter Rote

Their result showed that chain linkages could always be opened and plane polygonal linkages could be convexified, subject to not allowing links to do more than touch during the process. Furthermore, they were able to get additional insights into other aspects of the process.

Like many important new steps forward in mathematics, the work of Connelly, Demaine, and Rote builds on work that came prior to their own. The tools that they used in intriguing new ways involved ideas from linear programming (finding the maximum or minimum of a linear function over a region which is defined by linear constraints), rigidity theory (which configurations of linkages can and can not move freely in the plane) and the idea of an expansive motion. Some historical information will put some of this in better perspective.

In the 19th century A.L. Cauchy (1789-1857), in his work on polyhedra, stated a remarkable theorem:

Two convex (three-dimensional) polyhedra whose faces can be paired so that the corresponding faces are congruent (that is, there is an isometry between the surfaces of the polyhedra so that pairs of faces of the polyhedra match up), are congruent as three-dimensional objects.

Cauchy's Theorem is related to understanding when polyhedral structures are rigid in three-dimensional space. Important related work has been done by Connelly and Walter Whiteley (York University, Canada). Polyhedra can be thought of as being constructed with rods and, thus, viewed as a linkage. Alternatively, the polyhedron can be viewed as being made up of panels (the faces). For example, a (regular) cube made of panels is rigid, while a cube made of rods will flop around. Cauchy's Theorem can be interpreted as saying that convex panel polyhedra are rigid. In this context, it is not difficult to see that this result applies only to strictly convex polyhedra (i.e. neither faces nor edges of the polyhedra are subdivided into other edges or polygons). Also, it is not difficult to find counterexamples to the rigidity of non-convex polyhedra. In particular, consider the convex polyhedron whose surface consists of a rectangular solid with square ends (not a cube) and with a square pyramid on one of the square ends. This polyhedron is not congruent to the non-convex solid obtained from the polyhedron just described with the square pyramid reflected in the plane where the pyramid and rectangular solid are attached. This is despite the fact that pairs of faces on the surfaces of the two solids match up.

The proof of Cauchy's Theorem on polyhedra is based on a lemma that Cauchy proposed which deals with convex polygons.

Suppose we have a convex polygon A, B, C, ...., F. Suppose that this polygon is transformed into another polygon so that the sides of the polygon, AB, BC, ...., EF all stay fixed in length, and so that the angles at vertices B, C, ..., E also either increase in size or stay the same length (but at least one angle increases), then the length of the side AF in the new polygon increases.

(There is also an analogous theorem for decreasing angles.)

Cauchy gave a proof of this theorem which, like his proof of Euler's polyhedral formula, had a subtle error. This error remained undetected until it was spotted by the great German geometer Ernst Steinitz (1871-1928), but his proof was rather complex. A much easier proof was provided by I. Schoenberg and S. Zaremba in 1967. One can interpret Cauchy's Theorem as a statement about the distance between the first and last vertices in a chain linkage as the linkage is moved so that the angles between its consecutive links grow or stay unchanged. In this setting we see that the distance between the ends of the linkage must grow.

One of the critical insights that Connelly, Demaine, and Rote needed for their proof was the idea of an expansive motion. This is the notion that it might be possible to straighten a plane chain linkage in such a way that the distance between any pair of vertices that are not joined by a bar would not decrease as the straightening was carried out. Sometimes in mathematics it is easier to prove a stronger statement than one which seems simpler!

Since their work was published, Connelly, Demaine, and Rote (and others) have branched into new directions. This work has included similar problems for chain and polygonal linkages in spaces of dimensions three and higher. These studies may be helpful in getting insights into questions that involve the geometry of biological molecules and the folding of such molecules as proteins. Also, another major class of linkages came under investigation. This is linkages that form a tree. A tree is a connected graph which contains no circuits. (A chain linkage is a very special kind of tree.) Unlike planar chain and polygonal linkages, tree linkages can lock. Not all tree linkages can be straightened. Many recent investigations involving linkages have to do with issues of manipulating the linkage in a confined space such as a wedge, triangle, or square. In some cases a full understanding of the situation has been obtained; in other cases, the problem remains open.