Locked and Unlocked Polygonal Chains in Three Dimensions

Thérèse Biedl 1 Erik Demaine 1 Martin Demaine 1 Sylvain Lazard 2 Anna Lubiw 1 Joseph O'Rourke 3 M. Overmars 4 Steve Robbins 5 Ileana Streinu 3 Godfried Toussaint 5 Sue Whitesides 5
1 University of Waterloo [Waterloo]
2 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Department of Computer Science
4 UTRECHT UNIVERSITY - Departments of Psychonomics, and Media and Communication, Utrecht University
5 McGill University
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.''
Mots-clés : mécanismes articulés linkages
Type de document :
Communication dans un congrès
Symposium on Discrete Algorithms - SODA'99, Jan 1999, Baltimore, United States. ACM-SIAM, pp.866 - 867, 1999, 〈http://delivery.acm.org/10.1145/320000/314977/p866-biedl.pdf?key1=314977&key2=9974440921&coll=DL&dl=ACM&CFID=115354797&CFTOKEN=35617922〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00098772
Contributeur : Sylvain Lazard <>
Soumis le : vendredi 19 novembre 2010 - 14:12:10
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : dimanche 20 février 2011 - 02:25:17

Fichier

99-R-227.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00098772, version 2

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

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. ACM-SIAM, pp.866 - 867, 1999, 〈http://delivery.acm.org/10.1145/320000/314977/p866-biedl.pdf?key1=314977&key2=9974440921&coll=DL&dl=ACM&CFID=115354797&CFTOKEN=35617922〉. 〈inria-00098772v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

154

Téléchargements de fichiers

95

Contact


archive-ouverte@inria.fr