Carpenter's Rule Theorem

Robert Connelly, Erik Demaine, Günter Rote

In 2000, we solved the following three problems positively:

Furthermore:

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

Animations illustrate three different algorithms for unfolding and refolding polygonal chains:

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

The main paper appears in the journal Discrete & Computational Geometry. The technical report includes an additional appendix which strengthens the result but is highly technical. Extended abstracts also appear in the Proceedings of the 41st Annual Symposium on Foundations of Computer Science (11 pages, November 2000) and Proceedings of the 16th European Workshop on Computational Geometry (4 pages, March 2000). Papers about this work:

History

These problems were introduced and circulated independently by several researchers, including Stephen Schanuel in the early 1970s, Ulf Grenander in 1986–1989, William Lenhart and Sue Whitesides in March 1991, and Joseph Mitchell in December 1992. See our paper for details.

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.

Last updated January 22, 2012 by Erik Demaine.