Next: Problem 11: 3SUM Hard
Up: The Open Problems Project
Previous: Problem 9: Edge-Unfolding Convex
Problem 10: Simple Linear-Time Polygon Triangulation
- Is there a deterministic, linear-time polygon triangulation
algorithm significantly simpler than that of Chazelle [Cha91]?
- Implicit since Chazelle's 1990 linear-time algorithm.
- 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?
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001; 28 Aug. 2001.
Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos.
Linear-time triangulation of a simple polygon made easier via
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 201-212,
Triangulating a simple polygon in linear time.
Discrete Comput. Geom., 6(5):485-524, 1991.
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.
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 08, 2012