Straightening Polygonal Arcs and Convexifying Polygonal Cycles

Robert Connelly
Department of Mathematics
Cornell University
Ithaca, NY 14853, U.S.A.
email: connelly@math.cornell.edu Erik D. Demaine
MIT Laboratory for Computer Science 200 Technology Square Cambridge, MA 02139, USA email: edemaine@mit.edu
Günter Rote
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: rote@inf.fu-berlin.de

Report B 02-02
February 2002

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. In particular, this result settles the well-studied carpenter's rule conjecture.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-01-01.ps.gz