A. Kartashov et R. Folk, DELAUNAY TRIANGULATIONS IN THE PLANE WITH O(ROOT-N-LOG-N) STORAGE REQUIREMENTS, International journal of modern physics C, 6(5), 1995, pp. 639-649
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.