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.