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

DOI10.1137/0217067MaRDI QIDQ3809268zbMATH OpenOpenAlexFDO

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

amortizedbalanced divide and conquercomputational geometryheterogeneous finger search treehomogeneous finger search treehorizontal visibility informationJordan sorting with error-correctionsimplicity testingtriangulation problem

Mathematics Subject Classification ID

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

Cited in

(6)

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

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)