Polygon Triangulation in $O(N^log^log^N)$ Time with Simple Data Structures

Abstract:

We give a new $O(n$ log log $n)$-time deterministic algorithm for
triangulating simple $n$-vertex polygons, which avoids the use of
complicated data structures. In addition, for polygons whose vertices
have integer coordinates of polynomially bounded size, the algorithm
can be modified to run in $O(n$ log* $n)$ time. The major new
techniques employed are the efficient location of horizontal visibility
edges that partition the interior of the polygon into regions of
approximately equal size, and a linear-time algorithm for obtaining the
horizontal visibility partition of a subchain of a polygonal chain,
from the horizontal visibility partition of the entire chain. The
latter technique has other interesting applications, including a
linear-time algorithm to convert a Steiner triangulation of a polygon
into a true triangulation.

This technical report has been published as

Polygon Triangulation in $O(N^log^log^N)$ Time with Simple Data
Structures.
David G. Kirkpatrick, Maria M. Klawe and Robert E. Tarjan,

Proc. Sixth Annual ACM Symp. on Computational Geoemtry
(1990) 34-43 and

Discrete and Computational Geometry 7 (1992)
329-346.