Locked and Unlocked Polygonal Chains in Three Dimensions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

Locked and Unlocked Polygonal Chains in Three Dimensions

Résumé

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

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
99-R-227.pdf (144.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00098772 , version 1 (15-12-2009)
inria-00098772 , version 2 (19-11-2010)

Identifiants

  • HAL Id : inria-00098772 , version 2

Citer

Thérèse Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, et al.. Locked and Unlocked Polygonal Chains in Three Dimensions. Symposium on Discrete Algorithms - SODA'99, Jan 1999, Baltimore, United States. pp.866 - 867. ⟨inria-00098772v2⟩
72 Consultations
217 Téléchargements

Partager

Gmail Facebook X LinkedIn More