Polygon triangulation in O(nn) time with simple data structures
DOI10.1007/BF02187846zbMATH Open0753.68092DBLPjournals/dcg/KirkpatrickKT92WikidataQ56389442 ScholiaQ56389442MaRDI QIDQ1189285FDOQ1189285
Authors: Maria M. Klawe, David Kirkpatrick, Robert E. 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Triangulating a simple polygon in linear time
- Optimal Search in Planar Subdivisions
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Optimal Point Location in a Monotone Subdivision
- Triangulating a simple polygon
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Title not available (Why is that?)
- Sorting jordan sequences in linear time using level-linked search trees
- Title not available (Why is that?)
- A fast Las Vegas algorithm for triangulating a simple polygon
- Simplified linear-time Jordan sorting and polygon clipping
Cited In (15)
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Spiral serpentine polygonization of a planar point set
- Integral points in rational polygons: a numerical semigroup approach
- Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time
- Polygon triangulation: Efficiency and minimality
- Triangulating a simple polygon in linear time
- Three problems about simple polygons
- Computing hereditary convex structures
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- An O(log log n) algorithm to compute the kernel of a polygon
- Title not available (Why is that?)
- TRIANGULATING DISJOINT JORDAN CHAINS
- Time-space trade-offs for triangulating a simple polygon
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
This page was built for publication: Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1189285)
