Simple Linear-Time Polygon Triangulation

Determine whether there is a deterministic, linear-time algorithm for triangulating a simple polygon that is significantly simpler than Chazelle's algorithm.

Related question.

Determine whether there is a simple linear-time algorithm for computing a shortest path in a simple polygon without first applying a more complicated triangulation algorithm.

Download

Abstract

A deterministic linear-time algorithm for triangulating a simple polygon is known, but its construction is intricate. The open problem is to find a deterministic linear-time triangulation algorithm that is significantly simpler. Randomization yields simpler algorithms, including one with linear running time.

Background and progress

The question has been implicit since Chazelle's deterministic linear-time triangulation algorithm [Chazelle, 1991]. Simpler randomized algorithms with running time close to linear are known [Seidel, 1991]. A randomized linear-time algorithm later avoided much of the intricacy of Chazelle's method [Amato et al., 2000]. The corresponding simplification in the deterministic setting remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p10.

Reference papers

Linear-time triangulation of a simple polygon made easier via randomizationNancy M. Amato, Michael T. Goodrich, Edgar A. RamosProc. 16th Annu. ACM Sympos. Comput. Geom. · 2000
Triangulating a simple polygon in linear timeBernard ChazelleDiscrete Comput. Geom. · 1991
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygonsR. SeidelComput. Geom. Theory Appl. · 1991