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

• A polygon can be triangulated in linear time, though the algorithm (due to Chazelle) is not particularly simple: cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf. – Yuval Filmus May 13 '14 at 17:18
• Yes, linear time is $o(n \log n)$. – Geoffrey Irving May 13 '14 at 17:36
• Triangulation by decomposing into monotone pieces avoids the trapezoidal decomposition. – Louis May 13 '14 at 18:35

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.
I was looking for such a diagonal as well. As I could not find a simple way to obtain it we applied a linear time cutting of the polygon (Sutherland–Hodgman approach). Given a simple polygon $$P$$ we take a vertical line $$\ell$$ and cut through $$P$$. This can be done if $$O(n)$$ time by simply iterating over the boundary list of $$P$$ and verify if $$\ell$$ is crossed. This produces a set of sub-polygons. Clearly the number of vertices of the polygons to the left of $$\ell$$ is equal to the number of vertices on the right side of $$\ell$$, up to a constant at least. Then we triangulated each sub-polygon. Since there are vertices in the sub-polygons due to the cutting we had to also add a repair step to get rid of these additional vertices. For more details look directly at our work.