摘要: We give a deterministic algorithm for triangulating simple polygon in linear time. The basic strategy is to build coarse approximation of triangulation bottom-up phase and then use the information computed along way refine top-down phase. main tools used are polygon-cutting theorem, which provides us with balancing scheme, planar separator whose role essential discovery new diagonals. Only elementary data structures required by algorithm. In particular, no dynamic search trees, our
springer.com
acm.org 
sci-hub.se 参考文章(32)
Bruce G. Baumgart, A polyhedron representation for computer vision Proceedings of the May 19-22, 1975, national computer conference and exposition on - AFIPS '75. pp. 589- 596 ,(1975) , 10.1145/1499949.1500071
Richard J. Lipton, Robert Endre Tarjan, A Separator Theorem for Planar Graphs Siam Journal on Applied Mathematics. ,vol. 36, pp. 177- 189 ,(1979) , 10.1137/0136016
Leonidas J. Guibas, John Hershberger, Optimal shortest path queries in a simple polygon Journal of Computer and System Sciences. ,vol. 39, pp. 126- 152 ,(1989) , 10.1016/0022-0000(89)90041-X
Godfried T. Toussaint, David Avis, On a convex hull algorithm for polygons and its application to triangulation problems Pattern Recognition. ,vol. 15, pp. 23- 29 ,(1982) , 10.1016/0031-3203(82)90057-7
David P. Dobkin, Diane L. Souvaine, Christopher J. Van Wyk, Decomposition and intersection of simple splinegons Algorithmica. ,vol. 3, pp. 473- 485 ,(1988) , 10.1007/BF01762127
Leonidas Guibas, Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi ACM Transactions on Graphics. ,vol. 4, pp. 74- 123 ,(1985) , 10.1145/282918.282923
Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme Journal of Computer and System Sciences. ,vol. 40, pp. 2- 18 ,(1990) , 10.1016/0022-0000(90)90016-E
J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 11- 20 ,(1987) , 10.1145/41958.41960
A. Fournier, D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems ACM Transactions on Graphics. ,vol. 3, pp. 153- 174 ,(1984) , 10.1145/357337.357341
D.E. Muller, F.P. Preparata, Finding the intersection of two convex polyhedra Theoretical Computer Science. ,vol. 7, pp. 217- 236 ,(1978) , 10.1016/0304-3975(78)90051-8