2. Poisson hyperplane processes

In this section we collect a few basic properties of Poisson hyperplane processes and the associated intersection processes. Let ${\mathbb H}^{d-1}$ denote the space of all hyperplanes in ${\mathbb R}^d$ . Any such hyperplane H is of the form

\begin{align*} H_{u,s}\,{:\!=}\, \{y\in{\mathbb R}^d\colon \langle y,u\rangle =s\},\end{align*}

where u is an element of the unit sphere ${\mathbb S}^{d-1}$ , $s\in{\mathbb R}$ and $\langle \cdot,\cdot\rangle$ denotes the Euclidean scalar product. (Any hyperplane has two representations of this type.) We can make ${\mathbb H}^{d-1}$ a measurable space by introducing the smallest $\sigma$ -field containing for each compact $K\subset {\mathbb R}^d$ the set

\begin{align*} [K]\,{:\!=}\, \{H\in {\mathbb H}^{d-1}\colon H\cap K\ne\emptyset\}.\end{align*}

In fact ${\mathbb H}^{d-1}\cup\{\emptyset\}$ can be shown to be a closed subset of the space of all closed subsets of ${\mathbb R}^d$ , equipped with the Fell topology. We refer to [Reference Schneider and Weil18, Section 12.2] for more details on this topology and related measurability issues; see also [Reference Last and Penrose13, Appendix A3].

We consider a (stationary) Poisson hyperplane process, that is, a Poisson process $\eta$ on ${\mathbb H}^{d-1}$ whose intensity measure is given by

(2.1) \begin{align}\lambda=\gamma\int_{{\mathbb S}^{d-1}} \int_{\mathbb R}{\mathbf 1}\{H_{u,s}\in\cdot\}{\textrm{d}} s\,\mathbb{Q}({\textrm{d}} u),\end{align}

where $\gamma>0$ is an intensity parameter and $\mathbb{Q}$ (the directional distribution of $\eta$ ) is an even probability measure on ${\mathbb S}^{d-1}$ . We assume that $\mathbb{Q}$ is not concentrated on a great subsphere. It would be helpful (even though not strictly necessary) for the reader to be familiar with basic point process and random measure terminology; see e.g. [Reference Last and Penrose13]. For our purposes it is mostly enough to interpret $\eta$ as a random discrete subset of ${\mathbb H}^{d-1}$ . The number of points (hyperplanes) in a measurable set $A\subset{\mathbb H}^{d-1}$ is then given by $|\eta\cap A|$ and has a Poisson distribution with parameter $\lambda(A)$ . Since $\lambda$ is invariant under translations (we have for all $x\in{\mathbb R}^d$ that $\lambda({\cdot})=\lambda(\{H\colon H+x\in{\cdot}\})$ ), the Poisson process $\eta$ is stationary, i.e. distributionally invariant under translations. Furthermore we can derive from Campbell’s theorem (see e.g. [Reference Last and Penrose13, Proposition 2.7]) and (2.1) that

(2.2) \begin{align}\mathbb{E}[|\eta\cap [K]|]<\infty,\quad \text{$K\subset{\mathbb R}^d$ compact}.\end{align}

As usual we assume (without loss of generality) that $|\eta(\omega)\cap [K]|<\infty$ for all $\omega\in\Omega$ and all compact $K\subset{\mathbb R}^d$ . More details of Poisson hyperplane processes can be found in [Reference Schneider and Weil18, Section 4.4].

Let $m\in\{1,\ldots,d\}$ . We define a random measure $\Phi_m$ on ${\mathbb R}^d$ by

(2.3) \begin{align}\Phi_m(B)\,{:\!=}\, \dfrac{1}{m!}\;\sideset{}{^{\ne}}\sum_{\,\,H_1,\ldots,H_m \in \eta}\mathcal{H}^{d-m}(B\cap H_1\cap\cdots \cap H_m)\end{align}

for Borel sets $B\subset{\mathbb R}^d$ , where $\sum^{\neq}$ denotes summation over pairwise distinct entries and where $\mathcal{H}^{d-m}$ is the Hausdorff measure of dimension $d-m$ ; see e.g. [Reference Last and Penrose13, Appendix A.3]. Using the arguments on page 130 of [Reference Schneider and Weil18], one can show that almost surely for all distinct $H_1,\ldots,H_m\in\eta$ , the intersection $H_1\cap\cdots\cap H_m$ is either empty or has dimension $d-m$ . Combining this with (2.2), we see that the random measures $\Phi_1,\ldots,\Phi_m$ are almost surely locally finite, i.e. finite on bounded Borel sets. The random variable $\Phi_m(B)$ is the volume (in the appropriate dimension) of all possible intersections of $d-m$ hyperplanes within B.

It can be shown that (almost surely) the intersection of $d+1$ different hyperplanes from $\eta$ is empty. Therefore the random measure $\Phi_d$ is almost surely a point process without multiplicities, so that $\Phi_d(B)$ is just the number of (intersection) points $x\in B$ with $\{x\}=H_1\cap\cdots\cap H_d$ for some $H_1,\ldots,H_d\in\eta$ . It is convenient to define a simple (and locally finite) point process $\Phi$ as the set of all points $x\in{\mathbb R}^d$ with $\{x\}=H_1\cap\cdots\cap H_d$ for some $H_1,\ldots,H_d\in\eta$ . When (as is common) interpreting $\Phi$ as a random counting measure, we have $\mathbb{P}(\Phi=\Phi_d)=1$ . Figure 1 shows two samples of $\eta$ and $\Phi$ .

