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

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n - 2 triangles by adding n - 3 nonintersecting diagonals. We propose an O (n n) -time algorithm for this problem, improving on the previously best bound of O (n n) and showing that triangulation is not as hard as sorting. Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.