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.
- 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
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated March 12, 2024 by
Erik Demaine.