Pseudotriangulations, polytopes, and how to expand linkages

ABSTRACT

I will survey some recent results about unfolding of linkages and connections to pseudotriangulations.

REFERENCES

• 1: B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations, Algorithmica 12 (1994), 54--68.
• 2: R. Connelly. Rigidity. In Handbook of Convex Geometry, vol. A (P. M. Gruber and J. M. Wills, eds.), North-Holland, Amsterdam, 1993, pp. 223--271.
• 3: R. Connelly , E. D. Demaine , G. Rote, Straightening polygonal arcs and convexifying polygonal cycles, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.432, November 12-14, 2000
• 4: Erik D. Demaine, Folding and Unfolding Linkages, Paper, and Polyhedra, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.113-124, November 22-25, 2000
• 5: J. Graver, B. Servatius, and H. Servatius. Combinatorial rigidity. American Mathematical Society, Providence, 1993.
• 6: David G. Kirkpatrick , Bettina Speckmann, Separation Sensitive Kinetic Separation Structures for Convex Polygons, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.222-236, November 22-25, 2000
• 7: M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-\allowbreak triangulations. Discrete & Computational Geometry 16 (1996), 419--453.
• 8: Michel Pocchiola , Gert Vegter, Pseudo-triangulations: theory and applications, Proceedings of the twelfth annual symposium on Computational geometry, p.291-300, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237398]
• 9: G. Rote, F. Santos, and I. Streinu. Expansive motions and the polytope of pointed pseudo-\allowbreak triangulations. Submitted for publication.
• 10: B. Speckmann and C. D. Tóth. Vertex pi-guards in simple polygons. Presented at the 18th European Workshop on Computational Geometry, April 10--12, 2002, Warszawa, Poland. Submitted for publication.
• 11: 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
• 12: G. Ziegler. Lectures on Polytopes (2nd ed.), Springer-Verlag, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Kinematics and dynamics

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:
motion planning, polytopes, pseudotriangulations