Computational geometry column 43

ABSTRACT

The concept of pointed pseudo-triangulations is defined and a few of its applications described.

REFERENCES

• 1: {BKPS01} H. Brönnimann, L. Kettner, M. Pocchiola, and J. Snoeyink. Counting and enumerating pseudo-triangulations with the greedy flip algorithm. September 2001. http://www.cs.unc.edu/Research/compgeom/pseudoT/.
• 2: 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
• 3: {CEG+94} B. Chazelle, H. Edelsbrunner, M. Grigni, Leonidas J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12:54-68, 1994.
• 4: {KKM+01} L. Kettner, D. Kirkpatrick, A. Mantler, J. Snoeyink, B. Speckmann, and F. Takeuchi. Tight degree bounds for pseudo-triangulations of points. Comput. Geom. Th. Appl., 2001. To appear. Revision of abstract by L. Kettner, D. Kirkpatrick, and B. Speckmann, in Proc. 13th Canad. Conf. Comput. Geom., pp. 117-120, 2001.
• 5: David Kirkpatrick , Jack Snoeyink , Bettina Speckmann, Kinetic collision detection for simple polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.322-330, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336219]
• 6: Joseph O'Rourke, Computational geometry column 39, ACM SIGACT News, v.31 n.3, p.47-49, Sept. 2000 [doi>10.1145/356458.356461]
• 7: Michel Pocchiola , Gert Vegter, Computing the visibility graph via pseudo-triangulations, Proceedings of the eleventh annual symposium on Computational geometry, p.248-257, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220306]
• 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: {RRSS01} D. Randall, G. Rote, F. Santos, and J. Snoeyink. Counting triangulations and pseudotriangulations of wheels. In Proc. 13th Canad. Conf. Comp. Geom., pages 149-152, 2001.
• 10: {RSS01} G. Rote, F. Santos, and I. Streinu. Expansive motions and the polytope of pointed pseudo-triangulations. http://cs.smith.edu/~streinu/Papers/polytope.ps, September 2001.
• 11: {ST01} B. Speckmann and C. D. Tóth. Vertex π-guards in simple polygons. December 2001.
• 12: 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
• 13: {Urr00} J. Urrutia. Art gallery and illumination problems. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 973-1027. North-Holland, 2000.