The complexity of (un)folding

ABSTRACT

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.

REFERENCES

• 1: T. C. Biedl, E. D. Demaine, M. L. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. H. Overmars, S. Robbins, I. Streinu, G. T. Toussaint, and S. Whitesides. Locked and unlocked polygonal chains in three dimensions. Discrete and Computational Geometry, 26:269--281, October 2001.
• 2: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 3: J. Cantarella and H. Johnston. Nontrivial embeddings of polygonal intervals and unknots in 3-space. Journal of Knot Theory and its Ramifications, 7:1027--1039, 1998.
• 4: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 5: R. Connelly, E. D. Demaine, and G. Rote. Straightening polygonal arcs and convexifying polygonal cycles. Discrete and Computational Geometry, 2003. To appear.
• 6: Erik D. Demaine , Stefan Langerman , Joseph O'Rourke , Jack Snoeyink, Interlocked open linkages with few joints, Proceedings of the eighteenth annual symposium on Computational geometry, p.189-198, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513424]
• 7: Deborah A. Joseph , W. Harry Plantings, On the complexity of reachability and motion planning questions (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.62-66, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323242]
• 8: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• 9: J. T. Schwartz and M. Sharir. On the "piano movers" problem II: general techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math,, 4:298--351, 1983.
• 10: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
PSPACE-completeness, computational geometry, linkage reconfiguration