Paper by Erik D. Demaine

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”, in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

It is an open problem to determine whether a polygonal chain can be “straightened” in the plane if its links are not allowed to cross. This problem has been raised independently by several researchers, including J. Mitchell, and W. Lenhart and S. Whitesides [LW95]. In this paper, we propose a related question: whether a tree linkage can always be “straightened” in the plane, without allowing its links to cross. We prove that this is not always possible.

This paper is also available from the electronic proceedings as

The paper is 11 pages and the talk is 20 minutes.

The paper is available in PostScript (467k).
See information on file formats.
[Google Scholar search]

Related papers:
LockedTreeDAM (A Note on Reconfiguring Tree Linkages: Trees can Lock)
LockedTreeTR (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 27, 2017 by Erik Demaine.