DELAUNAY TRIANGULATIONS IN THE PLANE WITH O(ROOT-N-LOG-N) STORAGE REQUIREMENTS

We present a straightforward iterative algorithm constructing the plan ar Delaunay triangulation in O(N log N) time. The algorithm proceeds i teratively by adding new points one by one to a partial point set pre- ordered by one coordinate and adjusting the partial diagram correspond ingly. We introduce the techniques of safe fragments, showing that the larger part of a partial digram cannot be changed by adding further p oints; in the average case of a random point set the amount of informa tion which need be stored in memory at any moment does not exceed O(ro ot N log N). The computational overhead for the memory management is l inear in N. In particular, this makes very large Delaunay triangulatio ns (and Voronoi tessellations) accessible for simulations on personal computers.