A fast las vegas algorithm for triangulating a simple polygon
作者： Kenneth L. Clarkson , Robert E. Tarjan , Christopher J. Van Wyk
DOI: 10.1007/BF02187741
关键词:
摘要: We present a randomized algorithm that triangulates simple polygon onn vertices inO(n log*n) expected time. The averaging in the analysis of running time is over possible choices made by algorithm; bound holds for any input polygon.
springer.com
princeton.edu
paperity.org参考文章(16)
Joel Spencer, Probabilistic Methods in Combinatorics ,(1974)
Robert E. Tarjan, Christopher J. Van Wyk, An O ( n log log n )-time algorithm for triangulating a simple polygon SIAM Journal on Computing. ,vol. 17, pp. 143- 178 ,(1988) , 10.1137/0217010
Michael R. Garey, David S. Johnson, Franco P. Preparata, Robert E. Tarjan, Triangulating a simple polygon Information Processing Letters. ,vol. 7, pp. 175- 179 ,(1978) , 10.1016/0020-0190(78)90062-5
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
David Haussler, Emo Welzl, ɛ-nets and simplex range queries Discrete & Computational Geometry. ,vol. 2, pp. 127- 151 ,(1987) , 10.1007/BF02187876
K. L. Clarkson, Applications of random sampling in computational geometry, II symposium on computational geometry. ,vol. 4, pp. 1- 11 ,(1988) , 10.1145/73393.73394
Kenneth L. Clarkson, New applications of random sampling in computational geometry Discrete & Computational Geometry. ,vol. 2, pp. 195- 222 ,(1987) , 10.1007/BF02187879
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
Kurt Hoffmann, Kurt Mehlhorn, Pierre Rosenstiehl, Robert E. Tarjan, Sorting jordan sequences in linear time using level-linked search trees Information and Control. ,vol. 68, pp. 170- 184 ,(1986) , 10.1016/S0019-9958(86)80033-X
B. Chazelle, J. Incerpi, Triangulation and shape-complexity ACM Transactions on Graphics. ,vol. 3, pp. 135- 152 ,(1984) , 10.1145/357337.357340