Return to Question

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 exist constants $C>0$ and $n_0\in\mathbb N$ such that $$P(\# Del(\Phi|_B) \leq C \Phi(B)) = 1 \; \text{when } \#Del(\Phi|_B) \geq n_0$$

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.

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.

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 $$

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.

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 exist constants $C>0$ and $n_0\in\mathbb N$ such that $$P(\# Del(\Phi|_B) \leq C \Phi(B)) = 1 \; \text{when } \#Del(\Phi|_B) \geq n_0$$

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.

My thoughts on the question:

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 $$

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 $$

My thoughts on the question: