A note on reconfiguring tree linkages: Trees can lock

Therese Biedl; Erik Demaine; Martin Demaine; Sylvain Lazard; Anna Lubiw; Joseph O'Rourke; Steve Robbins; Ileana Streinu; Godfried Toussaint; Sue Whitesides

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

A note on reconfiguring tree linkages: Trees can lock

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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(Ω(N)) equivalence classes of configurations.

Original language	English (US)
Pages (from-to)	293-297
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	117
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(01)00229-3
State	Published - Mar 15 2002

Keywords

Distance geometry
Graph embedding
Linkage reconfiguration
Motion planning
Tree embedding

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

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

Cite this

@article{61e1159682d54be7bbb52551079526e7,

title = "A note on reconfiguring tree linkages: Trees can lock",

abstract = "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(Ω(N)) equivalence classes of configurations.",

keywords = "Distance geometry, Graph embedding, Linkage reconfiguration, Motion planning, Tree embedding",

author = "Therese Biedl and Erik Demaine and Martin Demaine and Sylvain Lazard and Anna Lubiw and Joseph O'Rourke and Steve Robbins and Ileana Streinu and Godfried Toussaint and Sue Whitesides",

note = "Funding Information: Research partially supported by Fonds pour la Formation de Chercheurs et l'Aide {\`a} la Recherche, Qu{\'e}bec (SW,SR), the Natural Sciences and Engineering Research Council, Canada (AL,GT,SW,ED) and the National Science Foundation, USA (JO,IS). ",

year = "2002",

month = mar,

day = "15",

doi = "10.1016/S0166-218X(01)00229-3",

language = "English (US)",

volume = "117",

pages = "293--297",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - A note on reconfiguring tree linkages

T2 - Trees can lock

AU - Biedl, Therese

AU - Demaine, Erik

AU - Demaine, Martin

AU - Lazard, Sylvain

AU - Lubiw, Anna

AU - O'Rourke, Joseph

AU - Robbins, Steve

AU - Streinu, Ileana

AU - Toussaint, Godfried

AU - Whitesides, Sue

N1 - Funding Information: Research partially supported by Fonds pour la Formation de Chercheurs et l'Aide à la Recherche, Québec (SW,SR), the Natural Sciences and Engineering Research Council, Canada (AL,GT,SW,ED) and the National Science Foundation, USA (JO,IS).

PY - 2002/3/15

Y1 - 2002/3/15

N2 - 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(Ω(N)) equivalence classes of configurations.

AB - 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(Ω(N)) equivalence classes of configurations.

KW - Distance geometry

KW - Graph embedding

KW - Linkage reconfiguration

KW - Motion planning

KW - Tree embedding

UR - http://www.scopus.com/inward/record.url?scp=84867972776&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867972776&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(01)00229-3

DO - 10.1016/S0166-218X(01)00229-3

M3 - Article

AN - SCOPUS:84867972776

SN - 0166-218X

VL - 117

SP - 293

EP - 297

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

A note on reconfiguring tree linkages: Trees can lock

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this