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

DOI10.1137/0217067zbMath0659.68068OpenAlexW2018714551MaRDI QIDQ3809268

Christopher J. Van Wyk, Robert Endre Tarjan

Publication date: 1988

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

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

zbMATH Keywords

computational geometrysimplicity testingtriangulation problemamortizedbalanced divide and conquerheterogeneous finger search treehomogeneous finger search treehorizontal visibility informationJordan sorting with error-correction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

Separating two simple polygons by a sequence of translations, Computing the link center of a simple polygon, Simplified linear-time Jordan sorting and polygon clipping, On separating two simple polygons by a single translation