HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On Reconfiguring Tree Linkages: Trees can lock

Abstract : 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^{\Omega(N)}$ equivalence classes of configurations.
Document type :
Complete list of metadata

Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:52:55 AM
Last modification on : Friday, February 4, 2022 - 3:17:02 AM


  • HAL Id : inria-00099329, version 1



Thérèse Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, et al.. On Reconfiguring Tree Linkages: Trees can lock. [Intern report] A00-R-388 || biedl00a, 2000, 16 p. ⟨inria-00099329⟩



Record views