Figure 1.

Samples of Poisson hyperplane processes $\eta$ in ${\mathbb R}^2$ (a, b) and ${\mathbb R}^3$ (c) and the corresponding intersection processes $\Phi$ (dots) for two directional distributions: only three possible directions (a) and isotropic (b, c).

Among other things, Theorem 4.4.8 of [Reference Schneider and Weil18] gives a formula for the intensity $\gamma_m\,{:\!=}\, \mathbb{E}[\Phi_m([0,1]^d)]$ of $\Phi_m$ . We only need to know that it is positive and finite. In the remaining part of this section we recall some second-order properties of $\Phi_m$ . (At first reading, some details could be skipped without too much loss.) Let A, B be bounded Borel subsets of ${\mathbb R}^d$ . Using the theory of U-statistics [Reference Last and Penrose13, Section 12.3], it was shown in [Reference Last, Penrose, Schulte and Thäle14] that

(2.4) \begin{align}\lim_{r\to\infty}r^{-(2d-1)}\operatorname{Cov}\![\Phi_m(rA),\Phi_m(rB)]=C_m(A,B),\end{align}

where

(2.5) \begin{align}\notag C_m(A,B)&\,{:\!=}\, \dfrac{1}{((m-1)!)^2}\int\biggl(\int \mathcal{H}^{d-m}(A\cap H_1\cap \dots \cap H_m)\,\lambda^{m-1}({\textrm{d}}(H_2,\dots,H_m))\biggr)\\[3pt]&\quad\, \times\biggl(\int \mathcal{H}^{d-m}(B\cap H_1\cap H'_2\cap \dots \cap H'_m)\,\lambda^{m-1}\bigl({\textrm{d}}(H'_2,\dots, H'_m)\bigr)\biggr)\,\lambda({\textrm{d}} H_1).\end{align}

If $m=1$ , this has to be read as

\begin{align*}C_1(A,B)=\int \mathcal{H}^{d-1}(A\cap H_1)\mathcal{H}^{d-1}(B\cap H_1)\,\lambda({\textrm{d}} H_1).\end{align*}

The asymptotic variance $C_m(A,A)$ was derived in [Reference Heinrich, Schmidt and Schmidt9]. We note that $C_m(A,A)$ is finite (this is implied by the form (2.1) of $\lambda$ ) and that $C_m(A,A)=0$ if and only if

\begin{equation*}\int\mathcal{H}^{d-m}(A\cap H_1\cap \cdots \cap H_m)\,\lambda^{m}({\textrm{d}}(H_1,\dots,H_m))=0.\end{equation*}

Since $\mathbb{Q}$ is not concentrated on a great subsphere, this happens if and only if the Lebesgue measure of A vanishes; see the proof of [Reference Schneider and Weil18, Theorem 4.4.8]. Therefore we obtain from (2.4) that the random measures $\Phi_1,\ldots,\Phi_d$ are hyperfluctuating (if $d\ge 2$ ). The results in [Reference Heinrich, Schmidt and Schmidt9] and [Reference Last, Penrose, Schulte and Thäle14] show that, for each finite collection $B_1,\ldots,B_n$ of bounded Borel sets, the random vector

\begin{equation*}r^{-(d-1/2)}(\Phi_m(rB_1)-\mathbb{E}[\Phi_m(rB_1)],\ldots,\Phi_m(rB_n)-\mathbb{E}[\Phi_m(rB_n)])\end{equation*}

converges in distribution to a multivariate normal distribution.

It is worth noting that the asymptotic covariances (2.5) are non-negative. If $\eta$ is isotropic (meaning that $\mathbb{Q}$ is the uniform distribution on ${\mathbb S}^{d-1}$ ), there exist more detailed non-asymptotic second-order results. In this case [Reference Heinrich, Schmidt and Schmidt9, p. 936] shows that the pair correlation function $\rho_2$ (see e.g. [Reference Last and Penrose13, Section 8.2]) of the intersection point process $\Phi=\Phi_d$ is given by

(2.6) \begin{align}\rho_2(x)=1+\sum^d_{i=1}a_i \gamma^{-i}\|x\|^{-i},\quad x\in{\mathbb R}^d,\ x\ne 0,\end{align}

where the coefficients $a_1,\ldots,a_d$ are strictly positive and depend only on the dimension. Hence, as $\|x\|\to\infty$ , $\rho_2(x)-1\to 0$ only at speed $\|x\|^{-1}$ . In particular, the truncated pair correlation function $\rho_2-1$ is not integrable outside any neighborhood of the origin. Using the well-known formula [Reference Last and Penrose13, Exercise 8.9]

\begin{align*}\operatorname{Var}\![\Phi(B)]=\gamma_dV_d(B)+\gamma_d^2\int V_d(B\cap (B+x))(\rho_2(x)-1){\textrm{d}} x\end{align*}

