Next: Problem 11: 3SUM Hard
Up: The Open Problems Project
Previous: Problem 9: EdgeUnfolding Convex
Problem 10: Simple LinearTime Polygon Triangulation
 Statement
 Is there a deterministic, lineartime polygon triangulation
algorithm significantly simpler than that of Chazelle [Cha91]?
 Origin
 Implicit since Chazelle's 1990 lineartime algorithm.
 Status/Conjectures
 Open.
 Partial and Related Results
 Simple randomized algorithms that are close to lineartime
are known [Sei91],
and a recent randomized lineartime
algorithm [AGR00] avoids much of the intricacies
of Chazelle's algorithm.
 Related Open Problems
 Relatedly, is there a simple lineartime algorithm for
computing a shortest path in a simple polygon, without
first applying a more complicated triangulation algorithm?
 Appearances
 [MO01]
 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.
Lineartime triangulation of a simple polygon made easier via
randomization.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 201212,
2000.
 Cha91

Bernard Chazelle.
Triangulating a simple polygon in linear time.
Discrete Comput. Geom., 6(5):485524, 1991.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (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):5164, 1991.
The Open Problems Project  September 19, 2017