Next: Problem 11: 3SUM Hard Problems
Previous: Problem 9: Edge-Unfolding Convex Polyhedra
Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle [Cha91]?
Implicit since Chazelle’s 1990 linear-time algorithm.
Open.
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.
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?
triangulations
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 randomization. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 201–212, 2000.
Bernard Chazelle. 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.
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.