(valid for all bounded Borel sets $B\subset{\mathbb R}^d$ ) and assuming that B is convex, it is not too hard to confirm (2.4) (using polar coordinates) for $A=B$ and a certain positive constant $C_d(B,B)$ . The value of this constant can be found in [Reference Heinrich, Schmidt and Schmidt9].

Remark 2.1. Assume that $\mathbb{Q}$ vanishes on any great subsphere. Then the random measures $\Phi_1,\ldots,\Phi_d$ have the following mixing property. Let $i\in\{1,\ldots,d\}$ . Then $\Phi_i$ can be interpreted as a random element in a suitable space $\mathbf{M}$ of measures on ${\mathbb R}^d$ equipped with a suitable $\sigma$ -field [Reference Kallenberg10, Reference Last and Penrose13]. Let A, B be arbitrary measurable subsets of $\mathbf{M}$ . Then

\begin{align*}\lim_{\|x\|\to\infty}\mathbb{P}(\Phi_i\in A,\theta_x\Phi_i\in B)=\mathbb{P}(\Phi_i\in A)\mathbb{P}(\Phi_i\in B),\end{align*}

where the random measure $\theta_x\Phi_i$ is defined by $\theta_x\Phi_i(C)\,{:\!=}\, \Phi_i(C+x)$ for Borel sets $C\subset{\mathbb R}^d$ . This is a straightforward consequence of [Reference Schneider and Weil18, Theorem 10.5.3] and the fact that $\Phi_i$ is derived from $\eta$ in a translation-invariant way. In particular, $\Phi_i$ is ergodic, i.e. $\mathbb{P}(\Phi_i\in A)\in\{0,1\}$ for each translation-invariant measurable set $A\subset\mathbf{M}$ .

3. A reconstruction algorithm

Let $\eta$ be a Poisson hyperplane process as in Section 2. Let $\Phi$ be the intersection point process associated with $\eta$ . (Recall from Section 2 that $\mathbb{P}(\Phi=\Phi_d)=1$ , where $\Phi_d$ is given by (2.3) for $m=d$ .) Let $K\subset{\mathbb R}^d$ be a non-empty convex and compact set. In this section we describe an algorithm which reconstructs $\eta\cap [K]$ (see Algorithm 3.2 and Figure 2) by observing the points of $\Phi$ in a (random) bounded domain Z in the complement of (the interior of) K. In the next section we shall show that the diameter of Z is exponentially small.

Figure 2.

Reconstruction algorithm of $\eta\cap [K]$ . Given a convex domain K, the algorithm recursively scans the points in $\Phi\cap K_{T_n}$ (solid circles). At step $n=16$ , three hyperplanes are reconstructed (a). At step $n=112$ , three polygons $P_1$ , $P_2$ , $P_3$ are reconstructed within $K_{T_n}$ (b). Hence all hyperplanes in $\eta\cap [K]$ (dashed lines) can be reconstructed (c).

We say that $n\ge d$ points from ${\mathbb R}^d$ are in affinely independent hyperplane position if any d of them are affinely independent and span the same hyperplane. The straightforward idea of the algorithm comes from the following proposition of some independent interest. We have not been able to find this result in the literature.

Proof. We start the proof with an auxiliary observation. Let $m\in{\mathbb N}$ and let f be a measurable function on $({\mathbb H}^{d-1})^m$ taking values in the space of all non-empty closed subsets of ${\mathbb R}^d$ . (We equip this space with the usual Fell–Matheron topology: see [Reference Schneider and Weil18]). We assert that

(3.1) \begin{align}\mathbb{P}(\text{there exist distinct $H_1,\ldots,H_{m+1}\in\eta$ such that $f(H_1,\ldots,H_m)\subset H_{m+1}$})=0.\end{align}

Obviously the indicator function of the event in (3.1) can be bounded by

\begin{align*}X\,{:\!=}\, \sideset{}{^{\ne}}\sum_{H_1,\ldots,H_{m+1} \in \eta}{\mathbf 1}\{f(H_1,\ldots,H_m)\subset H_{m+1}\}.\end{align*}

If $\mathbb{E}[X]=0$ , then (3.1) follows. By the multivariate Mecke formula [Reference Last and Penrose13, Theorem 4.5],

\begin{align*}\mathbb{E}[X]=\int {\mathbf 1}\{\,f(H_1,\ldots,H_m)\subset H_{m+1}\}\,\lambda^{m+1}({\textrm{d}}(H_1,\ldots,H_{m+1})).\end{align*}

By Fubini’s theorem it is then enough to prove that

(3.2) \begin{align}\int {\mathbf 1}\{F\subset H\}\,\lambda({\textrm{d}} H)=0\end{align}

for any non-empty closed set $F\subset{\mathbb R}^d$ . By monotonicity of integration it is sufficient to assume that $F=\{x\}$ for some $x\in{\mathbb R}^d$ . But then (3.2) directly follows from (2.1) and $\int {\mathbf 1}\{\langle x,u\rangle=r\}\,{\textrm{d}} r=0$ for each $u\in {\mathbb S}^{d-1}$ .

