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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)293-297
Number of pages5
JournalDiscrete Applied Mathematics
Volume117
Issue number1-3
DOIs
StatePublished - Mar 15 2002

Keywords

  • Distance geometry
  • Graph embedding
  • Linkage reconfiguration
  • Motion planning
  • Tree embedding

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A note on reconfiguring tree linkages: Trees can lock'. Together they form a unique fingerprint.

Cite this