Constructing Delaunay Triangulations by Merging Buckets in Quad Tree Order

Abstract

Recently Rex Dwyer [D87] presented an algorithm which constructs a Delaunay triangulation for a planar set of N sites in O(N log log N) expected time and O(N log N) worst-case time. We show that a slight modification of his algorithm preserves the worst-case running time, but has only O(N) average running time. The methcxl is a hybrid which combines the cell technique with the divide-and-conquer algorithm of Guibas & Stolfi [GS85]. First a square grid of size about $\sqrt{\mathit{N}}$ by $\sqrt{\mathit{N}}$ is placed on the set of sites. The grid forms about N cells (buckets), each of which is implemented as a list of the sites which fall into the corresponding square of the grid. A Delaunay triangulation of the generally rather few sites within each cell is constructed with the Guibas & Stolfi algorithm. Then the triangulations are merged, four by four, in a quadtree-like order.