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

DOI10.1137/0217067zbMATH Open0659.68068OpenAlexW2018714551MaRDI QIDQ3809268FDOQ3809268

Authors: Christopher J. Van Wyk, Robert E. 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)

Cited In (6)

• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
• Computing the link center of a simple polygon
• Separating two simple polygons by a sequence of translations
• Simplified linear-time Jordan sorting and polygon clipping
• On separating two simple polygons by a single translation
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon

This page was built for publication: Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3809268)