Triangulating a simple polygon in linear time

1991/09/01 by Bernard Chazelle · 2 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constrained Delaunay triangulation #Data Management and Algorithms #Data Visualization and Analytics #Delaunay triangulation #Diagonal #Discrete mathematics #Geometry #Mathematics #Minimum-weight triangulation #Point set triangulation #Polygon (computer graphics) #Polygon covering #Regular polygon #Simple (philosophy) #Simple polygon #Star-shaped polygon #Time complexity #Triangulation

paper · pdf · doi:10.1007/bf02574703

crossref issued 1991/09/01 · crossref published 1991/09/01 · crossref published-print 1991/09/01 · openalex publication_date 1991/09/01 · crossref created 2007/03/22 · crossref published-online 2007/06/26 · crossref deposited 2019/05/18 · openalex created_date 2025/10/10 · crossref indexed 2026/05/10 · openalex updated_date 2026/07/23

Citations

• An O(nlog log n)-Time Algorithm for Triangulating a Simple Polygon
• Applications of a Planar Separator Theorem
• A fast las vegas algorithm for triangulating a simple polygon
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Triangulating Simple Polygons and Equivalent Problems
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

Cited by

• Art Gallery and Illumination Problems
• Polygon triangulation [wikipedia]