Robert Connelly, Erik D. Demaine, and Günter Rote:

Straightening polygonal arcs and convexifying polygonal cycles

  1. Every polygon can be untangled
    In: Proceedings of the 16th European Workshop on Computational Geometry, Ben-Gurion University of the Negev, Israel, January 2000, pp. 62–65.
  2. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, California, (FOCS), November 12–14, 2000. IEEE Computer Society Press, 2000, pp. 432–442. doi:10.1109/SFCS.2000.892131
  3. Discrete and Computational Geometry 30 (2003), 205–239. doi:10.1007/s00454-003-0006-7 (This is a more detailed version of 2.)
  4. Technical report B02-02, Revised version, February 2002, 49 pages. (This is a version of 3 expanded by an appendix with supplementary proofs.)


Consider a planar linkage, consisting of disjoint polygonal arcs and cycles of rigid bars joined at incident endpoints (polygonal chains), with the property that no cycle surrounds another arc or cycle.  We prove that the linkage can be continuously moved so that the arcs become straight, the cycles become convex, and no bars cross while preserving the bar lengths.  Furthermore, our motion is piecewise-differentiable, does not decrease the distance between any pair of vertices, and preserves any symmetry present in the initial configuration. Furthermore, our motion strictly increases the distance between every pair of vertices that are not connected by a straight subchain of bars and are not on a common convex chain.

See also Erik Demaine's linkage page for information about related problems.

  pdf file   free PDF view@Springer
other papers about this subject
Last update: October 13, 2003.