We now turn to the main part of the proof. Let $I_1,\ldots,I_{2d-1}\subset{\mathbb N}$ be distinct with $|I_1|=\cdots=|I_{2d-1}|=d$ . We shall refer to these sets as blocks and to subsets of blocks as subblocks. For convenience we assume that $I_1=[d]\,{:\!=}\, \{1,\ldots,d\}$ . Assume that $\cup^{2d-1}_{i=1} I_i=[n]$ for some $n\ge d$ . Consider $(H_1,\ldots,H_{n})\in\eta^{n}$ with $H_i\ne H_j$ for $i\ne j$ and the following properties. For each $i\in\{1,\ldots,2d-1\}$ we find that $\cap_{j\in I_i} H_j$ consists of a single point $x_i$ and $x_1,\ldots,x_{2d-1}$ are in affinely independent hyperplane position. Let H be the affine hull of $\{x_1,\ldots,x_{2d-1}\}$ . We will show that almost surely $H\in\{H_1,\ldots,H_{2d-1}\}$ .

Let us assume on the contrary that $H\notin\{H_1,\ldots,H_{2d-1}\}$ . Then each $k\in[n]$ (e.g. $k=1$ ) belongs to at most $d-1$ of the blocks. Indeed, by the assumption of the affinely independent hyperplane position we would otherwise have $H_1=H$ . We will show that almost surely

(3.3) \begin{align}\bigcap_{j\in I} H_j\subset H\end{align}

for all subblocks I.

We prove (3.3) by (descending) induction on the cardinality k of I. In the case $k=d$ (3.3) holds by definition of H. So assume that (3.3) holds for all subblocks of cardinality $k\in\{2,\ldots,d\}$ . We need to show that it holds for each subblock I of cardinality $k-1$ . For notational convenience we take $I=[k-1]$ . By the induction hypothesis we obtain

(3.4) \begin{align}H_1\cap\cdots\cap H_k\subset H.\end{align}

Set $H'\,{:\!=}\, H_1\cap\cdots\cap H_{k-1}\cap H$ . Since $H_1\cap\cdots\cap H_{k-1}\ne\emptyset$ , we have (almost surely) $\dim H_1\cap\cdots\cap H_{k-1}=(d-(k-1))$ . Since $\dim H=d-1$ we therefore obtain $\dim H'\in\{d-k,d-(k-1)\}$ . Let us first assume that $\dim H'=d-k$ . By (3.4) (and since $H_1\cap\cdots\cap H_k\ne\emptyset$ ), we have $\dim H_k\cap H'=d-k$ . Therefore we find that $H_k\cap H'=H'$ , i.e. $H'\subset H_k$ . Since k is contained in at most $d-1$ of the subblocks, e.g. in $I_1,\ldots,I_{d-1}$ , the blocks $I_d,\ldots,I_{2d-1}$ still generate H, i.e. $H=\textrm{aff}\{x_d,\ldots,x_{2d-1}\}$ . Therefore H $^{\prime}$ is ‘independent’ of $H_k$ , contradicting $H'\subset H_k$ . More rigorously we can apply (3.1) to conclude that this case almost surely cannot occur. Let us now assume that $\dim H'=d-(k-1)$ . Then $\dim H'=\dim H_1\cap\cdots\cap H_{k-1}$ and therefore $H'=H_1\cap\cdots\cap H_{k-1}$ . This means that $H_1\cap\cdots\cap H_{k-1}\subset H$ , as required to finish the induction.

Using (3.4) for subblocks of size 1 yields that $H_k=H$ for each $k\in[n]$ . This contradiction finishes the proof of the proposition.

Our algorithm requires some notation. Let

\begin{equation*}d(x,K)\,{:\!=}\, \min\{\|y-x\|\colon y\in K\}\end{equation*}

denote the Euclidean distance between $x\in{\mathbb R}^d$ and K and let

\begin{align*}K_r\,{:\!=}\, \{x\in{\mathbb R}^d\setminus\textrm{int}\ {K}\colon d(x,K)\le r\}.\end{align*}

This is the difference of the parallel set of K at distance $r\ge 0$ and the interior $\textrm{int}\ {K}$ of K. Note that $K_r$ is closed and $K_0$ is the boundary of K. Define random times $T_n$ , $n\ge 1$ , inductively by setting

\begin{align*}T_{n+1}\,{:\!=}\, \min\{r>T_n\colon \Phi\cap (K_r\setminus K_{T_n})\ne\emptyset\},\end{align*}

where $T_0\,{:\!=}\, 0$ . We form a (random) set $\xi_n$ of hyperplanes as follows. A hyperplane H belongs to $\xi_n$ if it does not intersect K and if it contains $2d-1$ different points from $\Phi\cap K_{T_n}$ in affinely independent hyperplane position. By Proposition 3.1 we have almost surely that $\xi_n\subset\eta$ . For a hyperplane H with $H\cap K=\emptyset$ we let H(K) denote the half-space bounded by H with $K\subset H(K)$ .

Proof. Assume that the algorithm stops at stage n and let $P_1,\ldots,P_{2d-1}$ be as in step (i) of the algorithm. These are bounded polytopes which contain K in their interior and which are made up of different hyperplanes from $\eta$ . Assume that $H\in\eta$ intersects K. Then H intersects for each $i\in[2d-1]$ the boundary of the polytope $P_i$ and in fact at least one of its edges. Therefore there exist distinct hyperplanes $H_1,\ldots,H_{(2d-1)(d-1)}\in\eta\setminus\{H\}$ such that

