Degrees in the ${\hat{I}}^2$- and $β'$-Delaunay graphs

Abstract

We investigate the typical cells $\hat{Z}$ and ${\hat{Z}}^{\prime }$ of ${\hat{I}}^2$- and $β'$-Voronoi tessellations in ${\mathbb{R}}^d$, establishing a Complementary Theorem which entails: 1) a gamma distribution of the $\hat{I}¦$-content (a suitable homogeneous functional) of the typical cell with $n$-facets; 2) the independence of this $\hat{I}¦$-content with the shape of the cell; 3) a practical integral representation of the distribution of $Z^{(\prime )}$. We exploit the latter to derive bounds on the distribution of the facet numbers. Using duality, we get bounds on the typical degree distributions of ${\hat{I}}^2$- and $β'$-Delaunay triangulations. For $β'$-Delaunay, the resulting exponential lower bound seems to be the first of its kind for random spatial graphs arising as the skeletons of random tessellations. For ${\hat{I}}^2$-Delaunay, matching super-exponential bounds allow us to show concentration of the maximal degree in a growing window to only a finite number of deterministic values (in particular, only two values for $d=2$).

32 pages, 7 figures