A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case

This paper exploits the notion of "unfinished site", introduced by Katajain en and Koppinen (1998) in the analysis of a two-dimensional Delaunay triang ulation algorithm, based on a regular grid. We generalize the notion and it s properties to any dimension k greater than or equal to 2: in the case of uniform distributions, the expected number of unfinished sites in a k-recta ngle is O(N1-1/k). This implies, under some specific assumptions, the linea rity of a class of divide-and-conquer schemes based on balanced k-d trees. This general result is then applied to the analysis of a new algorithm for constructing Delaunay triangulations in the plane. According to Su and Drys dale (1995, 1997), the best known algorithms for this problem run in linear expected time, thanks in particular to the use of bucketing techniques to partition the domain. In our algorithm, the partitioning is based on a 2-d tree instead, the construction of which takes Theta (N log N) time, and we show that the rest of the algorithm runs in linear expected time. This "pre processing" allows the algorithm to adapt efficiently to irregular distribu tions, as the domain is partitioned using point coordinates, as opposed to a fixed, regular basis (buckets or grid). We checked that even for the larg est data sets that could fit in internal memory lover 10 million points), c onstructing the 2-d tree takes noticeably less CPU time than triangulating the data. With this in mind, our algorithm is only slightly slower than the reputedly best algorithms on uniform distributions, and is even the most e fficient for data sets of up to several millions of points distributed in c lusters, (C) 2000 Elsevier Science B.V. All rights reserved.