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.
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.