**Next:** Problem 11: 3SUM Hard Problems

**Previous:** Problem 9: Edge-Unfolding Convex Polyhedra

- Statement
Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle [Cha91]?

- Origin
Implicit since Chazelle’s 1990 linear-time algorithm.

- Status/Conjectures
Open.

- Partial and Related Results
Simple randomized algorithms that are close to linear-time are known [Sei91], and a recent randomized linear-time algorithm [AGR00] avoids much of the intricacies of Chazelle’s algorithm.

- Related Open Problems
Relatedly, is there a simple linear-time algorithm for computing a shortest path in a simple polygon, without first applying a more complicated triangulation algorithm?

- Appearances
- Categories
triangulations

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; 28 Aug. 2001.

- [AGR00]
Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos. Linear-time triangulation of a simple polygon made easier via randomization. In

*Proc. 16th Annu. ACM Sympos. Comput. Geom.*, pages 201–212, 2000.- [Cha91]
Bernard Chazelle. Triangulating a simple polygon in linear time.

*Discrete Comput. Geom.*, 6(5):485–524, 1991.- [MO01]
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42.

*Internat. J. Comput. Geom. Appl.*, 11(5):573–582, 2001. Also in*SIGACT News*32(3):63-72 (2001), Issue 120.- [Sei91]
R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons.

*Comput. Geom. Theory Appl.*, 1(1):51–64, 1991.