An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon

DOI10.1137/0217010zbMath0637.68044WikidataQ56389441 ScholiaQ56389441MaRDI QIDQ3777450

Robert Endre Tarjan, Christopher J. Van Wyk

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217010

zbMATH Keywords

computational geometry; simplicity testing; triangulation problem; amortized; balanced divide and conquer; heterogeneous finger search tree; homogeneous finger search tree; horizontal visibility information; Jordan sorting with error-correction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

52-04: Software, source code, etc. for problems pertaining to convex and discrete geometry

52A10: Convex sets in (2) dimensions (including convex curves)

Related Items

Triangulating a simple polygon in linear time, Tiling polygons with parallelograms, Finding minimum-cost flows by double scaling, Optimal parallel algorithms for point-set and polygon problems, Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures, Computing bushy and thin triangulations, The zookeeper route problem, Minimum vertex hulls for polyhedral domains, A workbench for computational geometry, Geometric classification of triangulations and their enumeration in a convex polygon, Motion planning in the presence of movable obstacles, Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences, A linear-time algorithm for constructing a circular visibility diagram, On the correctness of a linear-time visibility polygon algorithm^∗