An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
Robert Endre Tarjan, Christopher J. Van Wyk · SIAM Journal on Computing · 1988
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\log \log n)$-time algorithm for this problem, improving on the previously best bound of $O(n\log 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.