Abstract
We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are the polygon-cutting theorem, which provides us with a balancing scheme, and the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, of our algorithm.
Article PDF
Similar content being viewed by others
References
A. Aggarwal and J. Wein, Computational Geometry, Technical Report MIT/LCS/RSS 3, MIT, Cambridge, MA, August 1988.
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.
H. Booth, Some fast Algorithms on Graph and Trees, Ph.D. Thesis, Technical Report CS-TR 296-60, Princeton University, Princeton, NJ, 1990.
B. Chazelle, A theorem on polygon cutting with applications,Proc. 23rd Ann. IEEE Symp. on Found. of Comput. Sci. (1982), pp. 339–349.
B. Chazelle and L. J. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom. 4 (1989), 551–581.
B. Chazelle and J. Incerpi, Triangulation and shape-complexity,ACM Trans. Graphics 3 (1984), 135–152.
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.
D. P. Dobkin, D. L. Souvaine, and C. J. Van Wyk, Decomposition and intersection of simple splinegons,Algorithmica 3 (1988), 473–485.
H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput. 15 (1986), 317–340.
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.
A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics 3 (1984), 153–174.
M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett. 7 (1978), 175–180.
L. J. Guibas and J. Hershberger, Optimal shortest path queries in a simple polygon,J. Comput. System Sci. 32 (1989), 126–152.
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,Algorithmica 2 (1987), 209–233.
L. J. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics 4 (1985), 75–123.
J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size,Algorithmica 4 (1989), 141–155.
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.
K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees,Inform. and Control 68 (1986), 170–184.
D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput. 12 (1983), 28–35.
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.
R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs,SIAM J. Comput. 36 (1979), 177–189.
R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,SIAM J. Comput. 9 (1980), 615–627.
D. E. Muller and F. P. Preparata, Finding the intersection of two convex polyhedra,Theoret. Comput. Sci. 7 (1978), 217–236.
J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
R. Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Manuscript, 1990.
S. Suri, A linear time algorithm for minimum link paths inside a simple polygon,J. Comput. Vision Graphics Image Process. 35 (1986), 99–110.
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.
G. Toussaint,Computational Morphology, North-Holland, Amsterdam, 1988.
G. Toussaint, An Output-Complexity-Sensitive Polygon Triangulation Algorithm, Report SICS 86.3, McGill University, Montreal, 1988.
G. Toussaint and D. Avis, On a convex hull algorithm for polygons and its applications to triangulation problems,Pattern Recognition 15 (1982), 23–29.
C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme,Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), pp. 134–142.
Author information
Authors and Affiliations
Additional information
The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8700917.
Rights and permissions
About this article
Cite this article
Chazelle, B. Triangulating a simple polygon in linear time. Discrete Comput Geom 6, 485–524 (1991). https://doi.org/10.1007/BF02574703
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574703