A Note on Reconfiguring Tree Linkages: Trees can Lock

Thérèse Biedl 1 Erik Demaine 1 Martin Demaine 1 Sylvain Lazard 2 Anna Lubiw 1 Joseph O'Rourke 1 Steve Robbins 3 Ileana Streinu 1 Godfried Toussaint 3 Sue Whitesides 3
1 CPSC - Department of Computer Science [Calgary]
2 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 SCS - School of computer science [Ottawa]
Abstract : It has recently been shown that any polygonal chain in the plane can be reconfigured to lie on a straight line, and any polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two configurations that are not connected by a motion. Indeed, we prove that an $N$-link tree can have $2^{Omega(N)}$ equivalence classes of configurations.
Keywords : distance geometry. motion planning linkage reconfiguration graph embedding tree embedding reconfiguration de mécanismes articulés planification de trajectoires
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2002, 117 (1-3), pp.293-297. 〈10.1016/S0166-218X(01)00229-3〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00100889
Contributeur : Sylvain Lazard <>
Soumis le : mardi 26 septembre 2006 - 14:52:42
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Thérèse Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, et al.. A Note on Reconfiguring Tree Linkages: Trees can Lock. Discrete Applied Mathematics, Elsevier, 2002, 117 (1-3), pp.293-297. 〈10.1016/S0166-218X(01)00229-3〉. 〈inria-00100889〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

156

Contact


archive-ouverte@inria.fr