In 2000, we solved the following three problems positively:
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.
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. |
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.