Triangulating a polygon with holes — decomposing a multiply-connected region into triangles — has a natural complexity of O(n + h log h), where n is the total number of vertices and h is the number of holes. The h log h term comes from sorting the holes, which is information-theoretically necessary. Clarkson, Cole, and Tarjan achieved this bound in 1992 using randomization. Bar-Yehuda and Chazelle achieved a deterministic algorithm in 1994 with a slightly worse bound. For thirty years, no one could make a deterministic algorithm match the randomized complexity.
Timothy Chan closes the gap. His algorithm triangulates a polygon with h holes in O(n + h log h) deterministic time — optimal in both the input size and the number of holes, with no randomization required.
Note (2026-11-08): the abstract (Chan) says the earlier randomized algorithms (Clarkson, Cole and Tarjan 1992; Seidel 1991) ran in O(n log n + h log h) time, not the optimal O(n + h log h) the essay credits to them, and that the deterministic bounds of Bar-Yehuda and Chazelle (1994) were O(n + h log^(1+epsilon) h) and O((n + h log h) log log h). The new algorithm is optimal and deterministic, so it also improves on the randomized bound; there was no matching randomized optimum for it to close the gap to. The abstract says Chazelle's linear-time simple polygon triangulation is used as a black box; the essay's description of the technique (avoiding the trapezoidal map, hierarchical ordering of holes) is not in the abstract.*
The technique works through a careful decomposition that avoids the trapezoidal map construction on which previous approaches relied. Trapezoidal decomposition — sweeping a vertical line through the polygon — is the standard first step, but building it deterministically in optimal time has been the bottleneck. Chan's approach sidesteps this by working with the polygon's combinatorial structure directly, processing holes in a hierarchical order that amortizes the sorting cost.
The thirty-year gap between randomized and deterministic bounds for this fundamental problem is now closed. The result joins a small collection of computational geometry problems where the optimal deterministic algorithm was found decades after the optimal randomized one — a pattern that suggests the difficulty is in the technique, not the problem.
When a problem has a clean information-theoretic lower bound, the algorithm eventually finds it. Sometimes it takes a generation.