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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 13 '14 at 17:18
  • $\begingroup$ Yes, linear time is $o(n \log n)$. $\endgroup$ – Geoffrey Irving May 13 '14 at 17:36
  • $\begingroup$ Triangulation by decomposing into monotone pieces avoids the trapezoidal decomposition. $\endgroup$ – 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.

  • $\begingroup$ Thanks, I've seen that one, though it's essentially doing trapezoidal decomposition. It's also not really divide and conquer. It's possible I should get over my allergy to non-rotationally invariant algorithms. $\endgroup$ – Geoffrey Irving May 13 '14 at 17:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.