Complexity of Random Delaunay Triangulation in 3D My question:

Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one?

which is equivalent to the question

Is the number of Voronoi vertices in a three-dimensional Poisson-Voronoi tessellation with $n$ generators $\mathcal O(n)$ with probability one?


To formulate the question more mathematically, in terms of finite point configurations, denote 


*

*$Del(\gamma)$ the Delaunay triangulation of the (finite) point configuration $\gamma$,

*$\#Del(\gamma)$ denotes the number of tetrahedra in $Del(\gamma)$,

*$\Phi$ homogenous Poisson point process, and

*$\Phi|_B$ its restriction to a bounded Borel set $B$.
Then the question is whether there exists a constant $C>0$ such that
$$P(\# Del(\Phi|_B) \leq C \Phi(B)) = 1 $$
Alternatively the bound could be stochastic in that 
$$P(\# Del(\Phi|_B) \leq C \Phi(B)) \to 1 \text{ as } \#Del(\Phi|_B)\to \infty$$

My thoughts on the question:
On one hand, it is well known that the complexity 3d Delaunay triangulation is $\mathcal O(n^2)$ in general.
However, as noted in (1), the only know examples attaining this complexity are from point distributions on one-dimensional curves such as the moment curve. Furthermore, the expected complexity of Poisson-Delaunay distributed in a cube is $\mathcal O(n)$ (e.g. (2)). In (3), Jeff Erickson goes as far as saying that

For all practical purposes, three-dimensional Delaunay triangulations appear to have linear complexity.

This leads me to the question whether it is in fact almost surely true that a three dimensional Poisson-Delauany triangulation has $\mathcal O(n)$ cells. I haven't been able to find any reference on this fact, thought. I'll be grateful for a reference showing this statement or a counterexample. 

Possible proof/counterexample strategies.
In (3) and (4), Erickson proves some bounds between the complexity of the Delaunay triangulation and the spread $\Delta$ - the ratio between the longest and shortest pairwise distance. This gives some chance for the complexity to be continuous in the sense of moving points (since spread is). 
Perhaps spread could be used to prove the statement, or, perhaps we could allow the points on the moment curve to "wiggle" around, thus creating a class of configurations with have non-zero probability with respect to the Poisson process, while retaining the super-linear complexity. 

References


*

*1: Nina Amenta, Dominique Attali, and Olivier Devillers. 2007.
Complexity of Delaunay triangulation for points on lower-dimensional
polyhedra 

*2: R. Dwyer, The expected number of k-faces of a Voronoi
diagram, Computers Math. Applications 26 (5) (1993)

*3: Jeff Erickson. 2001. Nice point sets can have nasty Delaunay triangulations. In Proceedings of the seventeenth annual symposium on Computational geometry (SCG '01), Diane L. Souvaine (Ed.). ACM, New York, NY, USA, 96-105.

*4: Jeff Erickson. 2002. Dense point sets have sparse Delaunay triangulations: or "…but not too nasty". In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '02). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 125-134.
 A: Yes, at least for periodic boundary conditions so we don't have to worry about what happens near the boundary. See
Dwyer, Rex A.
Higher-dimensional Voronoĭ diagrams in linear expected time. 
Discrete Comput. Geom. 6 (1991), no. 4, 343–367
Dwyer counts Voronoi vertices rather than Delaunay simplices but it's the same thing. He only actually proves that the expected number is linear, not that it's linear with high probability, but it's straightforward to convert an expected value into a high probability bound via the fact that far-enough parts of the Delaunay triangulation don't affect each other. See e.g. proof of Lemma 9 in
Bern, Marshall; Eppstein, David; Yao, Frances.
The expected extremes in a Delaunay triangulation. 
Internat. J. Comput. Geom. Appl. 1 (1991), no. 1, 79–91.
https://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf
A: You may gain some empirical insight from this exploration:

Tanemura, Masaharu. "Statistical distributions of Poisson Voronoi cells in two and three dimensions." FORMA-TOKYO- 18, no. 4 (2003): 221-247.
  PDF download.
  
            
  


