Skip to Main content Skip to Navigation
Conference papers

Locked and Unlocked Polygonal Chains in 3D

Abstract : In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be {\em straightened\/} if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is {\em convexification\/}: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called {\em locked}. While there are open chains in 3D that are locked, we show that if an open chain has a simple orthogonal projection onto some plane, it can be straightened. For closed chains, we show that there are unknotted but locked closed chains, and we provide an algorithm for convexifying a planar simple polygon in 3D with a polynomial number of moves.
Document type :
Conference papers
Complete list of metadatas
Contributor : Sylvain Lazard <>
Submitted on : Tuesday, December 15, 2009 - 3:19:44 PM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM
Document(s) archivé(s) le : Monday, April 5, 2010 - 11:51:47 PM


  • HAL Id : inria-00098772, version 1


Therese C. Biedl, Erik D. Demaine, Mark Demaine, Sylvain Lazard, Anna Lubiw, et al.. Locked and Unlocked Polygonal Chains in 3D. 10th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'99, Jan 1999, Baltimore, Maryland, United States. pp.866-867. ⟨inria-00098772v1⟩



Record views


Files downloads