Robert Connelly, Erik D. Demaine, and Günter Rote:
Straightening polygonal arcs and convexifying polygonal cycles
- 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.
- In: Proceedings of the 41st Annual Symposium on Foundations
Science, Redondo Beach, California, (FOCS), November 12–14, 2000. IEEE
Society Press, 2000, pp. 432–442. doi:10.1109/SFCS.2000.892131
- Discrete and Computational Geometry 30
(2003), 205–239. doi:10.1007/s00454-003-0006-7
is a more detailed version of 2.)
report B02-02, Revised version, February 2002, 49 pages. (This
is a version of 3 expanded by an appendix with
Consider a planar linkage, consisting of disjoint polygonal arcs and
of rigid bars joined at incident endpoints (polygonal chains), with the
property that no cycle surrounds another arc or cycle. We prove
the linkage can be continuously moved so that the arcs become straight,
the cycles become convex, and no bars cross while preserving the bar
Furthermore, our motion is piecewise-differentiable, does not decrease
the distance between any pair of vertices, and preserves any symmetry
in the initial configuration. Furthermore, our motion strictly
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.
Last update: October 13, 2003.