Polygon triangulation in O(nn) time with simple data structures

DOI10.1007/BF02187846MaRDI QIDQ1189285zbMATH OpenDBLPWikidataFDO

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

zbMATH Keywords

horizontal visibilitysimple polygontriangulation

Mathematics Subject Classification ID

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

Review text

An \(O(n\log\log n)\) time algorithm for triangulating simple \(n\)-vertex polygons is presented. The rasterized version of the algorithm even consumes \(O(n\log^* n)\) time. Comparing to optimal linear time triangulating algorithms due to \textit{B. Chazelle} [Discrete Comput. Geom 6(5), 485-524 (1991)] the underlying data structures and procedures are quite simple. The algorithm is based on the balanced horizontal visibility partition of a given polygon.

Recommendations

• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• Triangulating a simple polygon in linear time
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity
• A randomized algorithm for triangulating a simple polygon in linear time

Cites work

• A fast Las Vegas algorithm for triangulating a simple polygon
• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• scientific article; zbMATH DE number 3825165 (Why is no real title available?)
• scientific article; zbMATH DE number 193423 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Simplified linear-time Jordan sorting and polygon clipping
• Sorting jordan sequences in linear time using level-linked search trees
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity

Cited in

(16)

• Triangulating a simple polygon in linear time
• Cartographic line simplification and polygon CSG formulae in O(n^* n) time
• Integral points in rational polygons: a numerical semigroup approach
• Three problems about simple polygons
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• Polygon triangulation: Efficiency and minimality
• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• TRIANGULATING DISJOINT JORDAN CHAINS
• scientific article; zbMATH DE number 753970 (Why is no real title available?)
• Spiral serpentine polygonization of a planar point set
• An O(log log n) algorithm to compute the kernel of a polygon
• Computing hereditary convex structures
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Time-space trade-offs for triangulating a simple polygon
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

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)