Paper by Erik D. Demaine

Reference:

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides, “On Reconfiguring Tree Linkages: Trees can Lock”, Technical Report SOCS-00.7, School of Computer Science, McGill University, September 2000.

BibTeX

@TechReport{LockedTreeTR,
  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},
  TITLE         = {On Reconfiguring Tree Linkages: Trees can Lock},
  INSTITUTION   = {School of Computer Science, McGill University},
  INSTITUTIONURL = {http://www.cs.mcgill.ca/},
  NUMBER        = {SOCS-00.7},
  NUMBERURL     = {http://www.cs.mcgill.ca/research/reports/00/SOCS.00.7.ps.gz},
  MONTH         = {September},
  YEAR          = {2000},

  length        = {16 pages},
  papers        = {LockedTreeDAM; CCCG98c},
  comments      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.CG/9910024">
                   arXiv:cs.CG/9910024</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.},
  webpages      = {linkage}
}

Abstract:

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

Comments:

This paper is also available as arXiv:cs.CG/9910024 of the Computing Research Repository (CoRR).

Length:

The paper is 16 pages.

Availability:

The paper is available in PostScript (412k) and gzipped PostScript (88k).

See information on file formats.

[Google Scholar search]

Related papers:

LockedTreeDAM (A Note on Reconfiguring Tree Linkages: Trees can Lock)

CCCG98c (On Reconfiguring Tree Linkages: Trees can Lock)

Related webpages:

Carpenter's Rule Theorem