\begin{align*} H\cap \bigcap_{j\in I_i} H_j\ne \emptyset,\quad i\in[2d-1],\end{align*}

where $I_i\,{:\!=}\, \{(i-1)(d-1)+1,\ldots,i(d-1)\}$ . Almost surely each of these intersections consists of only one point, say $x_i$ . We assert that these points are in affinely independent hyperplane position. If they are not, then d among those points, say $x_1,\ldots,x_d$ , are affinely dependent. Then one of those points, say $x_d$ , must lie in $\textrm{aff}\{x_1,\ldots,x_{d-1}\}$ . Therefore we need to show that the probability of finding distinct $H_0,\ldots,H_{d(d-1)}\in\eta$ such that $\{x_i\}\,{:\!=}\, H_0\cap \cap_{j\in I_i}H_j$ is a singleton for each $i\in[d]$ and

\begin{align*}x_d\in\textrm{aff}\{x_1,\ldots,x_{d-1}\}\end{align*}

is zero. As in the proof of (3.1), this probability can be bounded by

\begin{align*}\iiint &{\mathbf 1}\{|H\cap\cap_{j\in I_1}H_j|=\cdots=|H\cap\cap_{j\in I_d}H_j|=1\}\\[3pt]&{\mathbf 1}\{H\cap \cap_{j\in I_d}H_j\subset\textrm{aff} \bigl(H\cap \cap_{j\in I_1}H_j,\ldots,H\cap\cap_{j\in I_{d-1}}H_j)\}\\[3pt]&\qquad\lambda({\textrm{d}} H)\,\lambda^{d(d-1)}({\textrm{d}} (H_1,\ldots,H_{d(d-1)})).\end{align*}

Therefore it is enough to show that for $\lambda$ -a.e. $H\in{\mathbb H}^{d-1}$ and each affine space $E\subset H$ of dimension at most $d-2$ ,

(3.5) \begin{align}\int {\mathbf 1}\{|\cap_{j\in I_d}H_j|=1, \cap_{j\in I_d}H_j\subset E\}\,\lambda^{d-1}_H({\textrm{d}} (H_1,\ldots,H_{d-1}))=0,\end{align}

where $\lambda_H$ is the measure on the space of all affine subspaces of H given by

\begin{align*}\lambda_H\,{:\!=}\, \int{\mathbf 1}\{H'\cap H\in\cdot\}\,\lambda({\textrm{d}} H').\end{align*}

For $\lambda$ -a.e. H, the measure $\lambda_H$ is concentrated on the $(d-2)$ -dimensional subspaces of H and invariant under translations in H. In fact $\lambda_H$ is the intensity measure of the Poisson process $\eta_H\,{:\!=}\, \{H'\cap H\colon H'\in\eta\}$ . Up to a constant multiple,

\begin{equation*}B\mapsto \int {\mathbf 1}\{B\cap H_1\cap\cdots \cap H_{d-1}\ne \emptyset\}\,\lambda^{d-1}_H({\textrm{d}} (H_1,\ldots,H_{d-1}))\end{equation*}

is (as a function of the Borel set $B\subset H$ ) the intensity measure of the intersection process associated with $\eta_H$ (see [Reference Schneider and Weil18, p. 135]) and therefore proportional to the Lebesgue measure on H. (It can also be checked more directly that this function is a locally finite translation-invariant measure.) Hence (3.5) follows.

4. Strong rigidity

In this section we shall exploit the algorithm from Section 3 to show that the intersection processes $\Phi_1,\ldots,\Phi_d$ associated with a Poisson hyperplane process have very strong rigidity properties.

We start with a few definitions. Let $\Psi$ be a random measure on ${\mathbb R}^d$ (e.g. one of the $\Phi_1,\ldots,\Phi_d$ ). For a Borel set $B\subset{\mathbb R}^d$ we let $\Psi_B\,{:\!=}\, \Psi({\cdot}\cap B)$ denote the restriction of $\Psi$ to B. A mapping Z from $\Omega$ into the space of non-empty closed subsets of ${\mathbb R}^d$ is called a $\Psi$ -stopping set if $\{Z\subset F\}\,{:\!=}\, \{\omega\in\Omega\colon Z(\omega)\subset F\}$ is, for each closed set $F\subset {\mathbb R}^d$ , an element of the $\sigma$ -field $\sigma(\Psi_F)$ generated by $\Psi_F$ . (In particular, Z is then a random closed set [Reference Molchanov15].) By $\Psi_Z$ we understand the restriction of $\Psi$ to Z (i.e. the random measure $\omega\mapsto \Psi(\omega)_{Z(\omega)}$ ). If Z is a $\Psi$ -stopping set, then we say that $\eta\cap [K]$ is almost surely determined by $\Psi_Z$ if there exists a measurable mapping f (with suitable domain) such that $\eta\cap [K]=f(\Psi_Z)$ holds almost surely. Stopping sets often arise as the result of some algorithmic construction, as in our main theorem below. They have interesting probabilistic properties. Using the stopping set Z from Theorem 4.1, we may define $Z^*$ as the (random) set of hyperplanes intersecting Z. Then the Poisson process $\eta$ satisfies a spatial Markov property with respect to $Z^*$ . We do not go into further detail but refer to [Reference Baumstark and Last1] and [Reference Molchanov15] for more information on stopping sets.

