>> I've wondered for a long time why ear clipping + optimizations has won on triangulation over stuff like Seidel's trapezoidal method, which has O(nlogn) time complexity

In solvespace we use a simple ear clipping algorithm but I'd love to have something O(nlog(n)).

I have yet to see one that's both small and comprehensible ;-) If I were to attempt it, I'd just add a spatial index to make the check for anything inside a triangle O(log(n)) and make sure we check for new ears adjacent to clipped ears. With that it should be n*log(n), but my old spatial index is 3D and on a HD somewhere.