A faster divide-and-conquer algorithm for constructing Delaunay triangulations (Q1094872)

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation of n sites in the plane is presented. The change reduces its \(\theta\) (n log n) expected running time to O(n log log n) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well for \(n\leq 2^{16}\), the range of the experiments. It is conjectured that the average number of edges it creates - a good measure of its efficiency - is no more than twice optimal for n less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in the \(L_ p\) metric for \(1<p\leq \infty\).