An O(nlog log n)-Time Algorithm for Triangulating a Simple Polygon

1988/02/01 by Robert E. Tarjan, Christopher J. Van Wyk · 10 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotics and Sensor-Based Localization #Simple polygon #Combinatorics #Polygon covering #Diagonal #Mathematics #Polygon (computer graphics) #Partition (number theory) #Simple (philosophy) #Computational geometry #Time complexity #Binary logarithm #Vertex (graph theory) #Triangulation #Algorithm #SIMPLE algorithm #Sorting #Monotone polygon #Computer science #Graph #Geometry

paper · doi:10.1137/0217010

openalex publication_date 1988/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n - 2 triangles by adding n - 3 nonintersecting diagonals. We propose an O(nlog log n)-time algorithm for this problem, improving on the previously best bound of O(nlog n) and showing that triangulation is not as hard as sorting. Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.

Citations

• Self-adjusting binary search trees

Cited by

• A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Generating triangulations at random
• Polygon triangulation inO(n log logn) time with simple data structures
• A fast las vegas algorithm for triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Slicing an ear using prune-and-search
• Art Gallery and Illumination Problems
• Recent results in art galleries (geometry)
• Polygon triangulation [wikipedia]