A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time
We present a modification to the divide-and-conquer algorithm of Guibas & Stolfi [GS] for computing the Delaunay triangulation of n sites in the plane. The change reduces its T(...