Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
From MaRDI portal
Publication:1189285
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
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