The Open Problems Project

Next: Problem 11: 3SUM Hard Problems

Previous: Problem 9: Edge-Unfolding Convex Polyhedra

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.