Triangulation

From ResearchWiki

• Garey, Johnson, Preparata, Tarjan (n log n, sweeping)
• Tarjan, Van Wyck (n log log n)
• Kirkpatrick, Klawe, Tarjan (same bound as above)
• Clarkson, Tarjan Van Wyck (n log ^* n randomized)
• Seidel: same bound as above, but simpler (see Point Location)
• Chazelle: linear time, horrendously complicated.

Triangulation of simple polygon is equivalent to trapezoidal decomposition of boundary segments, with a linear cost (Fournier, Montuno)

Techniques: sweep, RIC.