Chazelle's Linear-Time Polygon Triangulation Algorithm
Bernard Chazelle's algorithm is a classic breakthrough in computational geometry that proves any simple n-gon can be triangulated in strictly linear O(n) worst-case time without adding Steiner points.
Chazelle's linear-time polygon triangulation algorithm, published in 1991 by French-American theoretical computer scientist Bernard Chazelle in Discrete & Computational Geometry, resolved one of the most prominent open problems in computational geometry: whether a simple non-self-intersecting polygon with n vertices can be partitioned into n - 2 non-overlapping triangles in deterministic linear O(n) time.
Before Chazelle's landmark proof, polygon triangulation was believed to be constrained by an Omega(n log n) sorting lower bound, which applies to general sets of disjoint line segments. Although Michael Garey, David S. Johnson, Franco Preparata, and Robert Tarjan achieved an O(n log n) bound in 1978 by decomposing polygons into monotone sub-polygons, reducing the time complexity to strictly linear O(n) remained an elusive theoretical goal for over a decade. Chazelle proved that the ordered connectivity of a simple polygon's perimeter encodes sufficient topological information to circumvent the sorting bottleneck, establishing a foundational theoretical milestone in discrete geometry.
Algorithmic Architecture and Visibility Maps
Chazelle's linear-time algorithm operates by constructing a coarse-to-fine hierarchy of horizontal visibility decompositions, termed "trapezoidal maps" or "chords":
- Hierarchy of Sub-Polygons: Rather than attempting to compute the complete trapezoidal map directly in a single pass, the algorithm builds a balanced tree hierarchy of progressively coarser polygonal approximations. By subsampling vertices and replacing boundary chains with straight chords, Chazelle constructs simplified polygons whose visibility maps can be computed in time proportional to their reduced size.
- Bottom-Up Map Refinement: Using planar Jordan sorting (which sorts the intersections of a simple curve with a line in linear time), the algorithm refines the visibility maps from coarser levels back to the original full polygon. At each stage, the refinement step runs in linear time relative to the number of vertices added.
- Decomposition into Monotone Mountains: Once the complete horizontal visibility map of the polygon is constructed, the internal chords divide the interior into "monotone mountains"โsimple sub-polygons whose vertices are monotonic along a single axis and contain one unimodal boundary chain.
- Linear Triangulation: In 1984, Alain Fournier and Danielle Montuno proved that any monotone mountain can be triangulated in linear time using a single stack-based scan. Consequently, once the visibility map is determined, final triangulation requires only O(n) time.
Theoretical Significance vs. Practical Implementation
Chazelle's algorithm is celebrated for its theoretical elegance, but it is notoriously intricate to implement in software:
Because Chazelle's construction involves complex data structures, multi-level polygonal cuts, and large hidden constant factors, it is rarely implemented directly in commercial CAD or computer graphics packages. In applied computational geometry, software libraries (such as CGAL) typically employ Raimund Seidel's 1991 randomized trapezoidation algorithm, which achieves an expected running time of O(n log* n) (where log* is the iterated logarithm, effectively constant for all physical inputs) while remaining far simpler to program.
Jordan Sorting and Topological Foundations
The conceptual linchpin that allows Chazelle's algorithm to beat the O(n log n) sorting barrier is the Jordan curve theorem.
When an arbitrary collection of n points is sorted along a line, the information-theoretic lower bound is Omega(n log n). However, when the points represent consecutive intersections of a closed, non-self-intersecting Jordan curve with a straight line, the topological planarity of the curve prevents arbitrary permutations. By exploiting planarity through Jordan sorting, Chazelle proved that geometry can bypass algebraic sorting bounds.
Impact on Computational Geometry
Bernard Chazelle's breakthrough resolved a longstanding open question in computational geometry by demonstrating that polygon triangulation does not require sorting and can be accomplished in strictly linear time. The analytical tools developed in the proof stimulated new research into planar subdivision search and geometric decomposition.
Open Problems and Higher-Dimensional Generalizations
Chazelle's linear triangulation theorem unlocked progress across numerous geometric subfields:
- Shortest Paths in Polygons: Computing the Euclidean shortest path between two points inside a simple polygon requires a prior triangulation of the interior; Chazelle's result established that shortest paths can also be found in optimal O(n) time.
- Art Gallery Theorems: Determining the minimum number of guards required to observe a polygonal art gallery relies on three-coloring the vertices of a triangulated polygon, directly benefiting from linear preprocessing.
References
- Chazelle, B. (1991). Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(5), 485โ524. doi:10.1007/BF02574703
- Seidel, R. (1991). A simple and fast randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geometry, 1(1), 51โ64. doi:10.1016/0925-7721(91)90012-490012-4)
- Fournier, A., & Montuno, D. Y. (1984). Triangulating simple polygons and equivalent problems. ACM Transactions on Graphics, 3(2), 153โ174. doi:10.1145/357337.357341