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
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
- Discrete and Computational Geometry 30
(2003), 205–239. doi:10.1007/s00454-003-0006-7
(This
is a more detailed version of 2.)
- Technical
report B02-02, Revised version, February 2002, 49 pages. (This
is a version of 3 expanded by an appendix with
supplementary
proofs.)
Abstract
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.
Last update: October 13, 2003.