4
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ I guess you're asking whether the probability tends to 1 as n goes to infinity? $\endgroup$
    – alesia
    Commented Dec 16, 2018 at 15:51
  • 1
    $\begingroup$ I think the answer should be yes, as far as I remember the expected degree of a vertex in such a Delaunay triangulation is roughly 27. Maybe the result on expected vertex degree can be boosted to asymptotically almost surely by using the fact that "distant" vertices have nearly independent degrees? $\endgroup$
    – alesia
    Commented Dec 16, 2018 at 15:57
  • $\begingroup$ @alesia: I suppose what I'm asking about is a stronger result? Either would be interesting, though. I've edited the question a little. 27 is roughly the number of vertices of a Voronoi cells, which would correspond to neighboring tetrahedra, I think degree of a Delaunay vertex corresponds to the number of edges, which is around 40.6 (pg. 316 in Okabe et al. ). Are you suggesting we bound the probability using Chebyshev's inequality to prove the asymptotic result? $\endgroup$
    – Dahn
    Commented Dec 16, 2018 at 18:22
  • $\begingroup$ What trips me up is that typically one thinks of Poisson in terms of the whole $\mathbb R^3$ and the intensity, whereas complexity requires the thinking to shift to $n$ iid points in a bounded set (I think?). To be honest, I am struggling to even understand the question correctly. $\endgroup$
    – Dahn
    Commented Dec 16, 2018 at 18:27
  • $\begingroup$ I mean you need to let n go to infinity, else the probability will be less than 1 for any C. And yes you need a bounded domain for the question to make sense. And I was suggesting using the fact that distant vertices have roughly independent degrees (to be proved). This way the probability that the average degree is more than say 1000 should go to zero for large n. More accurately, you should indeed consider the number of incident tetrahedra instead of the degree $\endgroup$
    – alesia
    Commented Dec 17, 2018 at 0:56

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

          Fig2

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .