Helmut Alt, Christian Knauer, Günter Rote, and Sue Whitesides:
1. The complexity of (un)folding
In: Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 164–170. doi:10.1145/777792.777818
2. On the complexity of the linkage reconfiguration problem
In: "Towards a Theory of Geometric Graphs". Editor: János
Pach,
American Mathematical Society, 2004, Contemporary Mathematics,
Vol. 342,
pp. 1–13.
Abstract
We consider the problem of reconguring a linkage of rigid straight
segments
from a given start to a given target position with a continuous
nonintersecting motion. The problem is nontrivial even for trees in two
dimensions since it is known that not all congurations can be
recongured to
a straight position. We show that deciding recongurability for trees in
two
dimensions and for chains in three dimensions is PSPACE-complete.
Last update: January 12, 2007.