Abstract
We give a newO(n log logn)-time deterministic algorithm for triangulating simplen-vertex polygons, which avoids the use of complicated data structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run inO(n log*n) time. The major new techniques employed are the efficient location of horizontal visibility edges that partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. The latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.
Article PDF
Similar content being viewed by others
References
Bhattacharya, B. K., and Toussaint, G. T., A linear algorithm for determining the translation separability of two simple polygons, Report SOCS-86.1, School Comput. Sci., McGill University, Montreal, 1986.
Chazelle, B., A theorem on polygon cutting with applications,Proc. 23rd Annual Symp. on Foundations of Computer Science, 1982, pp. 339–349.
Chazelle, B., Triangulating a simple polygon in linear time, Princeton Tech. Report CS-TR-264-90, 1990.
Chazelle, B., and Incerpi, J., Triangulation and shape complexity,ACM Trans. Graphics 3 (1984), 135–152.
Clarkson, K., Tarjan, R., and Van Wyk, C., A fast Las Vegas algorithm for triangulating a simple polygon,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 18–22 (Princeton Tech. Report CS-TR-157-88, 1988).
H. Edelsbrunner, Dynamic data structures for orthogonal intersection queries, Report f59, Techn. Univ. Graz, Instit. Informationsverarb., Graz, 1980.
Edelsbrunner, H., Guibas, L. J., and Stolfi, J., Optimal point location in a monotone subdivision,SIAM J. Comput. 15 (1986), 317–340.
Fiume, E., Fournier, A., and Rudolph, L., A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultra-computer,ACM Trans. Comput. Graphics 17(3) (1983), 141–150.
Fournier, A., and Montuno, D. Y., Triangulating simple polygons and equivalent problems,ACM Trans. Graphics 3 (1984), 153–174.
Fung, K. Y., Nicholl, T. M., Tarjan, R. E., and Van Wyk, C. J., Simplified linear-time Jordan sorting and polygon clipping, Princeton Tech. Report CS-TR-189-88, 1988.
Garey, M. R. Johnson, D. S., Preparata, F. P., and Tarjan, R. E., Triangulating a simple polygon,Inform. Process. Lett. 7 (1978), 175–180.
Guibas, L., Hershberger, J., Leven, D., Sharir, M., and Tarjan, R. E., Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons,Algorithmica 2 (1987), 209–233.
Hertel, S., and Mehlhorn, K., Fast triangulation of a simple polygon,Proc. Conf. on Foundations of Computer Theory, Lecture Notes on Computer Science, Vol. 158, Springer-Verlag, Berlin, 1983, pp. 207–218.
Hoffman, K., Mehlhorn, K., Rosenstiehl P., and Tarjan R., Sorting Jordan sequences in linear time using level-linked search trees,Inform. and Control 68 (1986), 170–184.
Keil, J. M., and Kirkpatrick, D. G., Computational geometry on integer gridsProc. 19th Annual Allerton Conference on Communication Control and Computing, 1981, pp. 41–50.
Kirkpatrick, D. G., Optimal search in planar subdivisions,SIAM J. Comput. 12(1) (1983), 28–35.
Lee, D. T., Shading of regions on vector display devices,ACM Trans. Comput. Graphics 15(3) (1981), 34–44.
Liou, W. T., Tan, J. J. M., and Lee, R. C. T., Minimum partitioning simple rectilinear polygons inO(n log logn) time,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 344–353.
Tarjan, R. E., and Van Wyk, C. J., AnO(n log logn)-time algorithm for triangulating a simple polygon,SIAM J. Comput. 17(1) (1988), 143–178.
Toussaint, G., Pattern recognition and geometrical complexity,Proc. 5th Intern. Conf. on Pattern Recognition, 1980, pp. 1324–1347.
Toussaint, G., Computational geometry and morphology, Tech. Report SOCS-86.3, McGill University, Montreal, 1986.
Toussaint, G., An output-complexity-sensitive polygon triangulation algorithm, Tech. Report SOCS-88.11, McGill University, Montreal, 1988.
Toussaint, G. (ed.),Computational Morphology, North-Holland, Amsterdam, 1988.
Toussaint, G., and Avis, D., On a convex hull algorithm for polygons and its application to triangulation problems,Pattern Recognition 15(1) (1982), 23–29.
Author information
Authors and Affiliations
Additional information
This research was partially supported by the following grants: NSERC 583584, NSERC 580485, ONR-N00014-87-0467, and by DIMACS, an NSF Science and Technology Center (NSF-STC88-09648).
Rights and permissions
About this article
Cite this article
Kirkpatrick, D.G., Klawe, M.M. & Tarjan, R.E. Polygon triangulation inO(n log logn) time with simple data structures. Discrete Comput Geom 7, 329–346 (1992). https://doi.org/10.1007/BF02187846
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02187846