Introduction to Stochastic Geometry

Abstract

This chapter introduces some of the fundamental notions from stochastic geometry. Background information from convex geometry is provided as far as this is required for the applications to stochastic geometry.

First, the necessary definitions and concepts related to geometric point processes and from convex geometry are provided. These include Grassmann spaces and invariant measures, Hausdorff distance, parallel sets and intrinsic volumes, mixed volumes, area measures, geometric inequalities and their stability improvements. All these notions and related results will be used repeatedly in the present and in the subsequent chapters of the book.

Second, a variety of important models and problems from stochastic geometry will be reviewed. Among these are the Boolean model, random geometric graphs, intersection processes of (Poisson) processes of affine subspaces, random mosaics, and random polytopes. We state the most natural problems and point out important new results and directions of current research.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Stochastic geometry is a branch of probability theory which deals with set-valued random elements. It describes the behavior of random configurations such as random graphs, random networks, random cluster processes, random unions of convex sets, random mosaics, and many other random geometric structures. Due to its strong connections to the classical field of stereology, to communication theory, and to spatial statistics it has a large number of important applications.

The connection between probability theory and geometry can be traced back at least to the middle of the eighteenth century when Buffon’s needle problem (1733), and subsequently questions related to Sylvester’s four point problem (1864) and Bertrand’s paradox (1889) started to challenge prominent mathematicians and helped to advance probabilistic modeling. Typically, in these early contributions a fixed number of random objects of a fixed shape was considered and their interaction was studied when some of the objects were moved randomly. For a short historical outline of these early days of Geometric Probability see [104, Chap. 8] and [105, Chap. 1].

Since the 1950s, the framework broadened substantially. In particular, the focus mainly switched to models involving a random number of randomly chosen geometric objects. As a consequence, the notion of a point process started to play a prominent role in this field, which since then was called Stochastic Geometry.

In this chapter we describe some of the classical problems of stochastic geometry, together with their recent developments and some interesting open questions. For a more thorough treatment we refer to the seminal book on “Stochastic and Integral Geometry” by Schneider and Weil [104].

2 Geometric Point Processes

A point process η is a measurable map from some probability space $(\varOmega,\mathcal{A}, \mathbb{P})$ to the locally finite subsets of a Polish space $\mathbb{X}$ (endowed with a suitable σ-algebra), which is the state space . The intensity measure of η, evaluated at a measurable set $A \subset \mathbb{X}$, is defined by $\mu (A) = \mathbb{E}\eta (A)$ and equals the mean number of elements of η lying in A. 32

In many examples considered in this chapter, $\mathbb{X}$ is either $\mathbb{R}^{d}$, the space of compact (convex) subsets of $\mathbb{R}^{d}$, or the space of flats (affine subspaces) of a certain dimension in $\mathbb{R}^{d}$. More generally, $\mathbb{X}$ could be the family $\mathcal{F}(\mathbb{R}^{d})$ of all closed subsets of $\mathbb{R}^{d}$ endowed with the hit-and-miss topology (which yields a compact Hausdorff space with countable basis).

In this section, we start with processes of flats. In the next section, we discuss particle processes in connection with Boolean models.

2.1 Grassmannians and Invariant Measures

Let $\mathbb{X}$ be the space of linear or affine subspaces (flats) of a certain dimension in $\mathbb{R}^{d}$. More specifically, for i ∈ { 0, …, d} we consider the linear Grassmannian

$$\displaystyle{G(d,i) =\{ L\text{ linear subspace of }\mathbb{R}^{d}:\ \text{dim }L = i\}}$$

and the affine Grassmannian

$$\displaystyle{A(d,i) =\{ E\text{ affine subspace of }\mathbb{R}^{d}:\ \text{dim }E = i\}.}$$

These spaces can be endowed with a canonical topology and with a metric inducing this topology. In both cases, we work with the corresponding Borel σ-algebra. Other examples of spaces $\mathbb{X}$ are the space of compact subsets or the space of compact convex subsets of $\mathbb{R}^{d}$. All these spaces are subspaces of $\mathcal{F}(\mathbb{R}^{d})$ and are endowed with the subspace topology.

In each of these examples, translations and rotations act in a natural way on the elements of $\mathbb{X}$ as well as on subsets (point configurations) of $\mathbb{X}$. It is well known and an often used fact that there is—up to normalization—only one translation invariant and locally finite measure on $\mathbb{R}^{d}$, the Lebesgue measure ℓ _d (⋅ ). It is also rotation invariant and normalized in such a way that the unit cube C ^d = [0, 1]^d satisfies ℓ _d (C ^d) = 1.

Analogously, there is only one rotation invariant probability measure on G(d, i), which we denote by ν _i ^d and which by definition satisfies ν _i ^d(G(d, i)) = 1. Observe that ν _d−1 ^d coincides (up to normalization) with (spherical) Lebesgue measure σ ^d on the unit sphere S ^d−1, by identifying a unit vector u ∈ S ^d−1 with its orthogonal complement $u^{\perp } = L \in G(d,d - 1)$. A corresponding remark applies to ν ₁ ^d on G(d, 1) where a unit vector is identified with the one-dimensional linear subspace it spans.

In a similar way, there is—up to normalization—only one rotation and translation invariant measure on A(d, i), the Haar measure μ _i ^d, which is normalized in such a way that $\mu _{i}^{d}(\{E \in A(d,i): E \cap B^{d}\neq \emptyset \}) =\kappa _{d-i}$, where B ^d is the unit ball in $\mathbb{R}^{d}$ and κ _d denotes its volume. Since the space A(d, i) is not compact, its total μ _i ^d-measure is infinite.

It is often convenient to describe the Haar measure μ _i ^d on A(d, i) in terms of the Haar measure ν _i ^d on G(d, i). The relation is

$$\displaystyle{ \mu _{i}^{d}(A) =\int \limits _{ G(d,i)}\int \limits _{L^{\perp }}\mathbb{1}_{A}(L + x)\,\ell_{d-i}(\mathrm{d}x)\,\nu _{i}^{d}(\mathrm{d}L), }$$

(1)

for measurable sets A ⊂ A(d, i). This is based on the obvious fact that each i-flat E ∈ A(d, i) can be uniquely written in the form $E = L + x$ with L ∈ G(d, i) and x ∈ L ^⊥, the orthogonal complement of L. If a locally finite measure μ on A(d, i) is only translation invariant, then it can still be decomposed into a probability measure σ on G(d, i) and, given a direction space L ∈ G(d, i), a translation invariant measure on the orthogonal complement of L, which then coincides up to a constant with Lebesgue measure on L ^⊥. In fact, a more careful argument shows the existence of a constant t ≥ 0 such that

$$\displaystyle{\mu (A) = t\int \limits _{G(d,i)}\int \limits _{L^{\perp }}\mathbb{1}_{A}(L + x)\,\ell_{d-i}(\mathrm{d}x)\,\sigma (\mathrm{d}L),}$$

for all measurable sets A ⊂ A(d, i). In this situation, σ = ν _i ^d if and only if μ is also rotation invariant and therefore μ = μ _i ^d, at least up to a constant factor.

The Haar measures ℓ _d , ν _i ^d, and μ _i ^d are the basis of the most natural constructions of point processes on $\mathbb{X} = \mathbb{R}^{d},G(d,i)$ and A(d, i), if some kind of invariance is involved.

2.2 Stationary Point Processes

Next we describe point processes on these spaces in a slightly more formal way than at the beginning of this section and refer to [71] for a general detailed introduction. A point process (resp. simple point process) η on $\mathbb{X}$ is a measurable map from the underlying probability space $(\varOmega,\mathcal{A}, \mathbb{P})$ to the set of locally finite (resp. locally finite and simple) counting measures $\mathbf{N}(\mathbb{X})$ (resp., $\mathbf{N}_{s}(\mathbb{X})$) on $\mathbb{X}$, which is endowed with the smallest σ-algebra, so that the evaluation maps ω ↦ η(ω)(A) are measurable, for all Borel sets $A \subset \mathbb{X}$. For $z \in \mathbb{X}$, let δ _z denote the unit point measure at z. It can be shown that a point process can be written in form

$$\displaystyle{\eta =\sum _{ i=1}^{\tau }\delta _{ \zeta _{i}},}$$

where τ is a random variable taking values in $\mathbb{N}_{0} \cup \{\infty \}$ and ζ ₁, ζ ₂, … is a sequence of random points in $\mathbb{X}$. In the following, we will only consider simple point processes, where ζ _i ≠ ζ _j for i ≠ j. If η is simple and identifying a simple measure with its support, we can think of η as a locally finite random set $\eta =\{\zeta _{i}: i = 1,\ldots,\tau \}$.

Taking the expectation of η yields the intensity measure

$$\displaystyle{\mu (A) = \mathbb{E}\eta (A)}$$

of η. As indicated above, the most convenient point processes from a geometric point of view are those where the intensity measure equals the Haar measure, or at least a translation invariant measure, times a constant t > 0, the intensity of the point process. If we refer to this setting, we write η _t and μ _t to emphasize the dependence on the intensity t. In the following, we make this precise under the general assumption that the intensity measure is locally finite. As usual we say that a point process η is stationary if any translate of η by a fixed vector has the same distribution as the process η.

Let us discuss the consequences of the assumptions of stationarity or some additional distributional invariance in some particular cases. If η is a stationary point process on $\mathbb{X} = \mathbb{R}^{d}$, then μ _t (A) = t ℓ _d (A) for all Borel sets $A \subset \mathbb{R}^{d}$. Clearly, this measure is also rotation invariant.

Furthermore, if η is a stationary flat process on $\mathbb{X} = A(d,i)$ and $A \subset \mathbb{R}^{d}$ is a Borel set, we set [A] = { E ∈ A(d, i): E ∩ A ≠ ∅}. Then the number of i-flats of the process meeting A is given by η([A]) and its expectation can be written as

$$\displaystyle{\mu _{t}([A]) = t\int \limits _{G(d,i)}\int \limits _{L^{\perp }}\mathbb{1}_{[A]}(L + x)\,\ell_{d-i}(\mathrm{d}x)\,\sigma (\mathrm{d}L),}$$

where σ is a probability measure on G(d, i) and t ≥ 0 is the intensity. This follows from what we said in the previous subsection, since the intensity measure is translation invariant by the assumption of stationarity of η. Here, the indicator function $\mathbb{1}_{[A]}(L + x)$ equals 1 if and only if x is in the orthogonal projection A | L ^⊥ of A to L ^⊥. Thus

$$\displaystyle{\mu _{t}([A]) = t\int \limits _{G(d,i)}\ell_{d-i}(A\vert L^{\perp })\,\sigma (\mathrm{d}L).}$$

A special situation arises if η is also isotropic (its distribution is rotation invariant). In this case and for a convex set A, the preceding formula can be expressed as an intrinsic volume, which will be introduced in the next section.

2.3 Tools from Convex Geometry

We work in the d-dimensional Euclidean space $\mathbb{R}^{d}$ with Euclidean norm $\|x\| = \sqrt{\langle x, x\rangle }$, unit ball B ^d and unit sphere S ^d−1. The set of all convex bodies, i.e., compact convex sets in $\mathbb{R}^{d}$, is denoted by $\mathcal{K}^{d}$. The Hausdorff distance between two sets A, B is defined as $d_{H}(A,B) =\inf \{\varepsilon \geq 0:\, A \subset B +\varepsilon B^{d}\text{ and }B \subset A +\varepsilon B^{d}\}$ where “+” denotes the usual vector or Minkowski addition. When equipped with the Hausdorff distance, $\mathcal{K}^{d}$ is a metric space. The elements of the convex ring $\mathcal{R}^{d}$ are the polyconvex sets, which are defined as finite unions of convex bodies.

If Lebesgue measure is applied to elements of $\mathcal{K}^{d}$, we usually write V _d instead of ℓ _d . Using the Minkowski addition on $\mathcal{K}^{d}$, we can define the surface area of a convex body by

$$\displaystyle{\lim _{\varepsilon \rightarrow 0+}\frac{V _{d}(K + \varepsilon B^{d}) - V _{d}(K)} {\varepsilon }.}$$

