On Reconfiguring Tree Linkages: Trees can lock

Thérèse Biedl; Erik Demaine; Martin Demaine; Sylvain Lazard; Anna Lubiw; Joseph O'Rourke; Steve Robbins; Ileana Streinu; Godfried Toussaint; Sue Whitesides

inria-00099329, version 1

On Reconfiguring Tree Linkages: Trees can lock

Thérèse Biedl^a^, 1, Erik Demaine^a^, 1, Martin Demaine^a^, 1, Sylvain Lazard^b^, 2, Anna Lubiw^a^, 1, Joseph O'Rourke^c, Steve Robbins^d^, 3, Ileana Streinu^c, Godfried Toussaint^d^, 3, Sue Whitesides^d^, 3

N° A00-R-388 || biedl00a (2000)

Résumé : 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.

a – UNIVERSITY OF WATERLOO
b – INRIA
c – SMITH COLLEGE
d – MCGILL UNIVERSITY
1 : Department of Computer Science [Calgary] (CPSC)
University of Calgary
2 : ISA (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : School of computer science [Ottawa] (SCS)
Carleton University

inria-00099329, version 1
http://hal.inria.fr/inria-00099329
oai:hal.inria.fr:inria-00099329
Contributeur : Sylvain Lazard <>
Soumis le : Mardi 26 Septembre 2006, 08:52:55
Dernière modification le : Jeudi 3 Mai 2007, 14:12:44

Voir la fiche détaillée

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00099329"><monogr>
<author><persName><forename>Thérèse</forename><surname>Biedl</surname></persName>
<affiliation>
<orgName type="laboratory">CPSC</orgName>
<orgName type="team">Department of Computer Science [Calgary]</orgName>
<country>CA</country>
<orgName type="institution">University of Calgary</orgName>
</affiliation>
</author>
<author><persName><forename>Erik</forename><surname>Demaine</surname></persName>
<affiliation>
<orgName type="laboratory">CPSC</orgName>
<orgName type="team">Department of Computer Science [Calgary]</orgName>
<country>CA</country>
<orgName type="institution">University of Calgary</orgName>
</affiliation>
</author>
<author><persName><forename>Martin</forename><surname>Demaine</surname></persName>
<affiliation>
<orgName type="laboratory">CPSC</orgName>
<orgName type="team">Department of Computer Science [Calgary]</orgName>
<country>CA</country>
<orgName type="institution">University of Calgary</orgName>
</affiliation>
</author>
<author><persName><forename>Sylvain</forename><surname>Lazard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ISA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Anna</forename><surname>Lubiw</surname></persName>
<affiliation>
<orgName type="laboratory">CPSC</orgName>
<orgName type="team">Department of Computer Science [Calgary]</orgName>
<country>CA</country>
<orgName type="institution">University of Calgary</orgName>
</affiliation>
</author>
<author><persName><forename>Joseph</forename><surname>O'Rourke</surname></persName></author>
<author><persName><forename>Steve</forename><surname>Robbins</surname></persName>
<affiliation>
<orgName type="laboratory">SCS</orgName>
<orgName type="team">School of computer science [Ottawa]</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<author><persName><forename>Ileana</forename><surname>Streinu</surname></persName></author>
<author><persName><forename>Godfried</forename><surname>Toussaint</surname></persName>
<affiliation>
<orgName type="laboratory">SCS</orgName>
<orgName type="team">School of computer science [Ottawa]</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<author><persName><forename>Sue</forename><surname>Whitesides</surname></persName>
<affiliation>
<orgName type="laboratory">SCS</orgName>
<orgName type="team">School of computer science [Ottawa]</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<title type="main" level="m">On Reconfiguring Tree Linkages: Trees can lock</title><title type="main" level="m">On Reconfiguring Tree Linkages: Trees can lock</title><imprint><biblScope type="publicationDate">2000-00-00</biblScope><biblScope type="pp">16 p</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00099329</idno></biblStruct>
</listBibl>
</listBibl>