Carpenter's Rule Theorem

Robert Connelly, Erik Demaine, Günter Rote

In 2000, we solved the following three problems positively:

• Convexifying polygons:
  Given a simple polygon in the plane (whose edges are considered rigid bars and whose vertices are considered hinges), is there a continuous motion of the polygon that preserves the lengths of the edges and never causes edges to cross, and results in the polygon being convex?

• Carpenter's rule conjecture:
  Given an open polygonal chain (also called a polygonal path or polygonal arc) in the plane, is there a continuous motion with the same properties that results in the arc becoming straight?

• A generalization:
  Given a collection of polygonal arcs and simple polygons in the plane, none of which intersect each other, such that no polygon contains another arc or polygon, there is a motion that preserves all of the edge lengths and never crosses any edges, and results in the arcs becoming straight and the polygons being convex.

• If desired, an arc or polygon can be contained inside another polygon, but this arc or polygon cannot be guaranteed to be straightened or convexified (as this is not always possible).
• The motion is expansive: the distance between every pair of vertices only increases.
• The motion is piecewise-differentiable.
• The motion preserves any symmetries present in the initial configuration.
• The configuration space of a polygonal arc or simple polygon, modulo isometries, is contractible.

The proof ends up being quite simple with the right ideas (in particular the notion of increasing pairwise distances) and tools (in particular the theory of rigidity) in hand.

Animations

Original Algorithm Illustrations of the original algorithm implicit in the Connelly, Demaine, Rote paper.

Energy Unfolding Algorithm Illustrations of a more recent and efficient algorithm for unfolding chains, described in a SoCG 2004 paper.

Energy Refolding Algorithm Illustrations of algorithms for folding polygons directly from one configuration to another, described in a SoCG 2006 paper and a SIGGRAPH 2004 technical sketch.

Papers

• Ivars Peterson's Science News article “Unlocking Puzzling Polygons” (September 23, 2000, volume 158, number 13, pages 200-201) is an overview of our results written for a general audience.

• Joseph O'Rourke's “Computational Geometry Column 39” (July 2000) is a 4-page overview of our result and Ileana Streinu's related result.

History

A fairly large group of people was involved in trying to construct and prove or disprove “locked” examples (counterexamples to the above theorems) at various times over the past few years. Typically, someone in the group would distribute an example that s/he constructed or was given by a colleague. We would try various motions that did not work, and we would often try proving that the example was locked because it appeared so! For some examples, it took several months before we found an opening motion.

My main interest in this research was initiated at the International Workshop on Wrapping and Folding organized by Anna Lubiw and Sue Whitesides at the Bellairs Research Institute of McGill University in February 1998. At this workshop, a bond between several linkage openers began: Therese Biedl, Martin Demaine, Hazel Everett, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steven Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides, and myself. The group of "linkage openers" metioned above grew to include Robert Connelly, Sándor Fekete, Joseph Mitchell, and Günter Rote. Other people working on the problem include Eric Babson, Prosenjit Bose, Christopher Croke, Branko Grünbaum, Michael Kaufmann, Paul Kearney, William Lenhart, Giuseppe Liotta, John Milnor, János Pach, Irena Pashchenko, Octavia Petrovici, Richard Pollack, Heiko Schröder, Michael Soss, Einar Steingrimsson, and Jorge Urrutia. One of the key meetings that started this paper is the Monte Verità Conference on Discrete and Computational Geometry in Ascona, Switzerland, organized by Jacob Goodman, Richard Pollack, and Emo Welzl in June 1999. In particular, Bob, Günter, and I first met at this conference. Our work continued at the 4th Geometry Festival, an international workshop on Discrete Geometry and Rigidity, in Budapest, Hungary, organized by András Bezdek, Károly Bezdek, Károly Böröczky, and Robert Connelly, in November 1999.