Classical results in convex geometry imply that the limit exists. The mean width of a convex body K is the mean length of the projection K | L of the set onto a uniform random line L through the origin,

$$\displaystyle{\int \limits _{G(d,1)}V _{1}(K\vert L)\,\nu _{1}^{d}(\mathrm{d}L).}$$

These two quantities, which describe natural geometric properties of convex bodies, are just two examples of a sequence of characteristics associated with convex bodies.

2.3.1 Intrinsic Volumes

More generally, we now introduce intrinsic volumes V _i of convex bodies, $i = 1,\ldots,d$. These can be defined through the Steiner formula which states that, for any convex body $K \in \mathcal{K}^{d}$, the volume of K + ɛ B ^d is a polynomial in ɛ ≥ 0 of degree d. The intrinsic volumes are the suitably normalized coefficients of this polynomial, namely,

$$\displaystyle{V _{d}(K + \varepsilon B^{d}) =\sum _{ i=0}^{d}\kappa _{ i}V _{d-i}(K)\varepsilon ^{i},\qquad \varepsilon \geq 0,}$$

where κ _i is the volume of the i-dimensional unit ball. Clearly, the functional 2V _d−1 is the surface area, V ₁ is a multiple of the mean width functional, and V ₀ corresponds to the Euler characteristic.

The intrinsic volumes V _i are translation and rotation invariant, homogeneous of degree i, monotone with respect to set inclusion, and continuous with respect to the Hausdorff distance. The intrinsic volumes are additive functionals , also called valuations, which means that

$$\displaystyle{V _{i}(K \cup L) + V _{i}(K \cap L) = V _{i}(K) + V _{i}(L)}$$

whenever $K,L,K \cup L \in \mathcal{K}^{d}$. Moreover, it is a convenient feature of the intrinsic volumes that for $K \subset \mathbb{R}^{d} \subset \mathbb{R}^{N}$ the value V _i (K) is independent of the ambient space, $\mathbb{R}^{d}$ or $\mathbb{R}^{N}$, in which it is calculated. In particular, for L ∈ G(d, 1) the intrinsic volume V ₁(K | L) is just the length of K | L.

A famous theorem due to Hadwiger (see [104, Sect. 14.4]) states that the intrinsic volumes can be characterized by these properties. If μ is a translation and rotation invariant, continuous valuation on $\mathcal{K}^{d}$, then

$$\displaystyle{\mu =\sum _{ i=0}^{d}c_{ i}V _{i}}$$

with some constants $c_{0},\ldots,c_{d} \in \mathbb{R}$ depending only on μ. If in addition μ is homogeneous of degree i, then μ = c _i V _i . To give a simple example for an application of Hadwiger’s theorem, observe that the mean projection volume

$$\displaystyle{\int \limits _{G(d,i)}\ell_{d-i}(K\vert L^{\perp })\,\nu _{ i}^{d}(\mathrm{d}L)}$$

of a convex body K to a uniform random (d − i)-dimensional subspace defines a translation invariant, rotation invariant, monotone and continuous valuation of degree d − i. Hence, up to a constant factor (independent of K), it must be equal to V _d−i (K). This yields Kubota’s formula

$$\displaystyle{V _{d-i}(K) = c_{d,i}\int \limits _{G(d,i)}\ell_{d-i}(K\vert L^{\perp })\,\nu _{ i}^{d}(\mathrm{d}L),}$$

with certain constants c _d, i which can be determined by comparing both sides for K = B ^d. This formula explains why the intrinsic volumes are often encountered in stereological or tomographic investigations and are also called “Quermassintegrals” , which is the German name for an integral average of sections or projections of a body.

Applications to stochastic geometry require an extension of intrinsic volumes to the larger class of polyconvex sets. Requiring such an extension to be additive on $\mathcal{R}^{d}$ suggests to define the intrinsic volumes of polyconvex sets by an inclusion–exclusion formula. The fact that this is indeed possible can be seen from a result due to Groemer [38], [104, Theorem 14.4.2], which says that any continuous valuation on $\mathcal{K}^{d}$ has an additive extension to $\mathcal{R}^{d}$. Volume and surface area essentially preserve their interpretation for the extended functionals and also Kubota’s formula remains valid for all intrinsic volumes. On the other hand, continuity with respect to the Hausdorff metric is in general not available on $\mathcal{R}^{d}$.

2.3.2 Mixed Volumes and Area Measures

The Steiner formula can be extended in different directions. Instead of considering the volume of the Minkowski sum of a convex body and a ball, more generally, the volume of a Minkowski combination of finitely many convex bodies $K_{1},\ldots,K_{k} \in \mathcal{K}^{d}$ can be taken. In this case, $V _{d}(\lambda _{1}K_{1} +\ldots +\lambda _{k}K_{k})$ is a homogeneous polynomial in λ ₁, …, λ _k  ≥ 0 of degree d, whose coefficients are nonnegative functionals of the convex bodies involved (see [101, Chap. 5.1]), which are called mixed volumes. We mention only the special case k = 2,

$$\displaystyle{V _{d}(\lambda _{1}K_{1} +\lambda _{2}K_{2}) =\sum _{ i=0}^{d}\binom{d}{i}\lambda _{ 1}^{i}\lambda _{ 2}^{d-i}V (K_{ 1}[i],K_{2}[d - i]);}$$

the bracket notation K[i] means that K enters with multiplicity i. In particular, for $K,L \in \mathcal{K}^{d}$ we thus get

$$\displaystyle{d \cdot V (K[d - 1],L) =\lim _{\varepsilon \rightarrow 0+}\frac{V _{d}(K + \varepsilon L) - V _{d}(K)} {\varepsilon },}$$

which provides an interpretation of the special mixed volume V (K[d − 1], L) as a relative surface area of K with respect to L. In particular, d ⋅ V (K[d − 1], B ^d) is the surface area of K. The importance of these mixed functionals is partly due to sharp geometric inequalities satisfied by them. For instance, Minkowski’s inequality (see [101, Chap. 7.2]) states that

$$\displaystyle{ V (K[d - 1],L)^{d} \geq V _{ d}(K)^{d-1}V _{ d}(L). }$$

(2)

If K, L are d-dimensional, then (2) holds with equality if and only if K and L are homothetic. Note that the very special case L = B ^d of this inequality is the classical isoperimetric inequality for convex sets.

