×

Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures. (English) Zbl 0753.68092

An \(O(n\log\log n)\) time algorithm for triangulating simple \(n\)-vertex polygons is presented. The rasterized version of the algorithm even consumes \(O(n\log^* n)\) time. Comparing to optimal linear time triangulating algorithms due to B. Chazelle [Discrete Comput. Geom 6(5), 485-524 (1991)] the underlying data structures and procedures are quite simple. The algorithm is based on the balanced horizontal visibility partition of a given polygon.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 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.
[2] Chazelle, B., A theorem on polygon cutting with applications,Proc. 23rd Annual Symp. on Foundations of Computer Science, 1982, pp. 339-349.
[3] Chazelle, B., Triangulating a simple polygon in linear time, Princeton Tech. Report CS-TR-264-90, 1990. · Zbl 0753.68090
[4] Chazelle, B., and Incerpi, J., Triangulation and shape complexity,ACM Trans. Graphics3 (1984), 135-152. · Zbl 0592.68083 · doi:10.1145/357337.357340
[5] 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). · Zbl 0681.68061
[6] H. Edelsbrunner, Dynamic data structures for orthogonal intersection queries, Report f59, Techn. Univ. Graz, Instit. Informationsverarb., Graz, 1980.
[7] Edelsbrunner, H., Guibas, L. J., and Stolfi, J., Optimal point location in a monotone subdivision,SIAM J. Comput.15 (1986), 317-340. · Zbl 0602.68102 · doi:10.1137/0215023
[8] Fiume, E., Fournier, A., and Rudolph, L., A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultra-computer,ACM Trans. Comput. Graphics17(3) (1983), 141-150. · doi:10.1145/964967.801143
[9] Fournier, A., and Montuno, D. Y., Triangulating simple polygons and equivalent problems,ACM Trans. Graphics3 (1984), 153-174. · Zbl 0592.68084 · doi:10.1145/357337.357341
[10] 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. · Zbl 0697.68036
[11] Garey, M. R. Johnson, D. S., Preparata, F. P., and Tarjan, R. E., Triangulating a simple polygon,Inform. Process. Lett.7 (1978), 175-180. · Zbl 0384.68040 · doi:10.1016/0020-0190(78)90062-5
[12] 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,Algorithmica2 (1987), 209-233. · Zbl 0642.68081 · doi:10.1007/BF01840360
[13] 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. · Zbl 0521.68040
[14] Hoffman, K., Mehlhorn, K., Rosenstiehl P., and Tarjan R., Sorting Jordan sequences in linear time using level-linked search trees,Inform. and Control68 (1986), 170-184. · Zbl 0614.68051 · doi:10.1016/S0019-9958(86)80033-X
[15] 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.
[16] Kirkpatrick, D. G., Optimal search in planar subdivisions,SIAM J. Comput.12(1) (1983), 28-35. · Zbl 0501.68034 · doi:10.1137/0212002
[17] Lee, D. T., Shading of regions on vector display devices,ACM Trans. Comput. Graphics15(3) (1981), 34-44.
[18] 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.
[19] 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. · Zbl 0637.68044 · doi:10.1137/0217010
[20] Toussaint, G., Pattern recognition and geometrical complexity,Proc. 5th Intern. Conf. on Pattern Recognition, 1980, pp. 1324-1347.
[21] Toussaint, G., Computational geometry and morphology, Tech. Report SOCS-86.3, McGill University, Montreal, 1986. · doi:10.1007/978-94-009-3757-4_47
[22] Toussaint, G., An output-complexity-sensitive polygon triangulation algorithm, Tech. Report SOCS-88.11, McGill University, Montreal, 1988.
[23] Toussaint, G. (ed.),Computational Morphology, North-Holland, Amsterdam, 1988. · Zbl 0642.00022
[24] Toussaint, G., and Avis, D., On a convex hull algorithm for polygons and its application to triangulation problems,Pattern Recognition15(1) (1982), 23-29. · doi:10.1016/0031-3203(82)90057-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.