Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures

DOI10.1007/BF02187846zbMath0753.68092WikidataQ56389442 ScholiaQ56389442MaRDI QIDQ1189285

Maria M. Klawe, David G. Kirkpatrick, Robert Endre Tarjan

Publication date: 26 September 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131199

zbMATH Keywords

triangulationsimple polygonhorizontal visibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Integral points in rational polygons: a numerical semigroup approach, Three problems about simple polygons, Computing hereditary convex structures

Cites Work

• Unnamed Item
• Unnamed Item
• Simplified linear-time Jordan sorting and polygon clipping
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon in linear time
• Triangulating a simple polygon
• A fast Las Vegas algorithm for triangulating a simple polygon
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• Optimal Point Location in a Monotone Subdivision
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Optimal Search in Planar Subdivisions
• Sorting jordan sequences in linear time using level-linked search trees