Polygon triangulation inO(n log logn) time with simple data structures

We give a newO(n log logn)-time deterministic algorithm for triangulating simplen-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 inO(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 research was partially supported by the following grants: NSERC 583584, NSERC 580485, ONR-N00014-87-0467, and by DIMACS, an NSF Science and Technology Center (NSF-STC88-09648).