Triangulating a Planar Polygon Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
So far, the only improvement to Chazelle's juggernaut is the 2001 randomized linear-time algorithm by Amato, Goodrich, and Ramos.  Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.