next up previous
Next: Problem 11: 3SUM Hard Up: The Open Problems Project Previous: Problem 9: Edge-Unfolding Convex


Problem 10: Simple Linear-Time Polygon Triangulation

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
[MO01]
Categories
triangulations
Entry Revision History
J. O'Rourke, 2 Aug. 2001; 28 Aug. 2001.

Bibliography

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.



The Open Problems Project - December 04, 2015