The following result shows that $\eta\cap[K]$ is almost surely determined by a $\Phi$ -stopping set $Z\subset {\mathbb R}^d\setminus \textrm{int}\ {K}$ of exponentially small size. Here we quantify the size of a closed set $F\subset{\mathbb R}^d$ by the radius R(F) of the smallest ball centered at the origin and containing F. (If F is not bounded then we set $R(F)\,{:\!=}\, \infty$ .)

Theorem 4.1. Let $K\subset{\mathbb R}^d$ be convex and compact. Then there exists a $\Phi$ -stopping set Z with $Z\subset {\mathbb R}^d\setminus \textrm{int}\ {K}$ and such that $\eta\cap [K]$ is almost surely determined by $\Phi\cap Z$ . Moreover, there exist constants $c_1,c_2>0$ such that

(4.1) \begin{align}\mathbb{P}(R(Z)>s)\le c_1\,{\textrm{e}}^{-c_2s},\quad s\ge 1.\end{align}

Proof. We consider the algorithm from Section 3 with running time T, defined after Algorithm 3.2. We assert that $Z\,{:\!=}\, K_{T}$ has all desired properties, where $K_\infty\,{:\!=}\, {\mathbb R}^d\setminus\textrm{int}\ {K}$ . The inclusion $Z\subset K_\infty$ is a direct consequence of the definitions. The stopping set property can be considered as pretty much obvious. The reader might wish to skip the following technical argument. Define ${\mathbf N}$ as the set of all locally finite subsets of ${\mathbb R}^d$ . The algorithm from Section 3 can be used (in an obvious way) to define a measurable mapping $\tilde{Z}$ from ${\mathbf N}$ (equipped with the standard $\sigma$ -field) to the space of all closed subsets of ${\mathbb R}^d$ such that $Z=\tilde Z(\Phi)$ . We need to show that $\tilde Z$ is a stopping set, that is, $\{\mu\colon \tilde Z(\mu)\subset F\}$ is, for all closed sets $F\subset{\mathbb R}^d$ , an element of the $\sigma$ -field generated by the mapping $\mu\mapsto \mu\cap F$ from ${\mathbf N}$ to ${\mathbf N}$ . To prove this we use [Reference Baumstark and Last1, Proposition A.1]. According to this proposition it is sufficient to show that $\tilde{Z}((\psi\cap \tilde{Z}(\psi))\cup\varphi)=\tilde{Z}(\psi)$ for all $\psi,\varphi\in{\mathbf N}$ with $\varphi\subset\tilde{Z}(\psi)^c$ . But this follows from the definition of the algorithm. Indeed, suppose that $\psi\in{\mathbf N}$ is a realization of the intersection process and that the algorithm stops at time t. Restricting $\psi$ to $K_t$ and then adding a configuration $\varphi$ in the complement of $K_t$ does not change the running time t.

We show (4.1) by modifying the idea of the proof of Lemma 1 of [Reference Schneider17]. Since $\mathbb{Q}$ is not concentrated on a great subsphere, there exist linearly independent vectors $e_1,\ldots,e_{d}\in{\mathbb R}^d$ in the support of $\mathbb{Q}$ . Since $\mathbb{Q}$ is even, the vectors $e_{d+1}\,{:\!=}\, -e_1,\ldots,e_{2d}\,{:\!=}\, -e_{d}$ are also in the support of $\mathbb{Q}$ . We can then find a (large) constant $b>0$ and (small) pairwise disjoint closed neighborhoods $U_i$ of $e_i$ , $i\in\{1,\ldots,2d\}$ , such that $U_{d+i}=\{-u\colon u\in U_i\}$ and each intersection

\begin{align*}P=\bigcap^{2d}_{i=1} H^-(u_i,1)\end{align*}

with $u_i\in U_i$ , $i\in\{1,\ldots,2d\}$ , is a polytope with $R(P)\le b$ . Here we write, for given $u\in{\mathbb R}^d$ and $s\in{\mathbb R}$ , $H^-(u,s)\,{:\!=}\, \{y\in{\mathbb R}^d\colon \langle y,u\rangle \le s\}$ . Let $t\ge 0$ . From linearity of the scalar product we then obtain

(4.2) \begin{align}R\biggl(\bigcap^{2d}_{i=1} H^-(u_i,t_i)\biggr)\le b(R(K)+t),\end{align}

whenever $R(K)\le t_i\le R(K)+t$ and $u_i\in U_i$ for $i\in\{1,\ldots,2d\}$ .

We need a straightforward analytic fact. Since the determinant is a continuous function we can assume that there exists $a>0$ such that

(4.3) \begin{align}|\det\!(u_1,\ldots,u_d)|\ge a,\quad(u_1,\ldots,u_d)\in {U}_1\times\cdots\times {U}_d.\end{align}

