Best time complexity for sequentially contructing a 3D Voronoi-Delaunay diagram

Question

According to R. A. Dwyer, Algorithmica 2.1-4 (1987): 137-151 the Delaunay triangulation for a uniform distribution of N points in a unit square can be constructed in O(N lnlnN) time. I was wondering what's the currently fastest known sequential algorithm of constructing a Delaunay diagram for a uniform distribution in a cubic cell?

Answer 1

TL; DR: I'd expect quasi-O(n) behaviour for a set of "well-distributed" points in a cube.

---

Good incremental algorithms for the construction of Delaunay tessellations / Voronoi complexes in R^3 have worst-case run-times of O(n^2) (where n is the number of points). It's known that these worst cases rarely occur in practice though, and it's expected that most "real" cases exhibit quasi-O(n) scaling.

Documentation for the Triangulation_3 class available in CGAL includes a discussion of such behaviour, as well as links to several papers that provide bounds on asymptotic complexity for certain distributions of points.

In short, the running time of an incremental Delaunay algorithm is based on a few different factors: (a) the complexity of the kernel used to insert individual points (through the modification of local topology), (b) the complexity of the search algorithm used to locate the subset of the tessellation to be modified, and (c) the "structure" of the distribution of points to be added, and the order in which they're processed.

"Fast" algorithms for (a) and (b) (i.e. Bowyer-Watson, etc) are known, and (c) is amenable to "biased" quasi-random ordering strategies. The combination of these techniques typically leads to O(n) behaviour in most practical cases.

This only leaves a set of rather pathological cases for which lesser performance is observed. To me, these cases generally seem so specific that they'd essentially need to be constructed by hand.