Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
作者： Raimund Seidel
DOI: 10.1016/J.COMGEO.2010.03.003
关键词:
摘要: This paper presents a very simple incremental randomized algorithm for computing the trapezoidal decomposition induced by set S of n line segments in plane. If is given as polygonal chain expected running time O(nlog^*n). leads to same complexity triangulating polygons. More generally, if presented plane graph with k connected components, then O(nlog^*n+klogn). As by-product our creates search structure linear size that allows point location queries resulting trapezoidation logarithmic time. The analysis performance elementary and straightforward. All expectations are respect ''coinflips'' generated not based on assumptions about geometric distribution input.
elsevier.com
acm.org 
core.ac.uk 
sci-hub.se 参考文章(13)
Godfried Toussaint, An output-complexity-sensitive polygon triangulation algorithm CG International '90 Proceedings of the eighth international conference of the Computer Graphics Society on CG International '90: computer graphics around the world. pp. 443- 466 ,(1990) , 10.1007/978-4-431-68123-6_26
Kurt Mehlhorn, Stefan Hertel, Marek Karpinski, Fast Triangulation of Simple Polygons Untitled Event. pp. 207- 218 ,(1983)
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
David G. Kirkpatrick, Maria M. Klawe, Robert E. Tarjan, Polygon triangulation in O(n log log n) time with simple data-structures symposium on computational geometry. pp. 34- 43 ,(1990) , 10.1145/98524.98533
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
Kenneth L. Clarkson, Robert E. Tarjan, Christopher J. Van Wyk, A fast las vegas algorithm for triangulating a simple polygon Discrete & Computational Geometry. ,vol. 4, pp. 423- 432 ,(1989) , 10.1007/BF02187741
Robert E. Tarjan, Richard Cole, Kenneth L. Clarkson, Randomized Parallel Algorithms for Trapezoidal Diagrams ,(2018)
Bernard Chazelle, A theorem on polygon cutting with applications 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 339- 349 ,(1982) , 10.1109/SFCS.1982.58
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
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