1999/10/31 by Therese Biedl, Thérèse Biedl, Erik D. Demaine +22
Computer Science · Engineering · #Advanced Materials and Mechanics #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F2.2 #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Robotic Locomotion and Control #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/9910024
16 pages, 6 figures Introduction reworked and references added, as the main open problem was recently closed
openalex publication_date 1999/11/01 · arxiv created 2000/09/29 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.