On Reconfiguring Tree Linkages: Trees can Lock

Simple item page
dc.creatorBiedl, Therese
dc.creatorDemaine, Erik
dc.creatorDemaine, Martin
dc.creatorLazard, Sylvain
dc.creatorLubiw, Anna
dc.creatorO'Rourke, Joseph
dc.creatorRobbins, Steve
dc.creatorStreinu, Ileana
dc.creatorToussaint, Godfried
dc.creatorWhitesides, Sue
dc.date1999-11-01
dc.date2000-09-29
dc.date.accessioned2026-07-07T03:24:26Z
dc.date.available2026-07-07T03:24:26Z
dc.descriptionIt 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.
dc.description16 pages, 6 figures Introduction reworked and references added, as the main open problem was recently closed
dc.identifierhttps://arxiv.org/abs/cs/9910024
dc.identifierhttp://arxiv.org/abs/cs/9910024
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33322
dc.subjectComputational Geometry
dc.subjectDiscrete Mathematics
dc.subjectF2.2
dc.titleOn Reconfiguring Tree Linkages: Trees can Lock
dc.typetext

Files

Collections

arXiv