# The ICICS/CS Reading Room

## UBC CS TR-90-17 Summary

- No on-line copy of this technical report is available.

- Polygon Triangulation in $0(N \log \log N)$ Time with Simple Data Structures, June 1990 David G. Kirkpatrick, Maria M. Klawe and Robert E. Tarjan
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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.