Construction of Pseudo-triangulation by Incremental Insertion

1. Aichholzer, O., Aurenhammer, F., Krasser, H., Speckmann, B.: Convexity minimizes pseudo-triangulations. In: Proceedings of the 14th Canadian Conference on Computational Geometry, pp. 158–162 (2002)

   Google Scholar 

2. Aichholzer, O., Rote, G., Speckmann, B., Streinu, I.: The Zigzag Path of a Pseudo-Triangulation. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 377–388. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

3. Aichholzer, O., Aurenhammer, F., Krasser, H., Brass, P.: Pseudo-triangulations from surfaces and novel type of edge flip. SIAM Journal on Computing 32, 1621–1653 (2003)

   Article  MATH  MathSciNet  Google Scholar 

4. Brönnimann, H., Kettner, L., Pocchiola, M., Snoeyink, J.: Counting and enumerating pseudo-triangulations with greedy flip algorithm. SIAM Journal on Computing 36, 721–739 (2007)

   Article  MATH  Google Scholar 

5. Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12, 54–68 (1994)

   Article  MATH  MathSciNet  Google Scholar 

6. Kettner, L., Kirkpatrick, D., Mantler, A., Snoeyink, J., Speckmann, B., Takeuchi, F.: Tight degree bounds for pseudo-triangulations of points. Computational Geometry - Theory and Applications 25(1-2), 3–12 (2003)

   Article  MATH  MathSciNet  Google Scholar 

7. Kirkpatrick, D., Snoeyink, J., Speckmann, B.: Kinetic collision detection for simple polygons. In: Proceedings of the 16th ACM Symposium on Computational Geometry, pp. 322–330 (2000)

   Google Scholar 

8. Kirkpatrick, D., Speckmann, B.: Separation sensitive kinetic separation structures for convex polygons. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 2000. LNCS, vol. 2098, pp. 222–236. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

9. Kolingerová, I., Trčka, J., Žalik, B.: The stochastic walk algorithms for point location in pseudo-triangulations (2011) (manuscript)

   Google Scholar 

10. Műcke, E.P., Saias, I., Zhu, B.: Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. In: Proceedings of the 12th Annual Symposium on Computational Geometry, pp. 274–283 (1996)

    Google Scholar 

11. Pocchiola, M., Vertger, G.: Computing the visibility graph via pseudo-triangulations. In: Proceedings of the 11th Annual ACM Symposium on Computational Geometry, pp. 248–257 (1995)

    Google Scholar 

12. Pocchiola, M., Vertger, G.: The visibility complex. Proceedings of the International Journal of Computational Geometry and Applications, 279–308 (1996)

    Google Scholar 

13. Pocchiola, M., Vertger, G.: Pseudo-triangulations: theory and applications. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 291–300 (1996)

    Google Scholar 

14. Randall, D., Rote, G., Santos, F., Snoeyink, J.: Counting triangulations and pseudo-triangulations of wheels. In: Proceedings of the 13th Canadian Conference on Computational Geometry, pp. 149–152 (2001)

    Google Scholar 

15. Rote, G., Wang, C.A., Wang, L., Xu, Y.: On constrained minimum pseudotriangulations. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 445–454. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

16. Speckmann, B., Tóth, C.D.: Allocating vertex π-guards in simple polygons via pseudo-triangulations. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 109–118 (2003)

    Google Scholar 

17. Streinu, I.: A combinatorical approach to planar non-colliding robot arm motion planning. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 443–453 (2000)

    Google Scholar 

Download references