Feature Column from the AMS

Linkages (Part II) - Old Wine in New Bottles

Further steps

4. Further steps

The work of Connelly, Demaine, and Rote was a breakthrough. However, relatively shortly after their work appeared, Ileana Streinu (Smith College) provided a dramatic new approach to the subject.

Ileana Streinu

One problem with the work of Connelly, Demaine, and Rote was that it did not provide a constructive way to actually carry out convexification of a polygon or the straightening of a chain linkage beyond using approximations to the schemes in their proof. The work of Ileana Streinu dealt with this issue.

Streinu's proof uses a variety of clever ideas, in particular, she takes great advantage of structures that at first glance seem to be rather strange - pseudo-triangulations. Before looking at a pseudo-triangulation, first let us look at triangulations of the plane. It is not surprising that triangulations of the plane would be of considerable interest because among all graphs that can be drawn in the plane with a fixed number of vertices, these graphs have the maximal number of edges. An example of a triangulation is shown below:

Figure 1

Triangulations are also known as maximal planar graphs because of the property that if one adds even a single edge between two vertices of a triangulation that are not already joined, the result is a graph which can not be redrawn in the plane without crossings at points that are not vertices. (Such graphs are referred to as non-planar graphs). Triangulations are also of interest from the point of view of rigidity. One can show that any plane triangulation other than the one with three vertices can be realized as a three-dimensional convex polyhedron. Thus, there is a three-dimensional convex polyhedron whose graph is structurally the same (isomorphic) to the triangulation above. Such a polyhedron will be rigid as a collection of rods in 3-space.

In proving theorems, sometimes it is actually easier to carry out the proof on a larger class of objects. For example, instead of triangulations one can consider near triangulations. These are structures drawn in the plane without edge crossings which have one face not necessarily a triangle, and all the other faces triangles. An example of a near triangulation with exactly one face which is a 4-gon (keep in mind that edges may also bind an infinite face, in this case, the exterior.) is shown below:

Figure 2

An even more specialized class of objects involving triangles is obtained when one has a near triangulation in which all the vertices appear on the one face that may not be a triangle. This type of structure is called a triangulated polygon. The original polygon is shown in blue and the diagonals that subdivide it into triangles are shown in black. An example of a triangulated 12-gon is shown below:

Figure 3

Mathematicians love to work with similar kinds of structures (e.g. triangulations, near triangulations, triangulated polygons) so that they can see what properties all the structures have and what properties fail to hold due to the small changes in the definitions of the structures. Mathematicians are always slightly changing the rules of the game to see if the new rules yield more interesting, as interesting, or dull new games. To see a simple example of this kind of thing at work, we have considered the three types of structures (triangulations, near triangulations, and triangulated polygons) as completed objects. Now consider the following: given a collection of points in the plane, under what conditions can we add line segments which intersect only at the points, so that we get a polygon, triangulation, near-triangulation, or a triangulated polygon? (There are also enumeration questions associated with these questions.)

Do you see how to add line segments to the plane point set below to get a triangulated 9-gon?

Figure 4

Can you show that every point set with n points that can be turned into a triangulated n-gon has to have 2n - 2 edges added? Can you verify that the point set above can not be triangulated? This is how theorems are born.

We are now better prepared to investigate the idea of a pseudo-triangulation. A pseudo-triangle is a polygon drawn in the plane which has exactly three convex vertices. A vertex of a polygon is convex if the (internal) angle between the edges of the polygon at a vertex is strictly less than 180 degrees. (We will only consider polygons with vertices that do not have straight angles for simplicity of exposition, though some of the results we mention do require analysis of such degenerate cases.) Note that ordinary triangles are pseudo-triangles as well.

Figure 5

Given a set of points P in the plane, the convex hull of these points is the intersection of all convex sets which contain the points of P. If one thinks of the points as being represented by nails in a board, and we put a tight rubber band around the nails, the rubber band will form the convex hull of the points. A pseudo-triangulation of a point set in the plane joins the vertices in the convex hull of the point set with edges, as well as additional edges so that all the polygons within the convex hull are pseudo-triangles. Here is an example of a pseudo-triangulation:

Figure 6

Note that the triangulation and near triangulation above (Figures 1 and 2) are also pseudo-triangulations, while the triangulated polygon in Figure 3 is not a pseudo-triangulation. This is because the convex hull vertices of the point set involved are not joined by edges. Also note that some of the edges, though not any old edge at all, can be omitted from the triangulation and near triangulations above and the result will be a pseudo-triangulation. For example, in the near triangulation (Figure 2), removing edge e₁ gives rise to a pseudo-triangulation while removing edge e₂ does not yield a pseudo-triangulation. Note that removing either of these two edges does not preserve the property of being a near triangulation. What is special about the pseudo-triangulation above (Figure 6) is that no edges can be removed and have the result still be a pseudo-triangulation (although edges can be added and still the property of being a pseudo-triangulation will hold). Minimal, sometimes called pointed, pseudo-triangulations have the property that for that set of points there is no pseudo-triangulation with fewer edges. Some pseudo-triangulations have some very special properties. For example, if a pseudo-triangulation PT is minimal and has n vertices, then:

* PT has exactly 2n - 3 edges

* PT has exactly n - 2 interior faces

* PT has the property that the cone of all edges at each vertex has an angle which is less than 180° (i.e. is pointed ).

Such triangulations also have the nice property that one can get between a given minimal pseudo-triangulation and other pseudo-triangulations on the same vertex set via a series of flips. Also, such pseudo-triangulations are rigid, because they satisfy the hypotheses of an important theorem in rigidity theory due to G. Laman.

At last, (doing mathematics is like organizing a well-structured military campaign!) we are in a position to say a bit more about Ileana Streinu's work on straightening linkages. Streinu studied the properties of linkages derived from minimal pseudo-triangulations. More specifically she looked at the consequence of removing a single edge from the infinite face of a minimal pseudo-triangulation (the edges of the convex hull). She was able to show that the resulting linkage is no longer rigid but flexible. However, it has the special property that its motion, when one moves an interior vertex of the linkage, is monotone. In Streinu's terminology this means that when a vertex is moved a small amount,.the distances between the vertices not linked by bars either all increase or all decrease Here the main result was to show that if one has a plane n-vertex polygon it can be convexified with a most n² motions. These motions are associated with a pseudo-triangulation based on the polygon to be convexified. With one edge removed from the convex hull polygon, the flexible structure is moved until two adjacent edges straighten. At that point a new pseudo-triangulation is obtained by a diagonal flip, and the process continues until the polygon is convexified. In the usual tradition that "every problem solved results in new questions," Streinu's work opens the door on a wide variety of new and provocative questions.