Triangulating a Planar Polygon
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.