Paper by Erik D. Demaine

Reference:

T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides, “Locked and Unlocked Polygonal Chains in Three Dimensions”, Discrete & Computational Geometry, volume 26, number 3, October 2001, pages 269–281.

BibTeX

@Article{3DChains_DCG2001,
  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},
  TITLE         = {Locked and Unlocked Polygonal Chains in Three Dimensions},
  JOURNAL       = {Discrete \& Computational Geometry},
  JOURNALURL    = {http://link.springer.de/link/service/journals/00454/},
  VOLUME        = 26,
  NUMBER        = 3,
  PAGES         = {269--281},
  MONTH         = {October},
  YEAR          = 2001,

  LENGTH        = {29 pages},
  PAPERS        = {3DChainsTR; SODA99c},
  replaces      = {SODA99c},
  doi           = {https://dx.doi.org/10.1007/s00454-001-0038-7},
  dblp          = {https://dblp.org/rec/journals/dcg/BiedlDDLLOORSTW01},
  COMMENTS      = {This paper is also available from
                   <A HREF="http://dx.doi.org/10.1007/s00454-001-0038-7">SpringerLink</A>.}
}

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.”

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 29 pages.

Availability:

The paper is available in PostScript (491k) and gzipped PostScript (166k).

See information on file formats.

[Google Scholar search]

Related papers:

3DChainsTR (Locked and Unlocked Polygonal Chains in 3D)

SODA99c (Locked and Unlocked Polygonal Chains in 3D)