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.


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.

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: January 12, 2007.