An O(n log log n)- time Algorithm for Triangulating a Simple Polygon

A simple n-vertex polygon is triangulated by adding to it n- 3 nonintersecting diagonals that partition the interior into n-2 triangles. This problem is of practical importance in computer graphics, and is also of theoretical interest because for many years the best known time bound for triangulation was O(n log n). The result in this talk shows that triangulation is actually easier than sorting. This result has many applications in computational geometry, including testing whether a given polygon is simple in o(n log n) time.