Locked and unlocked polygonal chains in three dimensions

T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O (n) basic "moves.".

Original languageEnglish (US)
Pages (from-to)269-281
Number of pages13
JournalDiscrete and Computational Geometry
Volume26
Issue number3
DOIs
StatePublished - Oct 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Locked and unlocked polygonal chains in three dimensions'. Together they form a unique fingerprint.

Cite this