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

doi:10.1007/s00454-001-0038-7

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

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	269-281
Number of pages	13
Journal	Discrete and Computational Geometry
Volume	26
Issue number	3
DOIs	https://doi.org/10.1007/s00454-001-0038-7
State	Published - Oct 2001

ASJC Scopus subject areas

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

Access to Document

10.1007/s00454-001-0038-7

Cite this

@article{dbdea663a1074d0886997a35c846619c,

title = "Locked and unlocked polygonal chains in three dimensions",

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.{"}.",

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

year = "2001",

month = oct,

doi = "10.1007/s00454-001-0038-7",

language = "English (US)",

volume = "26",

pages = "269--281",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Locked and unlocked polygonal chains in three dimensions

AU - Biedl, T.

AU - Demaine, E.

AU - Demaine, M.

AU - Lazard, S.

AU - Lubiw, A.

AU - O'Rourke, J.

AU - Overmars, M.

AU - Robbins, S.

AU - Streinu, I.

AU - Toussaint, G.

AU - Whitesides, S.

PY - 2001/10

Y1 - 2001/10

N2 - 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.".

AB - 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.".

UR - http://www.scopus.com/inward/record.url?scp=0035601782&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035601782&partnerID=8YFLogxK

U2 - 10.1007/s00454-001-0038-7

DO - 10.1007/s00454-001-0038-7

M3 - Article

AN - SCOPUS:0035601782

SN - 0179-5376

VL - 26

SP - 269

EP - 281

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Locked and unlocked polygonal chains in three dimensions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this