A Note 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-00100889, version 1

A Note 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^, 1, Steve Robbins^d^, 3, Ileana Streinu^c^, 1, Godfried Toussaint^d^, 3, Sue Whitesides^d^, 3

Discrete Applied Mathematics 117, 1-3 (2002) 293-297

Résumé : It has recently been shown that any polygonal chain in the plane can be reconfigured to lie on a straight line, and any polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two configurations that are not connected by a 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-00100889, version 1
http://hal.inria.fr/inria-00100889
oai:hal.inria.fr:inria-00100889
Contributeur : Sylvain Lazard <>
Soumis le : Mardi 26 Septembre 2006, 14:52:42
Dernière modification le : Mardi 22 Décembre 2009, 15:17:09

Voir la fiche détaillée

Documents associés

DOI : 10.1016/S0166-218X(01)00229-3

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="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00100889"><analytic>
<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>
<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>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>
<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>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="a">A Note on Reconfiguring Tree Linkages: Trees can Lock</title></analytic><monogr><title level="j" type="main">Discrete Applied Mathematics</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">2002-00-00</biblScope><biblScope type="vol">117</biblScope><biblScope type="issue">1-3</biblScope><biblScope type="pp">293-297</biblScope></imprint></monogr><idno type="doi">10.1016/S0166-218X(01)00229-3</idno><idno type="HALid">http://hal.inria.fr/inria-00100889</idno></biblStruct>
</listBibl>
</listBibl>