Although Minkowski’s inequality is sharp, it can be strengthened by taking into account that the left side is strictly larger than the right side if K and L are not homothetic. Quantitative improvements of (2) which introduce an additional factor (1 + f(d(K, L)) on the right-hand side, with a nonnegative function f and a suitable distance d(K, L), are extremely useful and are known as geometric stability results.

A second extension is obtained by localizing the parallel sets involved in the Steiner formula. For a given convex body K, this leads to a sequence of Borel measures S _j (K, ⋅ ), $j = 0,\ldots,d - 1$, on S ^d−1, the area measures of the convex body K. The top order area measure S _d−1(K, ⋅ ) can be characterized via the identity

$$\displaystyle{d \cdot V (K[d - 1],L) =\int \limits _{S^{d-1}}h(L,u)\,S_{d-1}(K,\mathrm{d}u),}$$

which holds for all convex bodies $K,L \in \mathcal{K}^{d}$, and where

$$\displaystyle{h(L,u):=\max \{\langle x,u\rangle: x \in L\},\qquad u \in \mathbb{R}^{d},}$$

defines the support function of L . Moreover, for any Borel set ω ⊂ S ^d−1 we have

$$\displaystyle{S_{d-1}(K,\omega ) = \mathcal{H}^{d-1}(\{x \in \partial K:\langle x,u\rangle = h(K,u)\text{ for some }u \in \omega \}),}$$

where $\mathcal{H}^{d-1}$ denotes the (d − 1)-dimensional Hausdorff measure. Further extensions and background information are provided in [101] and summarized in [104].

3 Basic Models in Stochastic Geometry

3.1 The Boolean Model

The Boolean model , which is also called Poisson grain model [41], is a basic benchmark model in spatial stochastics. Let $\xi _{t} =\sum _{ i=1}^{\infty }\delta _{x_{i}}$ denote a stationary Poisson point process in $\mathbb{R}^{d}$ with intensity t > 0. By $\mathcal{K}_{0}^{d}$ we denote the set of all convex bodies $K \in \mathcal{K}^{d}$ for which the origin is the center of the circumball. Let $\mathbb{Q}$ denote a probability distribution on $\mathcal{K}_{0}^{d}$, and let Z ₁, Z ₂, … be an i.i.d. sequence of random convex bodies (particles) which are also independent of ξ _t . If we assume that

$$\displaystyle{ \int \limits _{\mathcal{K}_{0}^{d}}V _{j}(K)\,\mathbb{Q}(\mathrm{d}K) < \infty }$$

(3)

for j = 1, …, d, then

$$\displaystyle{Z =\bigcup _{ i=1}^{\infty }(Z_{ i} + x_{i})}$$

is a stationary random closed set, the Boolean model with grain (or shape) distribution $\mathbb{Q}$ and intensity t > 0. Alternatively, one can start from a stationary point process (particle process) η _t on $\mathcal{K}^{d}$. Then the intensity measure $\mu _{t} = \mathbb{E}\eta _{t}$ of η _t is a translation invariant measure on $\mathcal{K}^{d}$ which can be decomposed in the form

$$\displaystyle{\mu _{t}(\cdot ) = t\int \limits _{\mathcal{K}_{0}^{d}}\int \limits _{\mathbb{R}^{d}}\mathbb{1}\{K + x \in \cdot \}\,\ell_{d}(\mathrm{d}x)\,\mathbb{Q}(\mathrm{d}K).}$$

The Poisson particle process η _t is locally finite if and only if its intensity measure μ _t is locally finite, which is equivalent to (3). We obtain again the Boolean model by taking the union of the particles of η _t , that is,

$$\displaystyle{Z = Z(\eta _{t}) =\bigcup _{K\in \eta _{t}}K.}$$

In order to explore a Boolean model Z, which is observed in a window $W \in \mathcal{K}^{d}$, it is common to consider the values of suitable functionals of the intersection Z ∩ W as the information which is available. Due to the convenient properties and the immediate interpretation of the intrinsic volumes V _i , i ∈ { 0, …, d}, for convex bodies, it is particularly natural to study the random variables V _i (Z ∩ W), i ∈ { 0, …, d}, or to investigate random vectors composed of these random elements. From a practical viewpoint, one aims at retrieving information about the underlying particle process, that is, its intensity and its shape distribution, from such observations.

3.1.1 Mean Values

Let Z ₀ be a random convex body having the same distribution as Z _i , $i \in \mathbb{N}$, which is called the typical grain. Formulas relating the mean values $\mathbb{E}V _{i}(Z \cap W)$ to the mean values of the typical grain $v_{j} = \mathbb{E}V _{j}(Z_{0})$, j ∈ { 0, …, d}, have been studied for a long time. Particular examples of such relations are

$$\displaystyle\begin{array}{rcl} \mathbb{E}V _{d}(Z \cap W)& =& V _{d}(W)\left (1 - e^{-tv_{d} }\right ), {}\\ \mathbb{E}V _{d-1}(Z \cap W)& =& V _{d}(W)tv_{d-1}e^{-tv_{d} } + V _{d-1}(W)\left (1 - e^{-tv_{d} }\right ). {}\\ \end{array}$$

If r(W) denotes the radius of the inball of W, we deduce from these relations that

$$\displaystyle\begin{array}{rcl} \lim _{r(W)\rightarrow \infty }\frac{\mathbb{E}V _{d}(Z \cap W)} {V _{d}(W)} & =& 1 - e^{-tv_{d} }, {}\\ \lim _{r(W)\rightarrow \infty }\frac{\mathbb{E}V _{d-1}(Z \cap W)} {V _{d}(W)} & =& tv_{d-1}e^{-tv_{d} }, {}\\ \end{array}$$

where the first limit is redundant and equal to $p = \mathbb{P}(o \in Z) = \mathbb{E}V _{d}(Z \cap W)/V _{d}(W)$, the volume fraction of the stationary random closed set Z. For the other intrinsic volumes V _i , i ∈ { 0, …, d − 2}, the mean values $\mathbb{E}V _{i}(Z \cap W)$ of the Boolean model Z can still be expressed in terms of the intensity and mean values of the typical grain, but the relations are more complicated and in general they involve mixed functionals of translative integral geometry. The formulas simplify again if Z is additionally assumed to be isotropic (if Z ₀ is isotropic). For a stationary and isotropic Boolean model, all mean values $\mathbb{E}V _{i}(Z \cap W)$ can be expressed in terms of the volume fraction p and a polynomial function of tv _i , …, tv _d . Moreover, the limits

$$\displaystyle{\delta _{i}:=\lim _{r(W)\rightarrow \infty }\frac{\mathbb{E}V _{i}(Z \cap W)} {V _{d}(W)} }$$

exist and are called the densities of the intrinsic volumes for the Boolean model. The system of equations which relates these densities to the (intensity weighted) mean values tv ₀, …, tv _d can be used to express the latter in terms of the densities δ ₀, …, δ _d of the Boolean model.

3.1.2 Covariances

While such first order results (involving mean values) have been studied for quite some time (see [104] for a detailed description), variances and covariances of arbitrary intrinsic volumes (or of more general functionals) of Boolean models have been out of reach until recently. In [58], second order information for functionals of the Boolean model is derived systematically under optimal moment assumptions. To indicate some of these results, we define for i, j ∈ { 0, …, d}

$$\displaystyle{ \sigma _{i,j} =\lim _{r(W)\rightarrow \infty }\frac{\mathrm{Cov}\left (V _{i}(Z \cap W),V _{j}(Z \cap W)\right )} {V _{d}(W)} }$$

(4)

as the asymptotic covariances of the stationary Boolean model Z, provided the limit exists. The following results are proved in [58] and ensure the existence of the limit under minimal assumptions. Note that condition (3) is equivalent to $\mathbb{E}V _{i}(Z_{0}) < \infty$ for i = 1, …, d.

Theorem 1

Assume that $\mathbb{E}V _{i}(Z_{0})^{2} < \infty$ for i ∈{ 1,…,d}.

• (1) Then σ _i,j is finite and independent of W for all i,j ∈{ 0,…,d}. Moreover, σ _i,j can be expressed as an infinite series involving the intensity t and integrations with respect to the grain distribution $\mathbb{Q}$ and the intensity measure μ of η _t .

• (2) The asymptotic covariance matrix is positive definite if Z ₀ has nonempty interior with positive probability.

• (3) If even $\mathbb{E}V _{i}(Z_{0})^{3} < \infty$ for i ∈{ 0,…,d}, then the rate of convergence in (4) is of the (optimal) order 1∕r(W).

A more general result is obtained in [58], which applies to arbitrary translation invariant, additive functionals which are locally bounded and measurable (geometric functionals). Further examples of such functionals are mixed volumes and certain integrals of area measures. The basic ingredients in the proof are the Fock space representation of Poisson functionals as developed in [73] (see also the contribution by Günter Last in this volume) and new integral geometric bounds for geometric functionals.

For an isotropic Boolean model, the infinite series representation for σ _i, j can be reduced to an integration with respect to finitely many curvature based moment measures of the typical grain Z ₀. As a basic example, which does not require Z to be isotropic, we mention (assuming a full-dimensional typical grain Z ₀) that

$$\displaystyle\begin{array}{rcl} \sigma _{d-1,d}& =& -e^{-2tv_{d} }tv_{d-1}\int \left (e^{tC_{d}(x)} - 1\right )\,\ell_{ d}(\mathrm{d}x) {}\\ & & +e^{-2tv_{d} }t\int e^{tC_{d}(x-y)}\,M_{ d-1,d}(\mathrm{d}(x,y)), {}\\ \end{array}$$

where $C_{d}(x) = \mathbb{E}[V _{d}(Z_{0} \cap (Z_{0} + x))]$, for $x \in \mathbb{R}^{d}$, defines the mean covariogram of the typical grain and

$$\displaystyle{M_{d-1,d}(\cdot ):= \frac{1} {2}\mathbb{E}\int \limits _{Z_{0}}\int \limits _{\partial Z_{0}}\mathbb{1}\{(x,y) \in \cdot \}\,\mathcal{H}^{d-1}(\mathrm{d}x)\,\ell_{ d}(\mathrm{d}y)}$$

is a mixed moment measure of the typical grain. A formula for the asymptotic covariance $\sigma _{d-1,d-1}$ is already contained in [42]. For a stationary and isotropic Boolean model in the plane $\mathbb{R}^{2}$, explicit formulas are provided in [58] for all covariances involving the Euler characteristic σ _0, 0, σ _0, 1, σ _0, 2. Moreover, again in general dimensions and for a stationary Boolean model whose typical grain is a deterministic ball, some of these formulas can be specified even further and used to plot the covariances as a function of the intensity. It is an interesting task to interpret these plots and to determine rigorously the analytic properties (e.g., zeros, extremal values) or the asymptotic behavior of the covariances and correlation functions for increasing intensity.

In addition, in [58] univariate and multivariate central limit theorems, including rates of convergence, are derived from general new results on the normal approximation of Poisson functionals via the Malliavin–Stein method [81, 82]. For these we refer to the survey [17], in this volume. Again these results are established for quite general geometric functionals, employing also tools from integral geometry. Some of these results do not require stationarity of the Boolean model or translation invariance of the functionals.

3.2 Random Geometric Graphs

Random graphs play an important role in graph theory since Renyi introduced his famous random graph model. Since then several models of random graphs have been investigated. The use of random graphs as a natural model for telecommunication networks (see, e.g., Zuyev’s survey in [115]) gave rise to additional investigations. Here we concentrate on random graphs with a geometric construction rule.

The most natural and best investigated graph is the so-called Gilbert graph. Let η _t be a Poisson point process on $\mathbb{R}^{d}$ with an intensity measure of the form μ _t (⋅ ) = t ℓ _d (⋅ ∩ W), where $W \subset \mathbb{R}^{d}$ is a compact convex set with ℓ _d (W) = 1. Let (δ _t : t > 0) be a sequence of positive real numbers such that δ _t  → 0 as t → ∞. The Gilbert graph, or random geometric graph, is obtained by taking the points of η _t as vertices and by connecting two distinct points x, y ∈ η _t by an edge if and only if $\|x - y\| \leq \delta _{t}$. There is a vast literature on the Gilbert graph and one should have a look at the seminal book [83] by Penrose or check the recent paper by Reitzner et al. [93] for further references. For natural generalizations one replaces the role of the norm by a suitable symmetric function $G:\, \mathbb{R}^{d} \rightarrow [0,1]$, where two points of η _t are connected with probability G(y − x). An important particular case is when G is the indicator function of a symmetric set. Recent developments in this direction are due to Bourguin and Peccati [16], and Lachièze-Rey and Peccati [66, 67].

Denote by $\mathcal{G} = (\mathcal{V},\mathcal{E})$ the resulting graph where $\mathcal{V} =\eta _{t}$ are the vertices and $\mathcal{E}\subset \eta _{t,\neq }^{2}$ are the occurring edges. Objects of interest are clearly the number of edges N _t and, more general, functions of the edge lengths

$$\displaystyle{\sum _{(x,y)\in \mathcal{E}}g(\|y - x\|).}$$

In particular, one is interested in the edge length powers

$$\displaystyle{L_{t}^{(\alpha )} = \frac{1} {2}\sum _{(x,y)\in \eta _{t,\neq }^{2}}\mathbb{1}\{\|x - y\| \leq \delta _{t}\}\,\|x - y\|^{\alpha }.}$$

Clearly L _t ⁽⁰⁾ = N _t . It is well known that for any α > −d

$$\displaystyle{\mathbb{E}L_{t}^{(\alpha )} = \frac{d\kappa _{d}} {2(\alpha +d)}t^{2}\delta _{ t}^{\alpha +d}V _{ d}(W)(1 + O(\delta _{t}))\,.}$$

This especially shows that the number of edges of the Gilbert graph is of order t ² δ _t ^d, whereas its total edge length is of order t ² δ _t ^d+1. The asymptotic variance is given by

$$\displaystyle{\mathrm{Var}L_{t}^{(\alpha )} = \left ( \frac{d\,\kappa _{d}} {2\,(2\alpha + d)}\,t^{2}\,\delta _{ t}^{2\alpha +d} + \frac{d^{2}\,\kappa _{ d}^{2}} {(\alpha +d)^{2}}\,t^{3}\,\delta _{ t}^{2\alpha +2d}\right )V _{ d}(W)(1 + O(\delta _{t})),}$$

and the asymptotic covariance matrix is computed in [93].

Many investigations benefit from the fact that these functions are Poisson U-statistics of order 2, and thus are perfectly suited to apply the Wiener–Itô chaos expansion, Malliavin calculus and Stein’s method. We refer to [91] and [69] (in this volume) for more details. There limit theorems are stated and more recent developments are pointed out.

Questions of interest not mentioned in the current notes concern for instance percolation problems. For recent developments in this context, we refer, e.g., to the recent book by Haenggi [40].

3.2.1 Random Simplicial Complexes

A very recent line of research is based on the use of random geometric graphs for constructing random simplicial complexes. For instance, given the Gilbert graph of a Poisson point process η _t , we construct the Vietoris–Rips complex R(δ _t ) by calling $F =\{ x_{i_{1}},\ldots,x_{i_{k+1}}\}$ a k-face of R(δ _t ) if all pairs of points in F are connected by an edge in the Gilbert graph. This results in a random simplicial complex, and it is particularly interesting to investigate its combinatorial and topological structure.

For example, counting the number N _t ^(k) of k-faces is equivalent to a particular subgraph counting. By definition this is a U-statistic given by

$$\displaystyle{N_{t}^{(k)} = N_{ t}^{(k)}(W,\delta _{ t}) = \frac{1} {(k + 1)!}\sum _{(x_{1},\ldots,x_{k+1})\in \eta _{t,\neq }^{k+1}}\mathbb{1}\{\|x_{i}-x_{j}\| \leq \delta _{t},\ \forall 1 \leq i,j \leq k+1\}.}$$

Using the Slivnyak–Mecke theorem (see [104, Sect. 3.2]), the expectation of N _t ^(k) can be computed. Central limit theorems and a concentration inequality follow from results for local U-statistics. A particularly tempting problem is the asymptotic behavior of the Betti-numbers of this random simplicial complex. We refer to [29, 60, 62, 69] and to the recent survey article by Kahle [61] for further information.

3.3 Poisson Processes on Grassmannians

Let η _t be a Poisson process on the space A(d, i) of affine i-flats with a σ-finite intensity measure μ _t  = t μ ₁, t > 0. Assume in particular that μ _t is absolutely continuous with respect to the Haar measure μ _i ^d on A(d, i). This implies that two subspaces L ₁, L ₂ ∈ η _t, ≠ ² are almost surely in general position. If 2i < d the intersection L ₁ ∩ L ₂ is almost surely empty and of interest is the linear hull of the subspace parallel to L ₁ and L ₂, which is of dimension 2i with probability one. If 2i ≥ d, then the dimension of the linear hull of the subspace parallel to L ₁ and L ₂ is d and of interest is the intersection L ₁ ∩ L ₂, which is an affine subspace of dimension 2i − d with probability one.

Crucial in all the following results mentioned for both cases is the fact that the functionals of interest are Poisson U-statistics and thus admit a finite chaos expansion. This makes it particularly tempting to use methods from the Malliavin calculus for proving distributional results.

3.3.1 Intersection Processes of Poisson Flat Processes

Starting from a stationary process η _t of i-flats in $\mathbb{R}^{d}$ with $d/2 \leq i \leq d - 1$, we obtain for given $k \leq d/(d - i)$ a stationary process η _t ^(k) of $[ki - (k - 1)d]$-flats by taking the intersection of any k flats from η _t whose intersection is of the correct dimension. If η _t is Poisson, then the intensity t ^(k) and the directional distribution σ ^(k) of this k-fold intersection process η _t ^(k) of η _t can be related to the intensity t and the directional distribution σ of η _t by

$$\displaystyle{t^{(k)}\sigma ^{(k)}(\cdot ) = \frac{t^{k}} {k!}\int \limits _{A(d,i)}\ldots \int \limits _{A(d,i)}\mathbb{1}\{L_{1} \cap \ldots \cap L_{k} \in \cdot \}[L_{1},\ldots,L_{k}]\,\sigma (\mathrm{d}L_{k})\ldots \sigma (\mathrm{d}L_{1}),}$$

where the subspace determinant [L ₁, …, L _k ] is defined as the k(d − i)-dimensional volume of the parallelepiped spanned by orthonormal bases of L ₁ ^⊥, …, L _k ^⊥. Natural questions which arise at this point are the following:

• For which choice of σ will t ^(k) be maximal if t is fixed?

• Are t and σ uniquely determined by the intersectional data t ^(k) and σ ^(k)?

• If uniqueness holds, is there a stability result as well? That is, are t σ and $\hat{t}\hat{\sigma }$ close to each other (in a quantitative sense) if t ^(k) σ ^(k) and $\hat{t}^{(k)}\hat{\sigma }^{(k)}$ are close?

For further information on this topic, see Sect. 4.4 in [104].

Since in applications the intersection process can only be observed in a convex window W, one is in particular interested in the sum of their j-th intrinsic volumes given by

$$\displaystyle{\varPhi _{t} = \frac{1} {k!}\sum _{(L_{1},\mathop{\ldots },L_{k})\in \eta _{t,\neq }^{k}}V _{j}(L_{1} \cap \mathop{\ldots } \cap L_{k} \cap W)}$$

for $j = 0,\ldots,d - k(d - i)$. The fact that the summands in the definition of Φ _t are bounded and have a bounded support ensures that the sum exists.

The expectation of Φ _t can be calculated using the Slivnyak–Mecke theorem, which yields

$$\displaystyle{\mathbb{E}\varPhi _{t} = \frac{1} {k!}t^{k}\int \ldots \int V _{ j}(L_{1} \cap \mathop{\ldots } \cap L_{k} \cap W)\,\mu _{1}(\mathrm{d}L_{1})\ldots \mu _{1}(\mathrm{d}L_{k}).}$$

If μ _t is also translation invariant this leads to the question to determine certain chord power integrals of the observation window W or more general integrals involving powers of the intrinsic volumes of intersections L ∩ W where L is an affine subspace.

Recent contributions deal with variances and covariances, multivariate central limit theorems [74] (see also [69]), and the distribution of the m-smallest intersection [108]. For further detailed investigations we refer to the recent contribution by Hug et al. [59].

3.3.2 Proximity of Poisson Flat Processes

A different situation arises if we consider a stationary process of i-flats in $\mathbb{R}^{d}$ with 1 ≤ i < d∕2. In this case, generically we expect that any two different i-flats L ₁, L ₂ ∈ η _t are disjoint. A natural way to investigate the geometric situation in this setting is to study the distances between disjoint pairs of i-dimensional flats, or more generally to consider the proximity functional.

We associate with such a pair (L ₁, L ₂) ∈ η _t, ≠ ² (in general position) a unique pair of points x ₁ ∈ L ₁ and x ₂ ∈ L ₂ such that $\|x_{1} - x_{2}\|$ equals the distance between L ₁ and L ₂. This gives rise to a process of triples (m(L ₁, L ₂), d(L ₁, L ₂), L(L ₁, L ₂)), where $m(L_{1},L_{2}):= (x_{1} + y_{2})/2$ is the midpoint, $d(L_{1},L_{2}):=\| x_{1} - x_{2}\|$ is the distance, and L(L ₁, L ₂) ∈ G(d, 1) is the subspace spanned by the vector x ₁ − x ₂.

The stationary process of midpoints and its intensity have been studied in [97] for a Poisson process (see also Sect. 4.4 in [104]), and more recently in [109]. Assume that η _t is a Poisson process on the space A(d, i), $i < \frac{d} {2}$, with intensity measure μ _t  = t μ ₁. The midpoints $m(L_{1},L_{2}) = \frac{1} {2}(x_{1} + x_{2})$ form a point process of infinite intensity, hence we restrict it to the point process

$$\displaystyle{\{m(L_{1},L_{2}):\ d(L_{1},L_{2}) \leq \delta,\ L_{1},L_{2} \in \eta _{t,\neq }^{2}\}}$$

and are interested in the number of midpoints in W, that is,

$$\displaystyle{\varPi _{t} =\varPi _{t}(W,\delta ) = \frac{1} {2}\sum _{(L_{1},L_{2})\in \eta _{t,\neq }^{2}}\mathbb{1}\{d(L_{1},L_{2}) \leq \delta,\,m(L_{1},L_{2}) \in W\}.}$$

The Slivnyak–Mecke formula shows that $\mathbb{E}\varPi _{t}$ is of order t ² δ ^d−2i. Schulte and Thäle [109] proved convergence of the suitably normalized random variable Π _t to a normally distributed variable with error term of order $t^{-\frac{d-i} {2} }$. Moreover, they showed that after suitable rescaling the ordered distances asymptotically form an inhomogeneous Poisson point process on the positive real axis. In [69], the authors add to this a concentration inequality around the median m _t of Π _t which shows that the tails of the distribution are bounded by

$$\displaystyle{\exp \left (-\frac{1} {4} \frac{u} {\sqrt{u + m_{t}}}\right )}$$

for $\frac{u} {\sqrt{u+m_{t}}} \geq e^{2}\sup _{L_{0}\in [W]}\mu _{t}(\{L:\, d(L_{0},L) \leq \delta \})$.

For the process of triples (m(L ₁, L ₂), d(L ₁, L ₂), L(L ₁, L ₂)) a more detailed analysis has been carried out in [59], which also emphasizes the duality of concepts and results as compared to the intersection process (of order k = 2) described before. While the proximity process provides a “dual counterpart” to the intersection process of order two, no satisfactory analogue for intersection processes of higher order is known so far.

3.4 Random Mosaics

Another widely used model of stochastic geometry is that of a random mosaic (tessellation). A deterministic mosaic of Euclidean space $\mathbb{R}^{d}$ is a family of countably many d-dimensional convex bodies $C_{i} \subset \mathbb{R}^{d}$, $i \in \mathbb{N}$, with mutually disjoint interiors, whose union is the whole space and with the property that each compact set intersects only finitely many of the sets. The individual sets of the family, which necessarily are polytopes, are called the cells of the tessellation. It is clear that this concept can be extended in various directions, for instance by dropping the convexity assumption on the cells or by allowing local accumulations of cells, which leads to a more general partitioning of space.

Formally, a random mosaic (tessellation) X in $\mathbb{R}^{d}$ is defined as a simple particle process such that for each realization the collection of all particles constitutes a mosaic. In addition to the cells of the mosaic, the collection of k-dimensional faces of the cells, for each k ∈ { 0, …, d}, provides an interesting geometric object which combines features of a particle process, a random closed set (considering for instance the union set), or a random geometric graph. For example, coloring the cells of the tessellation black or white, independently of each other and independently of X, one can ask for the probability of an infinite black connected component or study the asymptotic behavior of mean values and variances of functionals of the intersection sets Z _B ∩ W, where Z _B denotes the union of the black cells and W is an increasing observation window. For an introduction to such percolation models we refer the reader to [12, 13, 72, 77]. A first systematic investigation of central limit theorems in more general continuous percolation models related to stationary random tessellations is carried out in [78].

3.4.1 Typical Cells and Faces

In the following, we always consider stationary random tessellations X in $\mathbb{R}^{d}$. By stationarity, the intensity measure $\mathbb{E}X$ of X, which we always assume to be locally finite and nonzero, is translation invariant. Let $c: \mathcal{K}^{d} \rightarrow \mathbb{R}^{d}$ denote a center function. By this we mean a measurable function which is translation covariant, that is, $c(K + x) = c(K) + x$ for all $K \in \mathcal{K}^{d}$ and $x \in \mathbb{R}^{d}$. W.l.o.g. we take c(K) to be the center of the circumball, and define $\mathcal{K}_{0}^{d}:=\{ K \in \mathcal{K}^{d}: c(K) = o\}$ as in Sect. 2.3. Then

$$\displaystyle{\mathbb{E}X = t\int \limits _{\mathcal{K}_{0}^{d}}\int \limits _{\mathbb{R}^{d}}\mathbb{1}\{C + x \in \cdot \}\,\ell_{d}(\mathrm{d}x)\,\mathbb{Q}(\mathrm{d}C),}$$

where t > 0 and $\mathbb{Q}$ is a probability measure on $\mathcal{K}_{0}^{d}$ which is concentrated on convex polytopes. A random polytope Z with distribution $\mathbb{Q}$ is called a typical cell of X. This terminology can be justified by Palm theory or in a “statistical sense.” In addition to such a “mean cell” we also consider the cell containing a fixed point in its interior. Because of stationarity, we may choose the origin and hence the zero cell Z ₀ of a given stationary tessellation. Applying the same kind of reasoning to the stationary process X ^(k) of k-faces of X, we are led to the intensity t ^(k) and the distribution $\mathbb{Q}^{(k)}$ of the typical k-face Z ^(k) of X which are determined by

$$\displaystyle{t^{(k)}\mathbb{Q}^{(k)}(\cdot ) = \mathbb{E}\left [\sum _{ F\in X^{(k)}}\mathbb{1}\{c(F) \in B\}\mathbb{1}\{F - c(F) \in \cdot \}\right ],}$$

where $B \subset \mathbb{R}^{d}$ is a Borel set with ℓ _d (B) = 1 and

$$\displaystyle{t^{(k)} = \mathbb{E}\left [\sum _{ F\in X^{(k)}}\mathbb{1}\{c(F) \in B\}\right ].}$$

Let M _k denote a random measure concentrated on the union of the k-faces of X which is given by

$$\displaystyle{M_{k}(\cdot ) =\sum _{F\in X^{(k)}}\mathcal{H}^{k}(\,\cdot \cap F).}$$

Then the distribution of the k-volume weighted typical k-face Z ₀ ^(k) is defined by

$$\displaystyle{ \frac{1} {\mathbb{E}M_{k}(B)}\,\mathbb{E}\int \limits _{B}\mathbb{1}\left \{F_{k}(X^{(k)} - x) \in \cdot \right \}\,M_{ k}(\mathrm{d}x),}$$

where again $B \subset \mathbb{R}^{d}$ is a Borel set with ℓ _d (B) = 1 and F _k (X ^(k) − x) is the $\mathbb{P}$-a.s. unique k-face of X ^(k) − x containing o if x is in the support of M _k . Then, for any nonnegative, measurable function h on convex polytopes, we obtain

$$\displaystyle{ \mathbb{E}h\left (Z_{0}^{(k)} - c(Z_{ 0}^{(k)})\right ) = \frac{\mathbb{E}[h(Z^{(k)}V _{ k}(Z^{(k)})]} {\mathbb{E}[V _{k}(Z^{(k)})]}, }$$

(5)

which also explains why Z ₀ ^(k) is called the volume weighted typical k-face of X. This relation between the two types of typical faces is implied by Neveu’s exchange formula. In the particular case k = d we have Z ₀ ^(d) = Z ₀. Here we followed the presentation in [7, 8, 98, 99].

For general stationary random mosaics it is apparently difficult to establish distributional results. More is known about various mean values and intensities. For instance,

$$\displaystyle{ \sum _{i=0}^{d}(-1)^{i}t^{(i)} = 0 }$$

(6)

is an Euler type relation for the intensities, which points to an underlying general geometric fact (Gram’s relation). If Z _k denotes the union of the k-faces of X (its k-skeleton), then the specific Euler characteristic

$$\displaystyle{\bar{\chi }_{k}:=\lim _{r\rightarrow \infty } \frac{1} {r^{d}}\mathbb{E}\chi (Z_{k} \cap r[0,1]^{d})}$$

exists and satisfies

$$\displaystyle{\bar{\chi }_{k} =\sum _{ i=0}^{k}(-1)^{i}t^{(i)}.}$$

Mean value relations for the mean number of j-faces contained in (or containing) a typical k-faces if j < k (respectively, j ≥ k) or relations for the mean intrinsic volumes of the typical k-faces $t^{(k)}\mathbb{E}V _{j}(Z^{(k)})$ are also known (see [104, Sect. 10.1] for this and related results). More generally, asymptotic mean values and second order properties for functionals of certain colored random mosaics have been investigated in [78].

A different setting is considered in [43]. The starting point is a general stationary ergodic random tessellation in $\mathbb{R}^{d}$. With each cell a random inner structure is associated (for instance, a point pattern, fiber system, or random tessellation) independently of the given mosaic and of each other. Formally, this inner structure is generated by a stationary random vector measure J ₀. In this framework, with respect to an expanding observation window strong laws of large numbers, asymptotic covariances and multivariate central limit theorems are obtained for a normalized functional, which provides an unbiased estimator for the intensity vector of J ₀. Applications to communication networks are then discussed in dimension two under more specific model assumptions involving Poisson–Voronoi and Poisson line tessellations as the frame tessellation as well as the tessellations used for the nesting sequence.

3.4.2 Poisson Hyperplane Mosaics

A hyperplane process η _t in $\mathbb{R}^{d}$ with intensity t > 0 naturally divides $\mathbb{R}^{d}$ into convex polytopes, and the resulting mosaic is called hyperplane mosaic. In the following, we assume that all required intensities are finite (and positive). Let X be the stationary hyperplane mosaic induced by η _t . Let

$$\displaystyle{\frac{d_{j}^{(k)}} {t^{(k)}} =\int V _{j}(K)\,\mathbb{Q}^{(k)}(\mathrm{d}K) = \mathbb{E}V _{ j}(Z^{(k)})}$$

denote the mean j-th intrinsic volume of the typical k-face Z ^(k) of the mosaic X, where t ^(k) is again the intensity of the process of k-faces. We call d _j ^(k) the specific j-th intrinsic volume of the k-face process X ^(k). If n _k, j , for 0 ≤ j ≤ k ≤ d, denotes the mean number of j-faces of the typical k-face, then the relations

$$\displaystyle{ d_{j}^{(k)} = \binom{d - j}{d - k}d^{(\,j)},\qquad t^{(k)} = \binom{d}{k}t^{(0)},\qquad n_{ k,j} = 2^{k-j}\binom{k}{j} }$$

complement the Euler relation (6) valid for any random tessellation (see [104, Theorem 10.3.1]). In the derivation of these facts the property is used that each j-face of X lies in precisely $\binom{d - j}{d - k}$ flats of the (d − k)-fold intersection process η _t, (d−k) and therefore in $2^{k-j}\binom{d - j}{d - k}$ faces of dimension k of X. Further results can be obtained, for instance, if the underlying stationary hyperplane process η _t is Poisson. To prepare this, we observe that the intensity measure of η _t is of the form

$$\displaystyle{ t\int \limits _{S^{d-1}}\int \limits _{\mathbb{R}}\mathbb{1}\{u^{\perp } + xu \in \cdot \}\,\ell_{ 1}(\mathrm{d}x)\,\sigma (\mathrm{d}u), }$$

(7)

where t > 0 and σ is an even probability measure on the unit sphere. Since for $u \in \mathbb{R}^{d}$ the left-hand side of

$$\displaystyle{ \frac{t} {2}\int \limits _{S^{d-1}}\vert \langle u,v\rangle \vert \,\sigma (\mathrm{d}v) =: h(\varPi _{X},u)}$$

is a positively homogeneous convex function (of degree 1), it is the support function of a uniquely defined convex body $\varPi _{X} \in \mathcal{K}^{d}$, which is called the associated zonoid of X. This zonoid can be used to express basic quantities of the mosaic X. For instance, we have

$$\displaystyle{d_{j}^{(k)} = \binom{d - j}{d - k}V _{ d-j}(\varPi _{X}),\qquad t^{(k)} = \binom{d}{k}V _{ d}(\varPi _{X})}$$

(see [104, Theorem 10.3.3]). If X (or η _t ) is isotropic, then Π _X is a ball and these relations are directly expressed in terms of constants and the intensity t.

In [102], Schneider found an explicit formula for the covariances of the total face contents of the typical k-face of a stationary Poisson hyperplane mosaic. Let L _i (P) be the total i-face contents of a polytope $P \subset \mathbb{R}^{d}$, that is,

$$\displaystyle{L_{i}(P) =\sum _{F\in \mathcal{F}_{i}(P)}\mathcal{H}^{i}(F).}$$

The main result is a general new formula for the second moments $\mathbb{E}(L_{r}L_{s})(Z^{(k)})$, which is obtained by an application of the Slivnyak–Mecke formula and clever geometric dissection arguments (refining ideas of R. Miles) in combination with the mean values

$$\displaystyle{\mathbb{E}L_{r}(Z^{(k)}) = \frac{2^{k-r}\binom{k}{r}} {t\binom{d}{r}} V _{d-r}(\varPi _{X}),}$$

which follow from [100]. As a consequence of these formulas and deep geometric inequalities, namely the Blaschke–Santaló inequality and the Mahler inequality for zonoids, he deduced that the variance Var( f ₀(Z ^(k))) is maximal if and only if X is isotropic and minimal if and only if X is a parallel process (involving d fixed directions only). A similar result is obtained for the variance of the volume of the typical cell. In the isotropic case, explicit formulas for these variances and, more generally, for the covariances of the face contents are obtained.

In addition to the typical cell Z = Z ^(d) of a stationary hyperplane tessellation, we consider the almost surely unique cell Z ₀ = Z ₀ ^(d) containing the origin (the zero cell) . One relation between these two random polytopes is given in (5). Another one describes the distribution of the typical cell (where here the highest vertex in a certain admissible direction is chosen as the center function) as the intersection of Z ₀ with a random cone T(H ₁, …, H _d ) generated by d independent random hyperplanes sampled according to a distribution determined by the direction distribution σ of η _t . From this description, one can deduce that up to a random translation, Z is contained in Z ₀ (see Theorem 10.4.7 and Corollary 10.4.1 in [104]).

For the zero cell, mean values of some functionals are explicitly known. For instance,

$$\displaystyle{\mathbb{E}L_{r}(Z_{0}) = 2^{-d}d!V _{ d-r}(\varPi _{X})V _{d}(\varPi _{X}^{\circ }),}$$

where Π _X ^∘ is the polar body of the associated zonoid of X. Choosing r = 0, we get the mean number of vertices, and the choice r = d gives the mean volume of Z ₀. It follows, for instance, that

$$\displaystyle{2^{d} \leq \mathbb{E}f_{ 0}(Z_{0}) \leq d!2^{-d}\kappa _{ d}^{2}}$$

with equality on the left side if X is a parallel process, and with equality on the right side if X is isotropic. A related stability result has been established in [14].

3.4.3 Distributional Results

One of the very few distributional results which are known for hyperplane processes is the following. It involves the inradius r(K) of a convex body K, which is defined as the maximal radius of a ball contained in K. We call a hyperplane process nondegenerate if its directional distribution is not concentrated on any great subsphere.

Theorem 2

Let Z be the typical cell of a stationary mosaic generated by a (nondegenerate) stationary Poisson hyperplane process η _t with intensity t > 0. Then

$$\displaystyle{\mathbb{P}(r(Z) \leq a) = 1 -\exp (-2ta),\qquad a \geq 0.}$$

Clearly r(Z) ≥ a if and only if a ball of radius a is contained in Z. An extension covering more general inclusion probabilities (for homothetic copies of an arbitrary convex body) and typical k-faces has been established in [54, Sect. 4, (9)].

In order to study distributional properties of lower-dimensional typical faces, Schneider [98] showed that for k ∈ { 1, …, d − 1} the distribution of the volume-weighted typical k-face can be described as the intersection of the zero cell with a random k-dimensional linear subspace. To state this result, let η _t denote a stationary Poisson hyperplane process in $\mathbb{R}^{d}$ with intensity measure as given in (7). Further, let t ^(d−k) denote the intensity and σ ^(d−k) the directional distribution (a measure on the Borel sets of G(d, k)) of the intersection process η _t, (d−k) of order d − k of η _t . Both quantities are determined by the relation

$$\displaystyle\begin{array}{rcl} t^{(d-k)}\sigma ^{(d-k)}(\cdot )& =& \frac{t^{d-k}} {(d - k)!}\int \limits _{(S^{d-1})^{d-k}}\mathbb{1}\{u_{1}^{\perp }\cap \ldots \cap u_{ d-k}^{\perp }\in \cdot \} {}\\ & & [u_{1},\ldots,u_{d-k}]\,\sigma ^{d-k}(\mathrm{d}(u_{ 1},\ldots,u_{d-k})), {}\\ \end{array}$$

where [u ₁, …, u _d−k ] denotes the (d − k)-volume of the parallelepiped spanned by u ₁, …, u _d−k .

The next theorem summarizes results from [98, Theorem 1] and from [54, Theorem 1].

Theorem 3

Let X denote the stationary hyperplane mosaic generated by a stationary Poisson hyperplane process η _t . Then the distribution of the volume-weighted typical k-face of X is given by

$$\displaystyle{\mathbb{P}(Z_{0}^{(k)} \in \cdot ) =\int \limits _{ G(d,k)}\mathbb{P}(Z_{0} \cap L \in \cdot )\,\sigma ^{(d-k)}(\mathrm{d}L).}$$

The distribution of the typical k-face equals

$$\displaystyle{\mathbb{P}(Z^{(k)} \in \cdot ) =\int \limits _{ G(d,k)}\mathbb{P}(Z(X \cap L) \in \cdot )\,R_{k}(\mathrm{d}L),}$$

hence it is described in terms of the typical cells of the induced mosaics X ∩ L in k-dimensional subspaces sampled according to the directional distribution

$$\displaystyle{R_{k}(\cdot ) = \frac{V _{d-k}(\varPi _{X})} {\binom{d}{k}V _{d}(\varPi _{X})}\int \limits _{G(d,k)}\mathbb{1}\{L \in \cdot \}V _{k}(\varPi _{X}\vert L)\,\sigma ^{(d-k)}(\mathrm{d}L)}$$

of the typical k-face of X.

These results turned out to be crucial for extending various results for typical (volume-weighted) faces, which had been obtained before for the typical cell (the zero cell).

3.4.4 Large Cells: Kendall’s Problem

Next we turn to Kendall’s problem on the asymptotic shape of the large cells of a stationary but not necessarily isotropic Poisson hyperplane tessellation. The original problem (Kendall’s conjecture) concerned a stationary isotropic Poisson line tessellation in the plane and suggested that the conditional law for the shape of the zero cell Z ₀, given its area V ₂(Z ₀) → ∞, converges weakly to the degenerate law concentrated at the circular shape. Miles [75] provided some heuristic ideas for the proof of such a result and suggested also various modifications. The conjecture was strongly supported by Goldman [34], a first solution came from Kovalenko [64, 65]. Still the approaches of these papers were essentially restricted to the Euclidean plane and made essential use of the isotropy assumption.

The contribution [56] marks the starting point for a sequence of investigations which provide a resolution of Kendall’s problem in a substantially generalized form. To describe the result in some more detail, let η _t be a (nondegenerate) stationary Poisson hyperplane process in $\mathbb{R}^{d}$ with intensity t > 0 and directional distribution σ. In order to find a potential asymptotic shape for the zero cell Z ₀ of the induced Poisson hyperplane tessellation, we first have to exhibit a candidate for such a shape (if it exists), then we have to clarify what we mean by saying that two shapes are close and finally it remains to determine a quantity which should be used instead of the “area” of Z ₀ to measure the size of the zero cell.

Clearly, a natural candidate for a size functional is the volume V _d . The answer to the first question is less obvious, but is based on a strategy that has repeatedly been used in the literature with great success (see [104, Sect. 4.6] for various examples and references). The main idea is to describe the direction distribution σ in geometric terms. This allows one to apply geometric inequalities such as Minkowski’s inequality (2) and its stability improvement, which then can be reinterpreted again in probabilistic terms. Instead of the associated zonoid, for the present problem the Blaschke body associated with η _t , alternatively the direction body B of η _t , turns out to be the right tool. This auxiliary body B is characterized as the unique centered (that is, $B = -B$) d-dimensional convex body $B \in \mathcal{K}^{d}$ such that the area measure of B satisfies $S_{d-1}(B,\cdot ) =\sigma$. The existence and uniqueness of B, for given σ, is a deep result from convex geometry which in its original form is also due to Minkowski (see [101]). Finally, we say that the shape of $K \in \mathcal{K}^{d}$ is close to the shape of B if

$$\displaystyle{r_{B}(K) =\inf \{ s/r - 1: rB + z \subset K \subset sB + z,z \in \mathbb{R}^{d},r,s > 0\}}$$

is small. In particular, r _B (K) = 0 if and only if K and B are homothetic. Let $\mathcal{K}_{(o)}^{d}$ denote the set of all $K \in \mathcal{K}^{d}$ with o ∈ K. For any such K we introduce the constant

$$\displaystyle{\tau =\min \{ t^{-1}\mathbb{E}\eta _{ t}([K]): K \in \mathcal{K}_{(o)}^{d},V _{ d}(K) = 1\}}$$

of isoperimetric type, which can also be expressed in the form

$$\displaystyle{e^{-\tau t} =\max \{ \mathbb{P}(K \subset Z_{ 0}): K \in \mathcal{K}_{(o)}^{d},V _{ d}(K) = 1\}.}$$

The following theorem summarizes Theorems 1 and 2 in [56] and a special case of Theorem 2 in [51]. The latter provides a far reaching generalization of a result in [34] on the asymptotic distribution of the area of the zero cell of an isotropic stationary Poisson line tessellation in the plane.

Theorem 4

Under the preceding assumptions, there is a positive constant c ₀ , depending only on B, such that for every ε ∈ (0,1) and for every interval I = [a,b) with a ^1∕d t ≥ 1,

$$\displaystyle{\mathbb{P}(r_{B}(Z_{0}) \geq \epsilon \mid V _{d}(Z_{0}) \in I) \leq c\exp \left (-c_{0}\epsilon ^{d+1}a^{1/d}t\right ),}$$

where c is a constant depending on B and ε. Moreover,

$$\displaystyle{\lim _{a\rightarrow \infty }a^{-1/d}\ln \mathbb{P}(V _{ d}(Z_{0}) \geq a) = -\tau t.}$$

The same result holds for the typical cell Z.

If the size of Z ₀ is measured by some other intrinsic volume V _i (Z ₀), for i ∈ { 2, …, d − 1}, a similar result is true if η _t is also isotropic (see [57, Theorem 2]). No such result can be expected for the mean width functional V ₁. In fact, no limit shape may exist if size is measured by the mean width, which is proved in [51, Theorem 4] for directional distributions with finite support. Most likely a limit shape does not exist if size is measured by the mean width, but for arbitrary σ or in case of the typical cell this is still an open question. Crucial ingredients in the proofs of the results described so far are geometric stability results, which refine geometric inequalities and the discussion of the equality cases for these inequalities.

3.4.5 A General Framework

The results described so far suggest the general question which size functionals indeed lead to asymptotic or limit shapes and how these asymptotic or limit shapes are determined. A general axiomatic framework for analyzing these questions is developed in [51]. The main object of investigation is a Poisson hyperplane process η _t in $\mathbb{R}^{d}$ (and its induced tessellation) with intensity measure of the form

$$\displaystyle{ \mathbb{E}\eta _{t} = t\int \limits _{S^{d-1}}\int \limits _{0}^{\infty }\mathbb{1}\{H(u,x) \in \cdot \}x^{r-1}\,\ell_{ 1}(\mathrm{d}x)\,\sigma (\mathrm{d}u), }$$

(8)

where t > 0, r ≥ 1, and σ is an even nondegenerate (that is, not concentrated on any great subsphere) probability measure on the Borel sets of the unit sphere. The case r = 1 corresponds to the stationary case. We refer to t as the intensity, r as the distance exponent, and σ as the directional distribution of η _t . Let

$$\displaystyle{\varPhi (K):= t^{-1}\mathbb{E}\eta _{ t}([K]) = \frac{1} {r}\int \limits _{S^{d-1}}h(K,u)^{r}\,\sigma (\mathrm{d}u),\qquad K \in \mathcal{K}_{ (o)}^{d},}$$

which is called the hitting or parameter functional of η _t , since t Φ(K) is the mean number of hyperplanes of η _t hitting K. Moreover, we have

$$\displaystyle{\mathbb{P}(\eta _{t}([K]) = n) = \frac{[\varPhi (K)t]^{n}} {n!} \exp \left (-\varPhi (K)t\right ),\qquad n \in \mathbb{N}_{0},}$$

by the Poisson assumption on η _t .

In Theorem 4 we used the volume functional to bound the size of the zero cell. Many other functionals are conceivable such as the (centered) inradius, the diameter, the width in a given direction, or the largest distance to a vertex of Z ₀. It was realized in [51] that in fact any functional Σ on $\mathcal{K}_{(o)}^{d}$ which satisfies some natural axioms (continuity, homogeneity of a fixed degree k > 0 and monotonicity under set inclusion) qualifies as a size functional. From this it already follows that a general sharp inequality of isoperimetric type is satisfied, that is,

$$\displaystyle{ \varPhi (K) \geq \tau \varSigma (K)^{r/k},\qquad K \in \mathcal{K}_{ (o)}^{d}, }$$

(9)

with a positive constant τ > 0. The convex bodies K for which equality is attained are called extremal. Among the bodies of size Σ(K) = 1 these are precisely the bodies for which

$$\displaystyle{\mathbb{P}(K \subset Z_{0}) \leq e^{-\tau t}}$$

holds with equality (thus maximizing the inclusion probability). The final ingredient required in this general setting, if Φ, Σ are given, is a deviation functional ϑ on $\{K \in \mathcal{K}_{(o)}^{d}:\varSigma (K) > 0\}$, which should be continuous, nonnegative, homogeneous of degree zero, and satisfy ϑ(K) = 0 for some K with Σ(K) > 0 if and only if K is extremal. Then exponential bounds of the form

$$\displaystyle{ \mathbb{P}(\vartheta (Z_{0}) \geq \epsilon \mid \varSigma (Z_{0}) \in [a,b]) \leq c\exp \left (-c_{0}f(\epsilon )a^{r/k}t\right ) }$$

(10)

with a function $f: \mathbb{R}_{+} \rightarrow \mathbb{R}_{+}$ which is positive on (0, ∞), with f(0) = 0, and which satisfies

$$\displaystyle{\varPhi (K) \geq (1 + f(\epsilon ))\tau \varSigma (K)^{r/k}\quad \text{if }\vartheta (K) \geq \epsilon,}$$

are established in [51]. Thus if we know that K has positive distance ϑ(K) from an extremal body, we can again use this information to obtain an improved version of a very general inequality of isoperimetric type. As mentioned before, results of this form are known as stability results. Note that for the choice Σ = Φ, the inequality (9) becomes a tautological identity and all $K \in \mathcal{K}_{(o)}^{d}$ with K ≠ {o} are extremal. Hence, in this case ϑ is identically zero and (10) holds trivially.

Moreover, for the asymptotic distributions of size functionals it is shown that

$$\displaystyle{\lim _{a\rightarrow \infty }a^{-r/k}\ln \mathbb{P}(\varSigma (Z_{ 0}) \geq a) = -\tau t,}$$

thus providing a far reaching extension of the result for the volume functional [51]. The paper [51] contains also a detailed discussion of various specific choices of parameters and functionals which naturally occur in this context and which exhibit a rich variety of phenomena. In the next subsection we point out how this setting extends to Poisson–Voronoi tessellations. In the case of stationary and isotropic Poisson hyperplane tessellations, a similar general investigation is carried out in [52]. Extensions to lower-dimensional faces in Poisson hyperplane mosaics, which are based on the above-mentioned distributional results for k-faces, are considered in [53, 54].

Much less is known about the shape of small cells, although this has also been asked for by Miles [75]. For parallel mosaics in the plane, some work has been done in [10]. Recently, limit theorems for extremes of stationary random tessellations have been explored in [22, 27], but the topic has not been exhaustively investigated so far. In the survey [21], Calka discusses some generalizations of distributional results for the largest centered inball (centered inradius) R _M , the smallest centered circumball (centered circumradius) and their joint distribution, for an isotropic Poisson hyperplane process with distance exponent r ≥ 1. These radii are related to covering probabilities of the unit sphere by random caps. The two-dimensional situation had already been considered in [20]. In particular, Calka points out that after a geometric inversion at the unit sphere and by results available for convex hulls of Poisson point processes in the unit ball (see [23, 24]), the asymptotic behavior of $\mathbb{P}(R_{M} \geq t + t^{\delta }\mid R_{m} = t)$ can be determined for a suitable choice of δ as t → ∞. In addition, L ¹-convergence, a central limit theorem, and a moderate deviation result are available for the number of facets and the volume of Z ₀.

3.4.6 Random Polyhedra

The techniques developed for the solution of Kendall’s problem turned out to be useful also for the investigation of approximation properties of random polyhedra derived from a stationary Poisson hyperplane process η _t with intensity t > 0 and directional distribution σ. Here the basic idea is to replace the zero cell by the K-cell Z _t ^K defined as the intersection of all half-spaces H ⁻ bounded by hyperplanes H ∈ η _t for which K ⊂ H ⁻. Let d _H denote the Hausdorff distance of compact sets in $\mathbb{R}^{d}$, and let K ^y be the convex hull of K and {y}. If the support of the area measure S _d−1(K, ⋅ ) is contained in the support of σ, then

$$\displaystyle{\mathbb{P}(d_{H}(K,Z_{t}^{K}) >\epsilon ) \leq c_{ 1}(\epsilon )\exp \left (-c_{2}t\mu (K,\sigma,\epsilon )\right ),}$$

where c ₁(ɛ), c ₂ are constants and

$$\displaystyle{\mu (K,\sigma,\epsilon ) =\min _{y\in \partial (K+\epsilon B^{d})}\int \limits _{S^{d-1}}[h(K^{y},u) - h(K,u)]\,\sigma (\mathrm{d}u) > 0;}$$

see [55, Theorem1]. Using this bound as a starting point, under various assumptions on the relation between the body K to be approximated and the directional distribution σ of the approximating hyperplane process, almost sure convergence d _H (K, Z _t ^K) → 0 is shown as the intensity t → ∞, including bounds for the speed of convergence. It would be interesting to consider the rescaled sequence

$$\displaystyle{\left (\frac{t} {\log t}\right )^{ \frac{2} {d+1} }d_{H}(K,Z_{t}^{K})}$$

and to obtain further geometric information about the limit, for instance, if σ is bounded from above and from below by a multiple of spherical Lebesgue measure.

3.4.7 Poisson–Voronoi and Delaunay Mosaics

Perhaps the most common and best known tessellation in Euclidean space is the Voronoi tessellation . A Voronoi tessellation arises from a locally finite set $\eta _{t} \subset \mathbb{R}^{d}$ (deterministic or random) of points by associating with each point x ∈ η _t the cell

$$\displaystyle{v_{\eta _{t}}(x):=\{ z \in \mathbb{R}^{d}:\| z - x\|\leqslant \|z - y\|\mbox{ for all }y \in \eta _{ t}\}}$$

with nucleus (center) x. One reason for the omnipresence of Voronoi tessellations is that they are related to a natural growth process starting simultaneously at all nuclei at the same time. If η _t is a stationary Poisson process with intensity t > 0, then the collection of all cells $v_{\eta _{t}}(x)$, x ∈ η _t , is a random tessellation X of $\mathbb{R}^{d}$ which is called Poisson–Voronoi tessellation . The distribution of the typical cell of X is naturally defined by

$$\displaystyle{ \mathbb{Q}(\cdot ):= \frac{1} {t} \mathbb{E}\int \limits _{B}\mathbb{1}\{v_{\eta _{t}}(x) - x \in \cdot \}\,\eta _{t}(\mathrm{d}x), }$$

(11)

where $B \subset \mathbb{R}^{d}$ is an arbitrary Borel set with volume 1. A random polytope Z with distribution $\mathbb{Q}$ is called typical cell of X. An application of the Slivnyak–Mecke theorem shows that the typical cell Z is equal in distribution to $v_{\eta _{t}+\delta _{o}}(o)$, hence Z is stochastically equivalent to the zero cell of a Poisson hyperplane tessellation with generating Poisson hyperplane process given by $Y =\sum _{x\in \eta _{t}}\delta _{H(x)}$, where H(x) is the mid-hyperplane of o and x. It is easy to check that Y is isotropic but nonstationary with intensity measure

$$\displaystyle{ \mathbb{E}Y (\cdot ) = 2^{d}t\int \limits _{ S^{d-1}}\int \limits _{0}^{\infty }\mathbb{1}\{H(u,x) \in \cdot \}\,x^{d-1}\,\ell_{ 1}(\mathrm{d}x)\,\mathcal{H}^{d-1}(\mathrm{d}u), }$$

(12)

where $H(u,x):= u^{\perp } + xu$ is the hyperplane normal to u and passing through xu. Hence, Y perfectly fits into the framework of the parametric class of Poisson hyperplane processes discussed before. This also leads to the following analogue (see [57]) of Theorem 4. To state it, let ϑ(K), for a convex body K containing the origin in its interior, be defined by $\vartheta (K):= (R_{o} - r_{o})/(R_{o} + r_{o})$, where R _o is the radius of the smallest ball with center o containing K and r _o is the radius of the largest ball contained in K and center o.

Theorem 5

Let X be a Poisson–Voronoi tessellation as described above with typical cell Z. Let k ∈{ 1,…,d}. There is a constant c _d , depending only on the dimension, such that the following is true. If ɛ ∈ (0,1) and I = [a,b) (b = ∞ permitted) with a ^d∕k t ≥ 1, then

$$\displaystyle{\mathbb{P}\left (\vartheta (Z) \geq \varepsilon \mid V _{k}(Z) \in I\right ) \leq c_{d,\varepsilon }\,\exp \left (-c_{d}\varepsilon ^{(d+3)/2}a^{d/k}t\right ),}$$

where c _d,ɛ is a constant depending on d and ɛ.

It should be noted that conditioning on the mean width V ₁ is not excluded here. Moreover, asymptotic distributions of the intrinsic volumes of the typical cell can be determined as well. Although in retrospect this follows from the general results in [51], specific geometric stability results have to be established.

The shape of large typical k-faces in Poisson–Voronoi tessellations, with respect to the generalized nucleus as center function, has been explored in [53]. Here large typical faces are assumed to have a large centered inradius. A corresponding analysis for large k-volume seems to be difficult. In this context, the joint distribution of the typical k-face and the typical k-co-radius is described explicitly and related to a Poisson process of k-dimensional halfspaces with explicitly given intensity measure.

The distributional results obtained in [53] complement fairly general distributional properties of stationary Poisson–Voronoi tessellations that have been established by Baumstark and Last [7]. In particular, they describe the joint distribution of the $d - k + 1$ neighbors of the k-dimensional face containing a typical point (i.e., a point chosen uniformly) on the k-faces of the tessellation. Thus they generalize in particular the classical result about the distribution of the typical cell of the Poisson–Delaunay tessellation, which is dual to the given Poisson–Voronoi tessellation. The combinatorial nature of this duality and its consequences are nicely described in [104, Sect. 10.2]. Kendall’s problem for the typical cell in Poisson–Delaunay tessellations is explored in [50] (see also [48]).

3.4.8 High-Dimensional Mosaics and Polytopes

Despite significant progress, precise and explicit information about mean values or even variances and higher moments in stochastic geometry is rather rare. This is one reason why often asymptotic regimes are considered, where the number of points, the intensity of a point process, or the size of an observation window is growing to infinity. On the other hand, high-dimensional spaces are a central and challenging topic which has been explored for quite some time, motivated by intrinsic interest and applications.

Let X be a Poisson–Voronoi tessellation generated by a stationary Poisson point process with intensity t in $\mathbb{R}^{d}$. As before, let Z denote its typical cell. By definition (11), Z contains the origin in its interior. It is not hard to show that $t^{-k} \leq \mathbb{E}[V _{d}(Z)^{k}] \leq k!t^{-k}$, in particular, $\mathbb{E}[V _{d}(Z)] = 1/t$. These bounds are independent of the dimension d. Using a much finer analysis, Alishahi and Sharifitabar [1] showed that

$$\displaystyle{ \frac{c} {t^{2}\sqrt{d}}\left ( \frac{4} {3\sqrt{3}}\right )^{d} \leq \mathrm{ Var}(V _{ d}(Z)) \leq \frac{C} {t^{2}\sqrt{d}}\left ( \frac{4} {3\sqrt{3}}\right )^{d},}$$

where c, C > 0 are absolute constants. In a sense, this suggests that V _d (Z) gets increasingly deterministic. On the other hand, if B ^d(u) is a ball of volume u centered at the origin, then

$$\displaystyle{V _{d}(Z \cap B^{d}(u)) \rightarrow t^{-1}\left (1 - e^{-tu}\right ),\qquad d \rightarrow \infty,}$$

in L ² and in distribution. The paper [1] was the starting point for a more general high-dimensional investigation of the volume of the zero cell Z ₀ in a parametric class of isotropic but not necessarily stationary Poisson hyperplane tessellations. This parametric class is characterized by the intensity measure of the underlying Poisson hyperplane process which is of the form (8) but with σ being the normalized spherical Lebesgue measure. That the case of the typical cell of a Poisson–Voronoi tessellation is included in this model can be seen from (12) by choosing the distance exponent r = d and by adjusting the intensities. Depending on the intensity t, the distance parameter r, and the dimension d, explicit formulas for the second moment $\mathbb{E}(V _{d}(Z_{0})^{2})$ and the variance Var(V _d (Z ₀)) as well as sharp bounds for these characteristics were derived in [45]. Depending on the tuning of these parameters, the asymptotic behavior of V _d (Z ₀) can differ dramatically.

To describe an interesting consequence of such variance bounds, we define by $\overline{Z}:= V _{d}(Z)^{-1/d}Z$ the volume normalized typical cell of a Poisson–Voronoi tessellation with intensity t (as above). Let $L \subset \mathbb{R}^{d}$ be a co-dimension one linear subspace. Then there is an absolute constant c > 0 such that

$$\displaystyle{\mathbb{P}\left (V _{d-1}\left (\overline{Z} \cap L\right ) \geq \sqrt{e}/2\right ) \geq 1 - c \cdot \frac{1} {\sqrt{d}}\left ( \frac{4} {3\sqrt{3}}\right )^{d}.}$$

This is a very special case of Theorem 3.17 in [46]. It can be paraphrased by saying that with overwhelming probability the hyperplane conjecture , a major problem in the asymptotic theory of Banach spaces, is true for this class of random polytopes, see Milman and Pajor [76].

In [46] also the high-dimensional limits of the mean number of faces and an isoperimetric ratio of a mean volume and a mean surface area are studied for the zero cell of a parametric class of random tessellations (as an example of a random polytope). As a particular instance of such a result, we mention that

$$\displaystyle{\lim _{d\rightarrow \infty }d^{-1/2}\,\root{d}\of{\mathbb{E}f_{\ell}(Z_{ 0})} = \sqrt{2\pi b},}$$

where r = bd (with b fixed) increases proportional to the dimension d and ℓ is fixed. It is remarkable that this limit is independent of ℓ. At the basis of this and other results are identities connecting the f-vector of Z ₀ to certain dual intrinsic volumes of projections of Z ₀ to a deterministic subspace.

3.4.9 Poisson–Voronoi Approximation

Let A be a Borel set in $\mathbb{R}^{d}$ and let η _t be a Poisson point process in $\mathbb{R}^{d}$. Assume that we observe η _t and the only information about A at our disposal is which points of η _t lie in A, i.e., we have the partition of the process η _t into η _t ∩ A and η _t ∖ A. We try to reconstruct the set A just by the information contained in these two point sets. For that aim we approximate A by the set $A_{\eta _{t}}$ of all points in $\mathbb{R}^{d}$ which are closer to η _t ∩ A than to η _t ∖ A.

Applications of the Poisson–Voronoi approximation include nonparametric statistics (see Einmahl and Khmaladze [32, Sect. 3]), image analysis (reconstructing an image from its intersection with a Poisson point process, see [63]), quantization problems (see, e.g., Chap. 9 in the book of Graf and Luschgy [35]), and numerical integration (approximation of the volume of a set A using its intersection with a point process η _t ∩ A).

More formally, let η _t be a homogeneous Poisson point process of intensity t > 0, and denote by $v_{\eta _{t}}(x)$ the Voronoi cell generated by η _t with center x ∈ η _t . Then the set $A_{\eta _{t}}$ is just the union of the Poisson–Voronoi cells with center lying in A, i.e.,

$$\displaystyle{A_{\eta _{t}} =\bigcup \limits _{x\in \eta _{t}\cap A}v_{\eta _{t}}(x).}$$

We call this set the Poisson–Voronoi approximation of the set A. It was first introduced by Khmaladze and Toronjadze in [63]. They proposed $A_{\eta _{t}}$ to be an estimator for A when t is large. In particular, they conjectured that for arbitrary bounded Borel sets $A \subset \mathbb{R}^{d}$, $d\geqslant 1,$

$$\displaystyle{V _{d}(A_{\eta _{t}}) \rightarrow V _{d}(A),\quad t \rightarrow \infty,}$$

$$\displaystyle{ V _{d}(A\bigtriangleup A_{\eta _{t}}) \rightarrow 0,\quad t \rightarrow \infty, }$$

(13)

almost surely, where △ is the operation of the symmetric difference of sets. In full generality this was proved by Penrose [84].

It can be easily shown that for any Borel set $A \subset \mathbb{R}^{d}$ we have

$$\displaystyle{\mathbb{E}V _{d}(A_{\eta _{t}}) = V _{d}(A),}$$

since η _t is a stationary point process. Thus $V _{d}(A_{\eta _{t}})$ is an unbiased estimator for the volume of A. Relation (13) suggests that

$$\displaystyle{ \mathbb{E}V _{d}(A\bigtriangleup A_{\eta _{t}}) \rightarrow 0,\quad t \rightarrow \infty, }$$

(14)

although this is not a direct corollary. The more interesting problems are to find exact asymptotic of $\mathbb{E}V _{d}(A\bigtriangleup A_{\eta _{t}})$, $\mathrm{Var}V _{d}(A_{\eta _{t}})$, and $\mathrm{Var}V _{d}(A\bigtriangleup A_{\eta _{t}})$.

Very general results in this direction are provided by Reitzner et al. [92]. Their results for Borel sets with finite volume V _d (A) depend on the perimeter Per(A) of the set A in the sense of variational calculus. If A is a compact set with Lipschitz boundary (e.g., a convex body), then Per(A) equals the (d − 1)-dimensional Hausdorff measure $\mathcal{H}^{d-1}(\partial A)$ of the boundary ∂ A of A. In the general case $\mathrm{Per}(A)\leqslant \mathcal{H}^{d-1}(\partial A)$ holds.

If $A \subset \mathbb{R}^{d}$ is a Borel set with V _d (A) < ∞ and Per(A) < ∞, then

$$\displaystyle{ \mathbb{E}V _{d}(A\bigtriangleup A_{\eta _{t}}) = c_{d} \cdot \mathrm{Per}(A) \cdot t^{-1/d}(1 + o(1)),\quad t \rightarrow \infty, }$$

(15)

where $c_{d} = 2d^{-2}\varGamma (1/d)\kappa _{d-1}\kappa _{d}^{-1-1/d}$.

The asymptotic order of the variances of $A_{\eta _{t}}$ and $A\bigtriangleup A_{\eta _{t}}$ as t → ∞ was first studied in [44] for convex sets and then extended in [92] to arbitrary Borel sets, where also sharp upper bounds in terms of the perimeter are given. A very general result in this direction is due to Yukich [114]. If $A \subset \mathbb{R}^{d}$ is a Borel set with V _d (A) < ∞ and finite (d − 1)-dimensional Hausdorff measure $\mathcal{H}^{d-1}(\partial A)$ of the boundary of A, then

$$\displaystyle{\mathrm{Var}V _{d}(A_{\eta _{t}}) = C_{1}(A)t^{-1-1/d}(1 + o(1)),}$$

and

$$\displaystyle{\mathrm{Var}V _{d}(A\bigtriangleup A_{\eta _{t}}) = C_{2}(A)t^{-1-1/d}(1 + o(1)),\quad t \rightarrow \infty,}$$

with explicitly given constants C _i (A).

A breakthrough was achieved by Schulte [107] for convex sets A and, more generally, by Yukich [114] for sets with a boundary of finite (d − 1)-dimensional Hausdorff measure. They proved central limit theorems for $V _{d}(A_{\eta _{t}})$ and $V _{d}(A\bigtriangleup A_{\eta _{t}})$.

Recently, Lachièze-Rey and Peccati [68] proved bounds for the variance, higher moments, and central limit theorems for a huge class of sets, including fractals.

Another interesting open problem is to measure the quality of approximation of a convex set K by $K_{\eta _{t}}$ in terms of the Hausdorff distance between both sets. First estimates for the Hausdorff distance are due to Calka and Chenavier [22], very recently Lachièze-Rey and Vega [70] proved precise results on the Hausdorff distance even for irregular sets.

Since $A_{\eta _{t}} \rightarrow A$ in the sense described above, it is of interest to compare the boundary ∂ A to the boundary of the Poisson–Voronoi approximation $\partial A_{\eta _{t}}$. This has been explored recently by Yukich [114] who showed that $\mathcal{H}^{d-1}(\partial A_{\eta _{t}})$—scaled by a suitable factor independent of A—is an unbiased estimator for $\mathcal{H}^{d-1}(\partial A)$, and he also obtained variance asymptotics. We also mention a very recent deep contribution due to Thäle and Yukich [111] who investigate a large number of functionals of $A_{\eta _{t}}$.

3.5 Random Polytopes

The investigation of random polytopes started 150 years ago when Sylvester stated in 1864 his four-point-problem in the Educational Times. Choose n points independently according to some probability measure in $\mathbb{R}^{d}$. Denote the convex hull of these points by $\mathrm{conv}\{X_{1},\ldots,X_{n}\}$. Sylvester asked for the distribution function of the number of vertices of $\mathrm{conv}\{X_{1},\ldots,X_{4}\}$ in the case d = 2.

Random polytopes are linked to other fields and have important applications. We mention the connection to functional analysis: Milman and Pajor [76] showed that the expected volume of a random simplex is closely connected to the so-called isotropic constant of a convex set which is a fundamental quantity in the local theory of Banach spaces.

In this section we will concentrate on recent contributions and refer to the surveys by Hug [49], Reitzner [90], and Schneider [103] for additional information. Let η _t be a Poisson point process with intensity measure of the form μ _t  = t μ ₁, t > 0, where μ ₁ is an absolutely continuous probability measure on $\mathbb{R}^{d}$. Then the Poisson polytope is defined as Π _t  = conv(η _t ).

There are only few results for given t and general probability measures μ ₁. In analogy to Efron [31], it immediately follows from the Slivnyak–Mecke theorem that $\mathbb{E}f_{0}(\varPi _{t}) = t - \mathbb{E}\mu _{t}(\varPi _{t}))$, connecting the probability content $\mathbb{E}\mu _{t}(\varPi _{t})$ and the expected number of vertices $\mathbb{E}f_{0}(\varPi _{t})$. Identities for higher moments have been given by Beermann and Reitzner [9] who extended this further to an identity between the generating function $g_{I(\varPi _{t})}$ of the number of non-vertices or inner points $I(\varPi _{t}) = \vert \eta _{t}\vert - f_{0}(\varPi _{t})$ and the moment generating function $h_{\mu _{t}(\varPi _{t})}$ of the μ _t -measure of Π _t . Both functions are entire functions on $\mathbb{C}$ and satisfy

$$\displaystyle{g_{I(\varPi _{t})}(z + 1) = h_{\mu _{t}(\varPi _{t})}(z),\qquad z \in \mathbb{C},}$$

thus relating the distributions of the number of vertices and the μ _t -measure of Π _t .

3.5.1 General Inequalities

Assume that $K \subset \mathbb{R}^{d}$ is a compact convex set and set μ _t (⋅ ) = tV _d (K ∩⋅ ). We denote by Π _t ^K = conv[η _t ] the Poisson polytope in K.

In this section we describe some inequalities for Poisson polytopes. Based on the work of Blaschke [11], Dalla and Larman [28], Giannopoulos [33], and Groemer [36, 37] showed that

$$\displaystyle{ \mathbb{E}V _{d}(\varPi _{t}^{B}) \leq \mathbb{E}V _{ d}(\varPi _{t}^{K}) \leq \mathbb{E}V _{ d}(\varPi _{t}^{\bigtriangleup }) }$$

(16)

where Π _t ^△, resp. Π _t ^B denotes the Poisson polytope where the underlying convex set is a simplex, resp. a ball of the same volume as K. The left inequality is true in arbitrary dimensions, whereas the right inequality is just known in dimension d = 2 and open in higher dimensions. To prove this extremal property of the simplex in arbitrary dimensions seems to be very difficult and is still a challenging open problem. A positive solution to this problem would immediately imply a solution to the hyperplane conjecture, see Milman and Pajor [76].

There are some elementary questions concerning the monotonicity of functionals of Π _t ^K. First, it is immediate that for all $K \in \mathcal{K}^{d}$ and $i = 1,\ldots,d$,

$$\displaystyle{\mathbb{E}V _{i}(\varPi _{t}^{K}) \leq \mathbb{E}V _{ i}(\varPi _{s}^{K})}$$

for t ≤ s. Second, an analogous inequality for the number of vertices is still widely open. It is only known, see [30], that for t ≤ s

$$\displaystyle{\mathbb{E}f_{0}(\varPi _{t}^{K}) \leq \mathbb{E}f_{ 0}(\varPi _{s}^{K})}$$

for d = 2 (and also for smooth convex sets $K \subset \mathbb{R}^{3}$ if t is sufficiently large). Thirdly, the very natural implication

$$\displaystyle{K \subset L\ \Rightarrow \ \mathbb{E}V _{d}(\varPi _{t}^{K}\mid \eta _{ t}(K) = n) \leq \mathbb{E}V _{d}(\varPi _{t}^{L}\mid \eta _{ t}(L) = n)}$$

was asked by Meckes and disproved by Rademacher [85]. He showed that for dimension d ≥ 4 there are convex sets K ⊂ L such that for t sufficiently small $\mathbb{E}V _{d}(\varPi _{t}^{K}\mid \eta _{t}(K) = n) > \mathbb{E}V _{d}(\varPi _{t}^{L}\mid \eta _{t}(L) = n)$. In addition, Rademacher showed that in the planar case this natural implication is true. The case d = 3 is still open.

3.5.2 Asymptotic Behavior of the Expectations

Starting with two famous articles by Rényi and Sulanke [94, 95], the investigations focused on the asymptotic behavior of the expected values as t tends to infinity. Due to work of Wieacker [113], Schneider and Wieacker [106], Bárány [2], and Reitzner [87], for $i = 1,\ldots,d$,

$$\displaystyle{ V _{i}(K) - \mathbb{E}V _{i}(\varPi _{t}^{K}) = c_{ i}(K)t^{- \frac{2} {d+1} } + o\left (t^{- \frac{2} {d+1} }\right ) }$$

(17)

if K is sufficiently smooth. Investigations by Schütt [110] and more recently by Böröczky et al. [15] succeeded in weakening the smoothness assumption. Clearly, Efron’s identity yields a similar result for the number of vertices.

The corresponding results for polytopes are known only for i = 1 and i = d. In a long and intricate proof, Bárány and Buchta [3] showed that

$$\displaystyle{V _{d}(K) - \mathbb{E}V _{d}(\varPi _{t}^{K}) = c_{ d}(K)t^{-1}\ln ^{d-1}t + O\left (t^{-1}\ln ^{d-2}t\,\mathrm{lln}\,t\right )\!.}$$

For i = 1, Buchta [18] and Schneider [96] proved that

$$\displaystyle{V _{1}(K) - \mathbb{E}V _{1}(\varPi _{t}^{K}) = c(K)t^{-\frac{1} {d} }\ + o(t^{-\frac{1} {d} }).}$$

Somehow surprisingly, the cases 2 ≤ i ≤ d − 1 are still open.

Due to Efron’s identity, the results concerning $\mathbb{E}V _{d}(\varPi _{t}^{K})$ can be used to determine the expected number of vertices of Π _t ^K. In [89], Reitzner generalized these results for $\mathbb{E}f_{0}(\varPi _{t}^{K})$ to arbitrary face numbers $\mathbb{E}f_{\ell}(\varPi _{t}^{K})$, $\ell\in \{ 0,\ldots,d - 1\}$.

3.5.3 Variances

In the last years several estimates have been obtained from which the order of the variances can be deduced, see Reitzner [86, 88, 89], Vu [112], Bárány and Reitzner [5], and Bárány et al. [6]. The results can be summarized by saying that there are constants $\underline{c}(K),\overline{c}(K) > 0$ such that

$$\displaystyle{\underline{c}(K)t^{-1}\mathbb{E}V _{ i}(\varPi _{t}^{K}) \leq \mathrm{ Var}V _{ i}(\varPi _{t}^{K}) \leq \overline{c}(K)t^{-1}\mathbb{E}V _{ i}(\varPi _{t}^{K})}$$

and

$$\displaystyle{\underline{c}(K)t^{-1}\mathbb{E}f_{\ell}(\varPi _{ t}^{K}) \leq \mathrm{ Var}f_{\ell}(\varPi _{ t}^{K}) \leq \overline{c}(K)t^{-1}\mathbb{E}f_{\ell}(\varPi _{ t}^{K})}$$

if K is smooth or a polytope. It is conjectured that these inequalities hold for general convex bodies. That the lower bound holds in general has been proved in Bárány and Reitzner [5], but the general upper bounds are missing.

A breakthrough are recent results by Calka et al. [26] and Calka and Yukich [25] who succeeded in giving the precise asymptotics of these variances,

$$\displaystyle{\mathrm{Var}V _{i}(\varPi _{t}^{K}) = c_{ d,i}(K)\,t^{-\frac{d+3} {d+1} } + o(t^{-\frac{d+3} {d+1} })}$$

for i = 1, d, and

$$\displaystyle{\mathrm{Var}f_{\ell}(\varPi _{t}^{K}) =\bar{ c}_{ d,\ell}(K)\,t^{\frac{d-1} {d+1} } + o(t^{\frac{d-1} {d+1} })}$$

if K is a smooth convex body. The dependence of $\bar{c}_{d,\ell}(K)$ on K is known explicitly.

3.5.4 Limit Theorems

First CLTs have been proved by Groeneboom [39], Cabo and Groeneboom [19], and Hsing [47] but only in the planar case. In recent years, methods have been developed to prove CLTs for the random variables V _d (Π _t ^K) and f _ℓ (Π _t ^K) in arbitrary dimensions. The main ingredients are Stein’s method and some kind of localization arguments. For smooth convex sets this was achieved in Reitzner [88], and for polytopes in a paper by Bárány and Reitzner [4]. The results state that there is a constant c(K) and a function ɛ(t), tending to zero as t → ∞, such that

$$\displaystyle{\left \vert \mathbb{P}\left (\frac{V _{d}(\varPi _{t}^{K}) - \mathbb{E}V _{d}(\varPi _{t}^{K})} {\sqrt{\mathrm{Var }V _{d } (\varPi _{t }^{K })}} \leq x\right ) -\varPhi (x)\right \vert \ \leq c(K)\ \varepsilon (t)}$$

and

$$\displaystyle{\left \vert \mathbb{P}\left (\frac{f_{\ell}(\varPi _{t}^{K}) - \mathbb{E}f_{\ell}(\varPi _{t}^{K})} {\sqrt{\mathrm{Var }f_{\ell} (\varPi _{t }^{K })}} \leq x\right ) -\varPhi (x)\right \vert \ \leq c(K)\ \varepsilon (t).}$$

A surprising recent result is due to Pardon [79, 80] who proved in the Euclidean plane a CLT for the volume of Π _t ^K for all convex bodies K without any restriction on the boundary structure of K. A similar general result in higher dimensions seems to be out of reach at the moment.