1. A. Aggarwal and J. Wein, Computational Geometry, Technical Report MIT/LCS/RSS 3, MIT, Cambridge, MA, August 1988.

   Google Scholar 

2. B. G. Baumgart, A polyhedron representation for computer vision,Proc. 1975 National Comput. Conf., AFIPS Conference Proceedings, Vol. 44, AFIPS Press, Montvale, NJ (1975), pp. 589–596.

   Google Scholar 

3. H. Booth, Some fast Algorithms on Graph and Trees, Ph.D. Thesis, Technical Report CS-TR 296-60, Princeton University, Princeton, NJ, 1990.

   Google Scholar 

4. B. Chazelle, A theorem on polygon cutting with applications,Proc. 23rd Ann. IEEE Symp. on Found. of Comput. Sci. (1982), pp. 339–349.

5. B. Chazelle and L. J. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom.4 (1989), 551–581.

   Article MathSciNet MATH  Google Scholar 

6. B. Chazelle and J. Incerpi, Triangulation and shape-complexity,ACM Trans. Graphics3 (1984), 135–152.

   Article MATH  Google Scholar 

7. K. Clarkson, R. E. Tarjan, and C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon,Discrete Comput. Geom.4 (1989), 423–432.

   Article MathSciNet MATH  Google Scholar 

8. D. P. Dobkin, D. L. Souvaine, and C. J. Van Wyk, Decomposition and intersection of simple splinegons,Algorithmica3 (1988), 473–485.

   Article MathSciNet MATH  Google Scholar 

9. H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput.15 (1986), 317–340.

   Article MathSciNet MATH  Google Scholar 

10. H. Edelsbrunner and E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms,Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), pp. 118–133.

11. A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics3 (1984), 153–174.

    Article MATH  Google Scholar 

12. M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett.7 (1978), 175–180.

    Article MathSciNet MATH  Google Scholar 

13. L. J. Guibas and J. Hershberger, Optimal shortest path queries in a simple polygon,J. Comput. System Sci.32 (1989), 126–152.

    Article MathSciNet  Google Scholar 

14. L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons,Algorithmica2 (1987), 209–233.

    Article MathSciNet MATH  Google Scholar 

15. L. J. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics4 (1985), 75–123.

    Article  Google Scholar 

16. J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size,Algorithmica4 (1989), 141–155.

    Article MathSciNet MATH  Google Scholar 

17. S. Hertel and K. Mehlhorn, Fast triangulation of a simple polygon,Proc. Conf. Found. Comput. Theory, Lecture Notes on Computer Science, Vol. 158, Springer-Verlag, Berlin (1983), pp. 207–218.

    Chapter  Google Scholar 

18. K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees,Inform. and Control68 (1986), 170–184.

    Article MathSciNet  Google Scholar 

19. D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.12 (1983), 28–35.

    Article MathSciNet MATH  Google Scholar 

20. D. G. Kirkpatrick, M. M. Klawe, and R. E. Tarjan,O(n log logn) polygon triangulation with simple data structures,Proc. 6th Ann. ACM Symp. Comput. Geom. (1990), pp. 34–43.

21. R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs,SIAM J. Comput.36 (1979), 177–189.

    MathSciNet MATH  Google Scholar 

22. R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,SIAM J. Comput.9 (1980), 615–627.

    Article MathSciNet MATH  Google Scholar 

23. D. E. Muller and F. P. Preparata, Finding the intersection of two convex polyhedra,Theoret. Comput. Sci.7 (1978), 217–236.

    Article MathSciNet MATH  Google Scholar 

24. J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.

    MATH  Google Scholar 

25. R. Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Manuscript, 1990.

26. S. Suri, A linear time algorithm for minimum link paths inside a simple polygon,J. Comput. Vision Graphics Image Process.35 (1986), 99–110.

    Article MATH  Google Scholar 

27. R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-time algorithm for triangulating a simple polygon,SIAM J. Comput.17 (1988), 143–178.

    Article MathSciNet MATH  Google Scholar 

28. G. Toussaint,Computational Morphology, North-Holland, Amsterdam, 1988.

    MATH  Google Scholar 

29. G. Toussaint, An Output-Complexity-Sensitive Polygon Triangulation Algorithm, Report SICS 86.3, McGill University, Montreal, 1988.

    Google Scholar 

30. G. Toussaint and D. Avis, On a convex hull algorithm for polygons and its applications to triangulation problems,Pattern Recognition15 (1982), 23–29.

    Article MathSciNet  Google Scholar 

31. C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme,Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), pp. 134–142.

Download references