Polygon triangulation in O(n log log n) time with simple data-structures

ABSTRACT

We give a new &Ogr;(n log log n)-time deterministic linear-time algorithm for triangulating simple n-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 in &Ogr;(n log* n) time. The major new techniques employed are the efficient location of horizontal visibility edges which 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. This latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation. This research was partially supported by DIMACS and the following grants: NSERC 583584, NSERC 580485, NSF-STC88-09648, ONR-N00014-87-0467.

REFERENCES

• BT86: Bhattacharya, B.K. and Toussaint, G.T., "A linear algorithm for determining the translation separability of two simple polygons", McGill University, School Comput. Sci., Report SOCS-86.1, Montreal, Canada, 1986.
• C82: Chazelle, B., "A theorem on polygon cutting with applications", Proc. 23rd Annual Syrup. on Found. of Comput. Sci., 1982, pp. 339-349.
• CI84: B. Chazelle , J. Incerpi, Triangulation and shape-complexity, ACM Transactions on Graphics (TOG), v.3 n.2, p.135-152, April 1984 [doi>10.1145/357337.357340]
• C90: Chazelle, B., "Efficient Polygon Triangulation", preprint.
• CTV88: K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Proceedings of the fourth annual symposium on Computational geometry, p.18-22, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73396]
• EGS86: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• FFR83: Eugene Fiume , Alain Fournier , Larry Rudolph, A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultracomputer, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.141-150, July 1983
• FM84: A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
• FNTV88: K.Y. Fung, T.M. Nicholl, R.E. Tarjan, and C.J. Van Wyk, "Simplified linear-time Jordan sorting and polygon clipping", Princeton Tech. Report CS-TR- 189-88, 1988.
• GHLST87: 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), pp. 209-233.
• GJPT78: Garey, M.R., Johnson, D.S., Preparata, F.P. and Tarjan, R.E., "Triangulating a simple polygon", Inform. Process. Lett., 7 (1978), pp. 175-180.
• HM83: Stefan Hertel , Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.207-218, August 21-27, 1983
• HMRT86: Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E Tarjan, Sorting Jordan sequences in linear time using level-linked search trees, Information and Control, v.68 n.1-3, p.170-184, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80033-X]
• KK81: J.M. Keil and D.G. Kirkpatrick, "Computational Geometry on Integer Grids" ,Proc. 19th Annum Allerton Conference on Communication Control and Computing, September, 1981.
• K83: Kirkpatrick, D.G., "Optimal search in planar subdivisions", SIAM J. Comput. 12, 1 (Feb. 1983), pp. 28-35.
• LS1: D. T. Lee, Shading of regions on vector display devises, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.37-44, August 1981
• LTL89: W. T. Liou , J. J. Tan , R. C. Lee, Minimum partitioning simple rectilinear polygons in O(n log log n) - time, Proceedings of the fifth annual symposium on Computational geometry, p.344-353, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73871]
• TV88: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]
• T80: Toussaint, G., "Pattern recognition and geometrical complexity", Proc. 5th Intern. Conf. Pattern Recognition 1980, pp.1324-1347.
• T86: Toussaint, G., "Computational geometry and morphology", McGill Univ. Tech. Report 80CS-86.3, Montreal, Canada 1986.
• T88: Toussaint, G., "An output-complexity-sensitive polygon triangulation algorithm", McGill Univ. Tech. Report SOCS-88.11, Montreal, Canada 1988.
• T882: Toussaint, G., (Ed.), Computational Morphology, North-Holland, 1988.
• TA82: Toussaint, G. and Avis, D., "On a convex hull algorithm for polygons and its application to triangulation problems", Pattern Recognition 15,1(1982), pp.23- 29.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms