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.''
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2001, 26 (3), pp.269-281. 〈10.1007/s00454-001-0038-7〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00100521
Contributeur : Sylvain Lazard <>
Soumis le : mardi 26 septembre 2006 - 14:46:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Lien texte intégral

Identifiants

Collections

Citation

Thérèse Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, et al.. Locked and Unlocked Polygonal Chains in Three Dimensions. Discrete and Computational Geometry, Springer Verlag, 2001, 26 (3), pp.269-281. 〈10.1007/s00454-001-0038-7〉. 〈inria-00100521〉

Partager

Métriques

Consultations de la notice

159