| On Reconfiguring Tree Linkages: Trees can Lock (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a tree linkage can always be "straightened" in the plane, without allowing its links to cross. We prove that this is not always possible. Indeed, we prove that an N-link tree linkage can have 2 \Omega\Gamma N) equivalence classes of configurations. Key words: Motion Planning, Linkage Reconfiguration, Graph Embedding, Tree Embedding, Distance Geometry. Research partially supported by Fonds pour la Formation de Chercheurs et l'Aide `a la Recherche, Qu'ebec (SW,SR), the Natural Sciences and Engineering Research Council, Canada (AL,GT,SW,ED) and the National Science Foundation, USA (JO). Preprint submitted to Elsevier Preprint 17 January 2000 1 Introduction Consider a graph, each edge labelled with a positive number. Such a graph may be thought of as a collection of distance constraints between pair... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||