$O(n \log n)$ simple polygon triangulation via divide and conquer I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon.  It seems like there should be a simple divide and conquer variant that would fit the bill, ideally one avoiding auxiliary data structures such as trapezoidal decompositions.  Indeed, all that would be required is an $O(n)$ algorithm for finding a roughly balanced diagonal.  However, I am unable to find any algorithms that are as simple as I (perhaps naively) imagine should exist; nearly all the research is focused on $o(n \log n)$ algorithms, nearly all of which operate via trapezoidal decomposition.
Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.