For $i\in\{1,\ldots,d\}$ let $u_i\in U_i\cup U_{d+i}$ and $s_i\in{\mathbb R}$ . Then $H_{u_1,s_1}\cap\cdots\cap H_{u_d,s_d}$ consists of a single point x (by (4.3) and $U_{d+i}=-U_i$ ), whose Euclidean norm can be bounded as

(4.4) \begin{align} \|x\|\le b'\max\{|s_i|\colon i=1,\ldots,d\},\end{align}

where $b'>0$ is a constant that depends only on the dimension and the (fixed) sets $U_1,\ldots,U_d$ . To see this we note that x (now interpreted as a column vector) is the unique solution of the linear equation $Ax=s$ , where A is the matrix with rows $u_1,\ldots,u_d$ and s is the column vector with entries $s_1,\ldots,s_d$ . By (4.3) we have $x=A^{-1}s$ . It is well known that

\begin{align*}\|x\|_\infty\le \|A^{-1}\|_\infty \|s\|_\infty,\end{align*}

where $\|x\|_{\infty}\,{:\!=}\, \max\{|x_i|\colon i=1,\ldots,d\}$ and $\|A^{-1}\|_\infty$ is the maximum absolute row sum of $A^{-1}$ . In view of the explicit expression of $A^{-1}$ in terms of $\det\!(A)^{-1}$ and the minors of A and the minimum principle for continuous functions, we find that $\|A^{-1}\|_\infty$ is bounded from above by a positive constant. (Recall that $u_1,\ldots,u_d$ are unit vectors.) Since $\|x\|\le c \|x\|_{\infty}$ for some $c>0$ we obtain (4.4).

For notational simplicity we now assume that K is a ball with radius R centered at the origin. In fact, in view of the assertion this is no restriction of generality. Consider the following sets of hyperplanes:

\begin{align*}A_i(t)\,{:\!=}\, \{H(u,s)\colon u\in U_i,R< s\le R+t\},\quad i\in[2d].\end{align*}

We assert the event inclusion

(4.5) \begin{align}\bigcap^{2d}_{i=1}\{|\eta\cap A_i(t)|\ge 2d-1\}\subset \{R(Z)\le b''(R+t)\},\quad \mathbb{P}\text{-a.s.},\end{align}

