[ColonelTrick]

Since I just love the impracticality of it, Bernard Chazelle's linear time triangulation is my fave.

https://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.p...