On the complexity of the linkage reconfiguration problem
Helmut Guido Alt, Christian Knauer, Günter Rote, Sue H. Whitesides · Contemporary mathematics - American Mathematical Society · 2004
We consider the problem of reconfiguring 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 configurations can be reconfigured to a straight position. We show that deciding reconfigurability for trees in two dimensions and for chains in three dimensions is PSPACE-complete.