where $b''\,{:\!=}\, \max\{b,b'\}$ with b $^{\prime}$ as in (4.4).

To show (4.5), we assume that $|\eta\cap A_i(t)|\ge 2d-1$ for each $i\in[2d]$ . Then we can find distinct hyperplanes $H_{i,j}\in\eta$ ( $i\in[2d]$ , $j\in[2d-1]$ ) not intersecting K such that the polytopes

\begin{align*}P_j\,{:\!=}\, \bigcap^{2d}_{i=1} H_{i,j}(K),\quad j\in[2d-1],\end{align*}

contain K in their interior and satisfy $R(P_j)\le b(R+t)$ ; see (4.2). Next we show that each $H_{i,j}$ is in $\xi_n$ as soon as $T_n\ge b''(R+t)-R$ . (Then our algorithm has identified these hyperplanes by time $T_n$ .) Take $H_{1,1}$ , for instance. Define $x_1,\ldots,x_{2d-1}\in\Phi$ by $\{x_j\}\,{:\!=}\, H_{1,1}\cap\cap^d_{i=2}H_{i,j}$ . It can then be shown as in the proof of Proposition 3.3 that these points are in affinely independent hyperplane position. Therefore we obtain from (4.4) and the definition of $A_1(t)$ that $\|x_1\|\le b'(R+t)$ and in fact $\|x_j\|\le b'(R+t)$ for each $j\in[2d-1]$ . Therefore $H_{i,j}\in \xi_n$ , provided that $T_n\ge b'(R+t)-R$ . We have already seen that $R(P_j)\le b(R+t)$ , so that the boundary of $P_j$ is contained in $K_{T_n}$ if $T_n\ge b(R+t)-R$ . (Note that $K_{T_n}$ is a spherical shell with outer radius $R+T_n$ centered at the origin.) Altogether we obtain $T\le b''(R+t)-R$ and hence $R(Z)=R(K_T)\le b''(R+t)$ , proving (4.5).

Having established (4.5) we next note that

\begin{align*}\mathbb{P}(R(Z)> b''(R+t))&\le \mathbb{P}\biggl(\bigcup^{2d}_{i=1}\{|\eta\cap A_i(t)|\le 2d-2\}\biggr)\\&\le \sum^{2d}_{i=1}\mathbb{P}(|\eta\cap A_i(t)|\le 2d-2)\\&=\sum^{2d}_{i=1}\exp\![\!-\lambda(A_i(t))]\sum^{2d-2}_{j=0}\dfrac{\lambda(A_i(t))^j}{j!},\end{align*}

where we have used the defining properties of a Poisson process to obtain the final equality. By (2.1) we have

\begin{align*}\lambda(A_i(t))=\gamma t\,\mathbb{Q}(U_i).\end{align*}

Setting $a\,{:\!=}\, \min\{\mathbb{Q}(U_i)\colon i\in[2d]\}$ and using the fact that $\mathbb{Q}(U_i)\le 1$ for each $i\in[2d]$ , we obtain

\begin{align*}\mathbb{P}(R(Z)> b(R+t))\le 2d\,{\textrm{e}}^{-\gamma a t}\sum^{2d-2}_{j=0}\dfrac{\gamma^j}{j!}t^j.\end{align*}

This implies (4.1) for suitably chosen $c_1,c_2$ .

Remark 4.1. The stopping set Z in Theorem 4.1 depends measurably on $\Phi\cap K^c$ (is a measurable function of $\Phi\cap K^c$ ). This follows from the definition of the algorithm, but also from the following argument, which applies to general stopping sets Z with the property $Z\subset K^c$ . By standard properties of random closed sets it suffices to check for each compact $F\subset {\mathbb R}^d$ that $\{Z\cap F=\emptyset\}\in \sigma(\eta\cap K^c)$ . Since $Z\subset K^c$ we have $\{Z\cap F=\emptyset\}=\{Z\cap (F\cup K)=\emptyset\}$ . Since $F\cup K$ is compact, there is a decreasing sequence $(U_n)_{n\ge 1}$ of open sets with intersection $F\cup K$ and such that

\begin{align*}\{Z\cap (F\cup K)=\emptyset\}=\bigcup^\infty_{n=1}\{Z\cap U_n=\emptyset\}=\bigcup^\infty_{n=1}\{Z\subset U^c_n\}.\end{align*}

Since Z is a $\Phi$ -stopping set we find that the above right-hand side is contained in $\cup^\infty_{n=1}\sigma(\Phi_{U_n^c})\subset\sigma(\Phi_{K^c})$ , as asserted.

Theorem 4.1 implies the announced strong rigidity properties of the intersection processes.

The rigidity property in Theorem 4.2 is considerably stronger than the strong rigidity studied in [Reference Ghosh and Lebowitz7]. The random measure $(\Phi_m)_B$ is determined not only by $(\Phi_m)_{B^c}$ but already by $(\Phi_m)_{Z}$ for an exponentially small stopping set $Z\subset B^c$ .

5. Hyperfluctuating Cox processes and thinnings

In this section we briefly discuss two close relatives of the random measures $\Phi_1,\ldots,\Phi_d$ that have similar second-order properties but are not strongly rigid. To this end we use randomization.

Consider, for $m\in\{1,\ldots,d\}$ , a Cox process $\Psi_m$ directed by $\Phi_m$ [Reference Last and Penrose13, Chapter 13]. This means that the conditional distribution of $\Psi_m$ given $\Phi_m$ is that of a Poisson process with intensity measure $\Phi_m$ . For $m=d$ this point process can be interpreted as a multiset (or a random measure). Each point of $\Phi_m$ gets (independently of the other points) a random multiplicity having a Poisson distribution of mean 1. Let $B\subset{\mathbb R}^d$ be a bounded Borel set. Then the well-known conditional variance formula (together with the stationarity of $\Phi_m$ ) implies that

\begin{align*}\operatorname{Var}\![\Psi_m(B)]=\gamma_mV_d(B)+\operatorname{Var}\![\Phi_m(B)],\end{align*}

where $\gamma_m$ is the intensity of $\Phi_m$ ; see [Reference Last and Penrose13, Proposition 13.6]. By (2.4), $\Psi_m(B)$ has the same variance asymptotics as $\Phi_m(B)$ . In particular, $\Psi_m$ is (for $d\ge 2$ ) hyperfluctuating. However, $\Psi_m$ is not rigid. For example, given a Borel set B with positive volume, $\Psi_m(B)$ is not determined by the restriction of $\Psi_m$ to the complement of B.

In the case of the intersection point process $\Phi$ there is an even simpler way of randomizing, namely to form a p-thinning $\Phi_p$ of $\Phi$ for some $p\in(0,1)$ . Formally, given $\Phi$ , the points of $\Phi$ are taken independently of each other as points of $\Phi_p$ with probability p [Reference Last and Penrose13, Section 5.3]. This point process is not rigid. A simple calculation (using the conditional variance formula, for instance) shows that

\begin{align*}\operatorname{Var}\![\Phi_p(B)]=p^2\operatorname{Var}\![\Phi(B)]+p(1-p)\mathbb{E}[\Phi(B)],\end{align*}

so that $\Phi_p$ inherits the variance asymptotics from $\Phi$ . It also not hard to see that the pair correlation function of $\Phi_p$ is the same as that of $\Phi$ and hence given by the slowly decaying function (2.6).

6. Concluding remarks

We have shown that the intersection point process $\Phi$ associated with a stationary Poisson hyperplane process is rigid in a very strong sense. This holds for any directional distribution that is not concentrated on a great subsphere, and in particular for the uniform distribution (i.e. the isotropic case). On the other hand, $\Phi$ is hyperfluctuating. Hence hyperuniformity is not necessary for rigidity, as (weakly) conjectured in [Reference Ghosh and Lebowitz6]. However, we completely agree with Ghosh and Lebowitz [Reference Ghosh and Lebowitz6] that the precise relationships between rigidity and hyperuniformity constitute an interesting intriguing problem. We believe in the existence of generic point process assumptions that need to be added to rigidity to conclude hyperuniformity. Preferably these assumptions should be as minimal as possible.