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.
I will add links to related pages in the near future. Also, I am trying to write a small history on the problem. If you know anyone not listed below who has worked on the problem, please let me know.
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:
Mark Overmars has designed an excellent
Motion Planning
Game. In particular, the level on robot arms shows how intricate motions
of polygonal arcs can be when there are obstacles.
These problems were introduced and circulated independently by several researchers, including William Lenhart and Sue Whitesides in 1991, and Joseph Mitchell in 1992.
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 Bob, in November 1999.
We thank the people mentioned above for their work, feedback, and insight on the problem. We also thank Boris Aronov, Jeff Erickson, Jacob Goodman, Victor Klee, and Walter Whiteley for helpful discussions.