On Reconfiguring Tree Linkages: Trees can Lock

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an $N$-link tree can have $2^{Ω(N)}$ equivalence classes of configurations.
16 pages, 6 figures Introduction reworked and references added, as the main open problem was recently closed

Keywords

Computational Geometry, Discrete Mathematics, F2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/33322

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/9910024
 http://arxiv.org/abs/cs/9910024

Collections

arXiv