# Central Limit Theorem for Euclidean Minimal Spanning Acycles

Primoz Skraba  School of Mathematical Sciences, Queen Mary University of
London, London<EMAIL_ADDRESS>and  D. Yogeshwaran  Theoretical
Statistics and Mathematics Unit, Indian Statistical Institute, Bangalore.
<EMAIL_ADDRESS>
###### Abstract.

We investigate asymptotics for the minimal spanning acycles of the
(Alpha)-Delaunay complex on a stationary Poisson process on
$\mathbb{R}^{d},d\geq 2$. Minimal spanning acycles are topological (or higher-
dimensional) generalization of minimal spanning trees. We establish a central
limit theorem for total weight of the minimal spanning acycle on a Poisson-
Delaunay complex. Our approach also allows us to establish central limit
theorems for sum of birth times and lifetimes in the persistent diagram of the
Delaunay complex. The key to our proof is in showing the so-called weak
stabilization of minimal spanning acycles which proceeds by establishing
suitable chain maps and uses matroidal properties of minimal spanning acycles.
In contrast to the proof of weak-stabilization for Euclidean minimal spanning
trees via percolation-theoretic estimates, our weak-stabilization proof is
algebraic in nature and provides an alternative proof even in the case of
minimal spanning trees.

###### Key words and phrases:

Poisson process, Delaunay complex, Minimal spanning acycles, Persistence
diagrams, Stabilization, Central limit theorem.

###### 2020 Mathematics Subject Classification:

60G55, 60F05, 60D05, 60B99 55U10

##  1\. Introduction

Let $\mathcal{P}_{n}=\\{X_{1},\ldots,X_{N_{n}}\\}$ be the restriction of a
stationary Poisson point process $\mathcal{P}$ with intensity $\lambda>0$ to
the window $W_{n}:=\left[-\frac{n^{1/d}}{2},\frac{n^{1/d}}{2}\right]^{d}$.
Equivalently, $N_{n}$ is a Poisson($\lambda n$) random variable and $X_{i}$’s
are i.i.d. uniform points in $W_{n}$ independent of $N_{n}$. Consider the
complete graph on $\mathcal{P}_{n}$ with edge-weights given by the Euclidean
distance between the points. A classical problem at the intersection of
combinatorial optimization and geometric probability is to investigate the
total edge-lengths (or total weighted edge-length) of the minimal spanning
tree on this weighted graph. Strong laws for this statistic and many such
Euclidean optimization functionals were proven using subadditive ergodic
theory methods; see Steele [41], Yukich [44]. For the case of sum of power-
weighted edge-lengths, i.e., edge-lengths raised to $d$-th power, a strong law
was also proven using local weak convergence ideas; see Aldous and Steele [1].
The central limit theorem for the same was remarked to be a difficult problem
in [1]. It was solved independently by Alexander [2] and Kesten and Lee [25].
The former used an approach proposed by Ramey [38] in $d=2$ while the latter
used a martingale-difference central limit theorem which worked in all
dimensions and for sum of weighted edge-lengths as well. Both proofs, however,
use certain percolation-theoretic estimates. The aim of this article is to
prove a central limit theorem (CLT) for a topological generalization of
minimal spanning trees called minimal spanning acycles on weighted Poisson-
Delaunay complexes. The main challenge in this extension is the lack of
percolation-theoretic analogue in higher dimensions. Strong laws for
statistics of minimal spanning acycles follow from the results of [14] where
sub-additive ergodic theory methods are used.

The rest of the article is organized as follows. In Section 1.1, we briefly
introduce our model and state our main results. We also discuss our proof
strategy and compare our results with those in the existing literature. In
Section 2, we introduce the necessary topological and probabilistic
preliminaries. All our proofs are contained in Section 3. As it may be of
independent interest and is more easily understandable, we give an overview of
our proof for case of minimal spanning trees in Section 3.1. At the beginning
of each section, we give a more detailed description of the subsections
therein. Though we shall introduce all the necessary topological notions to
understand all our theorem statements, some of the proofs (in particular those
in Section 3.3 and 3.4) shall assume some basic knowledge of algebraic
topology.

###  1.1. Model and main results

For more formal definition of (simplicial) complexes, minimal spanning acycles
and their relation to homology, we refer the reader to Section 2. Here, we
will give a formal definition of Delaunay complexes but shall define minimal
spanning acycles informally. This shall aid in an easier presentation of
results.

Figure 1.  The Voronoi diagram (boundary of Voronoi cells are in blue) on a
point-set (Poisson process) in $\mathbb{R}^{2}$ and the dual Delauany complex
(with edges in red).

#### Delaunay Complex.

Let ${\mathcal{X}}\subset\mathbb{R}^{d}$ be a locally-finite point-set with
points in general position. Recall that general position means that no three
points are colinear and no $d+2$ points lie on a common sphere, i.e., are
cocircular. We define the Voronoi cell of $x\in{\mathcal{X}}$ as

$\mathrm{Vor}_{{\mathcal{X}}}(x):=\\{y:|y-x|\leq|y-x^{\prime}|,\forall
x^{\prime}\in{\mathcal{X}}\\},$

i.e., the set of points in $\mathbb{R}^{d}$ whose closest point in
${\mathcal{X}}$ is $x$. Each $\mathrm{Vor}_{{\mathcal{X}}}(x)$ is a convex
polyhedron and the collection
$\\{\mathrm{Vor}_{{\mathcal{X}}}(x)\\}_{x\in{\mathcal{X}}}$ forms a partition
of $\mathbb{R}^{d}$ with disjoint interiors known as the Voronoi diagram or
tessellation. See Figure 1 for an example.

######  Definition 1.1 (Delaunay Complex).

Let ${\mathcal{X}}\subset\mathbb{R}^{d}$ be a locally-finite point-set with
points in general position. The Delaunay complex on ${\mathcal{X}}$, denoted
as $\mathcal{D}({\mathcal{X}})$ is the following simplicial complex:

$\mathcal{D}({\mathcal{X}}):=\cup_{k=0}^{\infty}\\{[x_{0},\ldots,x_{k}]:\cap_{i=0}^{k}\mathrm{Vor}_{{\mathcal{X}}}(x_{i})\neq\emptyset\\}.$

The element $[x_{0},\ldots,x_{k}]$ is called a $k$-face of the Delaunay
complex and the collection of $k$-faces of the Delaunay complex is denoted by
$\mathcal{F}_{k}({\mathcal{X}})$. Generic faces of
$\mathcal{D}({\mathcal{X}})$ is denoted by $\sigma,\tau$ et al. The Delaunay
graph on ${\mathcal{X}}$ is the graph with vertex set ${\mathcal{X}}$ and
edge-set given by $1$-faces. We define the weight function on the Delaunay
complex as follows :

$w([x_{0},\ldots,x_{k}])=\inf\\{s:\cap_{i=0}^{k}B_{s}(x_{i})\cap\mathrm{Vor}_{{\mathcal{X}}}(x_{i})\neq\emptyset\\}$

where $B_{s}(x_{i})$ denotes the ball of radius $s$ centered on $x_{i}$.

It is a standard fact that if points are in general position, the Delanauy
complex and the Voronoi diagram are dual to one another and that each simplex
in the Delaunay complex corresponds to an empty circumsphere containing its
vertices, with the weight being the radius of this sphere. The above weighted
(simplicial) complex is also known as the Alpha-Delaunay complex. A closely
related weight function

$w^{\prime}([x_{0},\ldots,x_{k}])=\inf\\{s:\cap_{i=0}^{k}B_{s}(x_{i})\neq\emptyset\\},\,[x_{0},\ldots,x_{k}]\in\mathcal{D}({\mathcal{X}})$

gives rise to the Delaunay-Čech complex; see Bauer and Edelsbrunner [4,
Section 3]. Our results apply to Delaunay-Čech complex as well but we restrict
to Alpha-Delaunay complex for convenience, referring to it simply as the
Delaunay complex.

The dimension of the Delaunay complex is the dimension of the largest face,
which under the general position assumption, is the dimension of the ambient
space - $d$.

#### Minimal spanning acycles.

(a)

(b)

(c)

Figure 2.  In $\mathbb{R}^{3}$ (A) a minimum spanning tree and (B,C) two
examples of MSAs. In the latter, the blue faces are in MSA and the green faces
are not in MSA. Both the figures correspond to Delaunay complexes on the
Poisson process.

We now introduce spanning acycles and minimal spanning acycles (MSA) on a
Delaunay complex informally. Set the $0$-spanning acycle to be empty set. A
$1$-spanning acycle on the Delaunay complex is simply a spanning tree on the
Delaunay graph. Recall that a spanning tree is a collection of edges that does
not contain any cycles, i.e., does not enclose any $1$-dimensional holes, and
is connected. See Figure 2(A) for simulation of a minimal spanning tree on a
Delaunay graph when ${\mathcal{X}}$ is a Poisson process in $\mathbb{R}^{3}$.
A $k$-spanning acycle is a collection of $k$-faces of the Delaunay complex
that do not enclose $k$-dimensional holes and also fills in (i.e. bounds) all
possible $(k-1)$-dimensional holes enclosed by all the $(k-1)$-faces, i.e.,
$\mathcal{F}_{k-1}({\mathcal{X}})$. For example, when $k=d$, one cannot create
any $d$-dimensional holes and to fill in all $(d-1)$-dimensional holes, all
the $d$-faces must be included and so the spanning acycle is
$\mathcal{F}_{d}({\mathcal{X}})$. Given a spanning acycle (or any collection
of faces), one can define the weight of the spanning acycle to be the sum of
weights of faces in the spanning acycle i.e., if
$M\subset\mathcal{F}_{k}({\mathcal{X}})$ is a $k$-spanning acycle, then

$w(M):=\sum_{\sigma\in M}w(\sigma).$

Immediately, one can define a minimal spanning acycle as a spanning acycle
with minimum weight. If the weights on faces (of a fixed dimension $k$) are
unique, which is the case when ${\mathcal{X}}$ is in general position, then
there is a unique minimal $k$-spanning acycle (MSA). When unique, we denote
the MSA on $\mathcal{D}({\mathcal{X}})$ by $MSA({\mathcal{X}})$ with the
dependence on $k$ suppressed for convenience. Figures 2(B,C) shows two
simulations of $2$-MSAs when ${\mathcal{X}}$ is a Poisson process in
$\mathbb{R}^{3}$.

Though the concept of spanning acycles was introduced by Kalai [23] in 1983,
minimal spanning acycles have only received attention in recent years [16] and
especially in the context of random simplicial complexes [19, 40, 18, 24].

#### Poisson-Delaunay Complexes.

The object of interest to us are MSAs on the Poisson-Delaunay complex. We take
${\mathcal{X}}=\mathcal{P}$, the stationary Poisson point process of intensity
$\lambda>0$ and consider the Delaunay complex $\mathcal{D}(\mathcal{P})$. More
specifically, we set $\mathcal{P}_{n}:=\mathcal{P}\cap W_{n}$, the restriction
of the stationary Poisson process to the window
$W_{n}=[\frac{-n^{1/d}}{2},\frac{n^{1/d}}{2}]$ and investigate the asymptotic
behaviour for $k$-minimal spanning acycles on the sequence of Delaunay
complexes $\mathcal{D}(\mathcal{P}_{n})$. Since the face-weights for a fixed
dimension $k$ are a.s. distinct, we have that
$\operatorname{MSA}(\mathcal{P}_{n}):=\operatorname{MSA}(\mathcal{D}(\mathcal{P}_{n}))$
is a.s. unique by Skraba et al. [40, Lemma 25]. The statistic of interest for
us is the sum of face-weights defined as

(1)
$\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})=\mathbf{M}^{\phi}_{k}(\mathcal{D}(\mathcal{P}_{n})):=\sum_{\sigma\in\operatorname{MSA}(\mathcal{P}_{n})}\phi(w(\sigma)),$

where $\phi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ is a strictly increasing
function. We denote $\mathbf{M}^{\phi}_{k}$ by $\mathbf{M}_{k}$ when $\phi$ is
identity. From the relation between persistent homology and minimal spanning
acycles (see Theorem 2.2), we know that $\mathbf{M}_{k}(\mathcal{P}_{n})$ is
the sum of death times in the persistence diagram of
$\mathcal{D}(\mathcal{P}_{n})$. With this connection, it is natural also to
study sum of birth times as well a sum of lifetimes in a persistence diagram.
We define them as

(2) $\displaystyle\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})$
$\displaystyle:=\mathbf{B}^{\phi}_{k}(\mathcal{D}(\mathcal{P}_{n}))=\smashoperator[]{\sum_{\sigma\in\mathcal{F}_{k}(\mathcal{P}_{n})\setminus
MSA(\mathcal{P}_{n})}^{}}\phi(w(\sigma))$ (3)
$\displaystyle\mathbf{L}_{k}(\mathcal{P}_{n})$
$\displaystyle:=\mathbf{L}_{k}(\mathcal{D}(\mathcal{P}_{n}))=\mathbf{M}_{k}(\mathcal{P}_{n})-\mathbf{B}_{k-1}(\mathcal{P}_{n}).$

Note that trivially $B_{0}(\mathcal{P}_{n})=0$ as
$\mathcal{F}_{0}(\mathcal{P}_{n})=\mathcal{P}_{n},\operatorname{MSA}_{0}(\mathcal{P}_{n})=\emptyset$
and $w(v)=0$ for all $v\in\mathcal{P}_{n}$. Thus,
$\mathbf{L}_{1}(\mathcal{P}_{n})=\mathbf{M}_{1}(\mathcal{P}_{n})$ (the total
edge-length of minimal spanning tree).

Strong laws for $\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})$ and
$\mathbf{L}_{k}(\mathcal{P}_{n})$ can be deduced from strong laws for
$\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})$ and
$\mathbf{F}^{\phi}_{k}(\mathcal{P}_{n})$. Strong laws and central limit
theorem for
$\mathbf{F}^{\phi}_{k}(\mathcal{P}_{n}):=\sum_{\sigma\in\mathcal{F}_{k}(\mathcal{P}_{n})}\phi(w(\sigma))$
can be deduced from Penrose and Yukich [36, Theorem 3.2] and Penrose and
Yukich [35, Theorem 2.1]. Strong laws for
$\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})$ follow from Divol and Polonik [14,
Theorem 6]. Hence, we focus on central limit theorems for
$\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})$,
$\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})$ and
$\mathbf{L}_{k}(\mathcal{P}_{n})$.

#### Weak Stabilization and central limit theorem.

Our first main result is to show a weak stabilization result for sum of death
times, birth times and lifetimes of persistent diagrams of weighted Poisson-
Delaunay complexes.

Let $A_{n}$ be sequence of boxes (i.e., $A_{n}=W_{m}+x$ for some $m\geq 1$ and
$x\in\mathbb{R}^{d}$) such that $A_{n}\to\mathbb{R}^{d}$; see Section 2.4 for
precise definition of boxes ($\mathfrak{A}$) and convergence of sets.

######  Proposition 1.2.

Let $1\leq k\leq d$ and $\phi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a strictly
increasing function. Let $A_{n}$ be defined as above and
$\mathcal{P}_{n}=\mathcal{P}\cap A_{n}$. All three statistics -
$\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n}),\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})$,
and $\mathbf{L}_{k}(\mathcal{P}_{n})$ \- satisfy weak stabilization as in (5)
i.e., as $n\to\infty$

(4)
$D_{\textbf{0}}\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n}):=\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n}\cup\\{0\\})-\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})\to
D_{\infty}(\mathbf{M}^{\phi}_{k}),\,\,\mbox{a.s.},\quad$

where $D_{\infty}(\mathbf{M}^{\phi}_{k})$ is an a.s. finite random variable
and similarly for $\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})$ and
$\mathbf{L}_{k}(\mathcal{P}_{n})$.

Kesten and Lee [25] introduced the the notion of weak stabilization to prove a
central limit theorem for Euclidean minimal spanning trees and this was
abstracted to the above form of weak stabilization for general Poisson
functionals in Penrose and Yukich [35]. This was further improved by Trinh
[42]; see Theorem 2.3. We now state our central limit theorem for the sum of
birth times, death times and lifetimes. We will need to impose a growth
assumption on the weight function $\phi$ to verify certain moment conditions.

######  Theorem 1.3.

Let $\phi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a strictly increasing function
such that $\phi(t)\leq Ct^{p},t\geq 0$ for some $p>0$. Then, there exist
constants $\sigma^{2}(\mathbf{M}_{k},\phi)\in(0,\infty),1\leq k\leq d$ and
$\sigma^{2}(\mathbf{B}_{k},\phi),\sigma^{2}(\mathbf{L}_{k})\in(0,\infty),$ for
$1\leq k\leq d-1$ such that the following hold. As $n\to\infty$, for $1\leq
k\leq d$,

$n^{-1}\mathsf{VAR}\\!\left(\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})\right)\to\sigma^{2}(\mathbf{M}_{k},\phi),\,\,n^{-1/2}\left[\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})-\mathbb{E}\\!\left\\{\mathbf{M}^{\phi}_{k}(\mathcal{P}_{n})\right\\}\right]\
{\Rightarrow}\ N(0,\sigma^{2}(\mathbf{M}_{k},\phi)),$

and for $1\leq k\leq d-1$,

$n^{-1}\mathsf{VAR}\\!\left(\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})\right)\to\sigma^{2}(\mathbf{B}_{k},\phi),\,\,n^{-1/2}\left[\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})-\mathbb{E}\\!\left\\{\mathbf{B}^{\phi}_{k}(\mathcal{P}_{n})\right\\}\right]\
{\Rightarrow}\ N(0,\sigma^{2}(\mathbf{B}_{k},\phi)),$

and

$n^{-1}\mathsf{VAR}\\!\left(\mathbf{L}_{k}(\mathcal{P}_{n})\right)\to\sigma^{2}(\mathbf{L}_{k}),\,\,n^{-1/2}\left[\mathbf{L}_{k}(\mathcal{P}_{n})-\mathbb{E}\\!\left\\{\mathbf{L}_{k}(\mathcal{P}_{n})\right\\}\right]\
{\Rightarrow}\ N(0,\sigma^{2}(\mathbf{L}_{k})),$

where $\Rightarrow$ denotes convergence in distribution and $N(0,\sigma^{2})$
denotes the Normal random variable with mean $0$ and variance
$\sigma^{2}\in[0,\infty)$.

For $k=1$, since $\mathbf{M}^{\phi}_{1}$ is the $\phi$-weighted sum of edges
on a minimal spanning tree, weak stabilization and central limit theorem
follow from the results of Kesten and Lee [25] (see also Lee [29, Proposition
1], Lee [30, Proposition 1] and Penrose and Yukich [37, Lemma 2.1]), but these
proofs use percolation properties of the the Poisson-Boolean model
$\cup_{X\in\mathcal{P}}B_{r}(X),r\geq 0$. With the study of homological
percolation still in a nascent stage (see Skraba and Bobrowski [39]), proof of
weak stabilization in higher-dimensions necessitates a different approach. Our
proof relies mainly upon local-finiteness of the weighted Delaunay graph,
existence of certain homomorphisms between chain complexes and also implicitly
that minimal spanning acycles can be constructed via greedy algorithms. We
discuss the proof in more detail at the end of this section. Also to follow
our proof ideas better, we give a proof overview in the case of minimal
spanning tree in Section 3.1 where we consider
$\mathcal{D}\cap\mathcal{P}_{n}$ instead of $\mathcal{D}(\mathcal{P}_{n})$.
The difference between $\mathcal{D}\cap\mathcal{P}_{n}$ and
$\mathcal{D}(\mathcal{P}_{n})$ lies in the boundary effects. While this
doesn’t significantly affect the percolation theoretic approach, our approach
necessitates the use of suitable chain homomorphisms to overcome the boundary
effects. In the case of $\mathcal{D}\cap\mathcal{P}_{n}$, one can use
combinatorial arguments to deduce stabilization of the MSA, but for
$\mathcal{D}(\mathcal{P}_{n})$, simplices may disappear with increasing window
size. So rather than rely on monotoncity, we resort to the existence of
certain chain maps (Section 3.4), which requires more algebraic arguments (see
Section 3.3).

The main advantage of our approach is that it requires no change when going
from minimal spanning trees to minimal spanning acycles. We use the randomness
of the point process in controlling the stabilization of $\mathcal{D}$. This
can be extended to fairly general point processes, see Błaszczyszyn et al. [6,
Theorem 2.5] and the discussion therein. However, the central limit theorem
which relies heavily on Theorem 2.3, does require the Poisson point process
assumption.

We now comment on the use of weak stabilization in random topology and
connections to our result. Weak stabilization has been a crucial tool to prove
central limit theorems for topological statistics in recent years. This is
mainly because other stronger notions of stabilization are insufficient to
handle long-range dependence of topological statistics especially in the
presence of percolation in the Poisson-Boolean model. In Yogeshwaran et al.
[43], weak stabilization was shown for Betti numbers and later this was
extended to persistent Betti numbers in Hiraoka et al. [21], Krebs and Polonik
[26]. The statistics of minimal spanning acycle have more global dependence
than Betti numbers and persistent Betti numbers and hence the methods do not
naturally extend to minimal spanning acycles. The relation between Betti
numbers and total lifetime sum ($\mathbf{L}_{k}$) can be exploited to prove
weak stabilization of $\mathbf{L}_{k}$ as in the case of random cubical
complexes in Hiraoka and Tsunoda [20]. But this does not extend to the weight
of a minimal spanning acycle (equivalently death times in the persistence
diagram). In all these works, weak stabilization was shown en-route to the
proof of central limit theorem for these statistics. Proposition 1.2 and
Theorem 1.3 significantly extend these results by proving stabilization not
only for lifetime sums but also more generally for weight of a minimal
spanning acycle and its complement. Recently strong stabilization has been
shown for persistent Betti numbers in [26] but it is unclear whether this can
be extended to minimal spanning acycles.

We now mention some possible extensions and related results in non-geometric
or mean-field models. Quantifying the convergence in (4) via percolation-
theoretic estimates for the Poisson-Boolean model has been used to prove
normal approximation results for Euclidean minimal spanning trees in
Chatterjee and Sen [11], Lachièze-Rey et al. [27]. Though one would expect
this to hold for minimal spanning acycles, a proof is far from obvious at this
stage. The results of [26] may be considered a first step towards such a
quantification and in also extending central limit theorems in [43, 21] to
inhomogeneous Poisson processes and Binomial point processes.

In a different direction, central limit theorem for minimal spanning trees on
randomly weighted complete graphs was proven in Janson [22]. Strong laws for
lifetime sums have been shown for simplicial complex versions of randomly
weighted complete graphs in Hino and Kanazawa [18] using the relation between
Betti numbers and lifetime sums. A central limit theorem still evades us in
these models and again the stabilization-based approach of Cao [8] offers
promise.

#### Discussion of proofs:

We end the introduction with a detailed sketch of our proofs. As is obvious
from the above discussions, the key result is Proposition 1.2 and then
applying Theorem 2.3, we obtain the central limit theorem - Theorem 1.3. The
crucial step towards the proof of Proposition 1.2 is in understanding
stabilization when $A_{n}=W_{n}$ i.e., a sequence of centred boxes.
Proposition 3.14 proves stabilization in this case and we shall outline here
this proof alone.

One of the technical difficulties in proving stabilization along windows
$W_{n}$ (i.e., Proposition 3.14) lies in overcoming the boundary effects in
the Delaunay complex. More precisely, it is easier to show weak stabilization
for $\mathcal{D}(\mathcal{P})\cap W_{n}$ but what is required is weak
stabilization of $\mathcal{D}(\mathcal{P}_{n})$. The former sequence of
complexes satisfy monotonicity in $n$ but the latter do not. We overcome this
via by passing to the nerve of covers induced by the Voronoi diagrams and
using chain maps between $\mathcal{D}(\mathcal{P}_{n})$ and
$\mathcal{D}(\mathcal{P}_{m})$ for $n<m$.

The starting point of our proof strategy is to decompose addition of the
origin into a.s. a finite number of changes in the complex locally around the
origin. By showing that the effect of these elementary changes stabilizes for
Delaunay complexes, we show that the effect of adding the origin stabilizes.
More precisely, denoting by $\mathcal{D}$ the Delaunay complex on
$\mathcal{P}$ and $\mathring{\mathcal{D}}$ the Delaunay complex on
$\mathcal{P}\cup\\{\textbf{0}\\}$, we show the following statements (either
a.s. or pointwise):

  1. (1)

The removal and addition of simplices to go from $\mathcal{D}$ to
$\mathring{\mathcal{D}}$ happens in $W_{N}$ for some $N$ (random but a.s.
finite); Proposition 3.12.

  2. (2)

Thus for $m>N$,
$\mathbf{M}^{\phi}_{k}(\mathcal{D}(P_{m}\cup\\{\textbf{0}\\}))-\mathbf{M}^{\phi}_{k}(\mathcal{D}(\mathcal{P}_{m}))$
can be expressed as sum of finite differences of the form
$\mathbf{M}^{\phi}_{k}(\mathcal{D}^{\prime}_{m})-\mathbf{M}^{\phi}_{k}(\mathcal{D}_{m})$
such that $\mathcal{D}^{\prime}_{m},\mathcal{D}_{m}$ are obtained from
$\mathcal{D}(\mathcal{P}_{m})$ or $\mathcal{D}(P_{m}\cup\\{\textbf{0}\\})$ by
the removal of finitely many simplices and furthermore
$\mathcal{D}^{\prime}_{m}$ and $\mathcal{D}_{m}$ differ by at most one
simplex.

  3. (3)

Though there is no inclusion between
$\mathcal{D}^{\prime}_{m},\mathcal{D}^{\prime}_{n}$ for $n>m$ (resp.
$\mathcal{D}_{m},\mathcal{D}_{n}$), we show existence of appropriate chain
maps between $\mathcal{D}^{\prime}_{m}$ and $\mathcal{D}^{\prime}_{n}$ (resp.
between $\mathcal{D}_{m}$ and $\mathcal{D}_{n}$); see Section 3.4.

  4. (4)

Then, using a series of lemmas (Section 3.3) that analyse stabilization under
chain maps when one simplex is added or removed, we show in Proposition 3.14
that
$\mathbf{M}^{\phi}(\mathcal{D}^{\prime}_{m})-\mathbf{M}^{\phi}(\mathcal{D}_{m})$
converges as $m\to\infty$.

  5. (5)

To show that the limiting variance is non-degenerate, we show that limit of
$\mathcal{D}(P_{m}\cup\\{\textbf{0}\\})-\mathcal{D}(\mathcal{P}_{m})$ is a
non-zero random variable by constructing some specific configurations for
which the limiting random variable is strictly greater than zero with positive
probability; see Section 3.7.

For ease of understanding the main points of the above proof strategy and for
the benefit of the readers interested in the case of minimal spanning trees,
we give a proof overview for the special case of $k=1$ and where $\phi$ is
identity in Section 3.1.

Also, as mentioned below Definition 1.1, our proof also works for Delaunay-
Čech complex. All the above steps follow straightforwardly for the Delaunay-
Čech case except that of variance lower bound proof. The latter uses specific
constructions which must be suitably modified (see Remark 3.20).

##  2\. Preliminaries

Weighted complexes, spanning acycles and connection to persistent homology are
introduced respectively in Sections 2.1, 2.2 and 2.3. Section 2.4 introduces
Poisson process and recalls the general central limit theorem for functionals
of Poisson process from Trinh [42].

For more on algebraic topology notions considered in this paper, we refer the
reader to Edelsbrunner and Harer [15], Munkres [32], Hatcher [17].

###  2.1. Weighted complexes

We introduce weighted (simplicial) complexes and the associated filtration. A
(simplicial) complex $\mathcal{K}$ on a vertex set $V$ is a collection of
subsets of $\mathcal{K}$ such that if $\sigma\in\mathcal{K}$ and
$\tau\subset\sigma$ then $\tau\in\mathcal{K}.$ We shall assume that
$V\subset\mathcal{K}$. Elements of $\mathcal{K}$ are called faces or simplices
and faces of cardinality $(k+1)$ are called as $k$-dimensional faces or
simplices. We represent a $k$-dimensional face $\tau$ by
$[v_{0},\ldots,v_{k}]$ where $v_{i}\in V$, $i=0,\ldots,k$. A weighted complex
is a complex equipped with a weight function
$w:\mathcal{K}\rightarrow\mathbb{R}$. We shall assume that all our weight
functions on a simplicial complex are monotone i.e., for all
$\alpha\in\mathbb{R}$, the preimage $w^{-1}(-\infty,\alpha]$ is a simplicial
complex. The sub-complex of $\mathcal{K}$ consisting of only $k$-faces and
lower is called the $k$-skeleton $\mathcal{K}_{k}$ i.e.,
$\mathcal{K}_{k}=\cup_{i=0}^{k}\mathcal{F}_{i}(\mathcal{K})$. Given a weighted
complex $\mathcal{K}$, we can define the following two filtrations :

$\mathcal{K}(t):=\\{\sigma\in\mathcal{K}:w(\sigma)\leq
t\\},\,\,\mathcal{K}(t^{-}):=\\{\sigma\in\mathcal{K}:w(\sigma)<t\\},\,\,t\geq
0.$

Also, given two weighted complexes $\mathcal{K},\mathcal{L}$ with respective
weight functions $w,w^{\prime}$, we say $\mathcal{K}\subset\mathcal{L}$ if
$\mathcal{K}$ is a subcomplex of $\mathcal{L}$ (i.e, the simplices of
$\mathcal{K}$ are also in $\mathcal{L}$) and $w(\tau)=w^{\prime}(\tau)$ for
all $\tau\in\mathcal{K}$. For a weighted complex $\mathcal{K}$ and $\sigma$, a
simplex, we denote by $\mathcal{K}(\sigma^{-})=\mathcal{K}(w(\sigma)^{-}).$

Given a simplicial complex $\mathcal{K}$ and $k\geq 0$, let
$C_{k}(\mathcal{K}),B_{k}(\mathcal{K})$ and $Z_{k}(\mathcal{K})$ denote the
$k$th-chain group, $k$-th boundary group and $k$-th cycle group
respectively111It will be clear from context whether the boundary group or a
ball is denoted by $B$.. These are defined via the boundary operator
$\partial_{k}:C_{k}(\mathcal{K})\rightarrow C_{k-1}(\mathcal{K})$, where
$Z_{k}(\mathcal{K})$ the kernel of $\partial_{k}$ and $B_{k}$ is the image of
$\partial_{k+1}$. The definition for $\partial$ is standard and we do not
repeat it here. Also it is customary to suppress the subscript $k$ and we
shall do so in future.

Set $C_{-1}(\mathcal{K})=\mathbb{F}$, where $\mathbb{F}$ is our coefficient
field. Since our coefficients are over a field $\mathbb{F}$, all our groups
are actually $\mathbb{F}$-vector spaces. We define the (reduced) $k$-th
homology group $\mathrm{H}_{k}(\mathcal{K})$ as the quotient group
$\mathrm{H}_{k}(\mathcal{K}):=Z_{k}(\mathcal{K})/B_{k}(\mathcal{K}).$ The rank
of $\mathrm{H}_{k}(\mathcal{K})$ is called as the $k$-th Betti number
$\beta_{k}(\mathcal{K})$.

###  2.2. Minimal spanning acycles

For a more detailed exposition on spanning acycles, we refer the reader to
Skraba et al. [40, Section 2.1].

We now introduce spanning acycles. A subset $S\subset\mathcal{F}_{k}$ is said
to be a $k$-spanning acycle if $\beta_{k-1}(\mathcal{K}_{k-1}\cup
S)=\beta_{k-1}(\mathcal{K})$ and $\beta_{k}(\mathcal{K}_{k-1}\cup S)=0$. A
minimal $k$-spanning acycle is a spanning acycle $S$ that minimizes the total
weight $w(S)=\sum_{\sigma\in S}w(\sigma)$. When the index $k$ in consideration
is clear, we shall drop the index and refer to as spanning acyle and minimal
spanning acycle (MSA). When unique, we shall denote the minimal spanning
acycle by $\operatorname{MSA}$. The MSA is unique if the weight function $w$
is injective on $k$-faces [40, Lemma 31]. We refer the reader to Figure 2 for
illustrations of $2$-MSAs.

###  2.3. Relation to persistent homology

We shall now relate minimal spanning acycles to persistent homology. This is
important in understanding the implications of our results to persistent
homology and also this shall yield us the important notion of negative and
positive faces that will characterize minimal spanning acycles.

Persistent homology is an algebraic invariant which keep track of changes of
homology in $\mathrm{H}_{k}(\mathcal{K}(t))$ for a weighted complex
$\mathcal{K}$. [15, 9, 10]. More formally, we define the $(s,t)$-persistent
homology group as the quotient group

$\mathrm{H}^{s,t}_{k}(\mathcal{K})=\frac{Z_{k}(\mathcal{K}(s))}{Z_{k}(\mathcal{K}(t))\cap
B_{k}(\mathcal{K}(t))},\quad s\leq t.$

The ranks of $\mathrm{H}^{s,t}_{k}(\mathcal{K}),0\leq s\leq t\leq\infty$ can
be encoded as a collection of intervals of $\mathbb{R}_{+}$ called as
persistence barcode [45] or alternatively as a multi-set of points in called
the persistence diagram $\operatorname{Dgm}(\mathcal{K},w)$ [12]. We do not
define persistence diagrams formally here but refer to [40, Definition 9]. For
our purposes, it suffices to understand that
$\operatorname{Dgm}(\mathcal{K},w)$ is a finite subset of $\\{(s,t):0\leq
s\leq t\leq\infty\\}$ and if $(b,d)\in\operatorname{Dgm}(\mathcal{K},w)$ it
signifies that a certain homology class was ‘born’ in $\mathcal{K}(b)$ and
’died’ at $\mathcal{K}(d)$. The projection of the persistence diagram to the
$y$-axis is called the death times (denoted by $\operatorname{Dgm}_{d}$) and
the projection to the $x$-axis is called the birth times (denoted by
$\operatorname{Dgm}_{b}$). There are two important alternate characterizations
of birth and death times for us. The first is a straighforward one via Betti
numbers and the second will be via minimal spanning acycles.

######  Lemma 2.1.

([13, Section 3]) Let $\mathcal{K}$ be a finite weighted complex. If
$\sigma\in\mathcal{F}_{k}$ then
$\beta_{j}(\mathcal{K}(\sigma^{-})\cup\\{\sigma\\})=\beta_{j}(\mathcal{K}(\sigma^{-}))$
for $j\neq k,k-1$. Further, only one of the following two statements hold :

  1. (i)

(Negative face)
$\beta_{k-1}(\mathcal{K}(\sigma^{-})\cup\\{\sigma\\})=\beta_{k-1}(\mathcal{K}(\sigma^{-}))-1$
and
$\beta_{k}(\mathcal{K}(\sigma^{-})\cup\\{\sigma\\})=\beta_{k}(\mathcal{K}(\sigma^{-}))$.

  2. (ii)

(Positive face)
$\beta_{k-1}(\mathcal{K}(\sigma^{-})\cup\\{\sigma\\})=\beta_{k-1}(\mathcal{K}(\sigma^{-}))$
and
$\beta_{k}(\mathcal{K}(\sigma^{-})\cup\\{\sigma\\})=\beta_{k}(\mathcal{K}(\sigma^{-}))+1$.

Suppose that $w$ is an injective weight function. Then $w(\sigma)$ is a death
time iff it is a negative face and $w(\sigma)$ is a birth time iff it is a
positive face.

Positive faces may also be characterized by
$Z_{k}(\mathcal{K}(\sigma^{-}))\subsetneq Z_{k}(\mathcal{K}(\sigma))$ or and
negative faces by $B_{k}(\mathcal{K}(\sigma^{-}))\subsetneq
B_{k}(\mathcal{K}(\sigma))$. The first condition is equivalent to the
statement that
$\partial_{k}\sigma\in\partial_{k}C_{k}(\mathcal{K}(\sigma^{-}))$ and the
second that
$\partial_{k}\sigma\notin\partial_{k}C_{k}(\mathcal{K}(\sigma^{-}))$.

With the classification of faces as positive and negative, we can assign
labels to faces. We set $\ell(\sigma)=1$, if $\sigma$ is positive and else
$\ell(\sigma)=-1$ i.e., $\sigma$ is negative. The following theorem relating
birth and death times to MSA was proven in [40].

######  Theorem 2.2.

([40, Theorem 3]) Let $\mathcal{K}$ be a finite weighted complex with an
injective weight function $w$. Denote by
$\operatorname{Dgm}_{b},\operatorname{Dgm}_{d}$ respectively the birth and
death times of the persistent diagram $\operatorname{Dgm}(\mathcal{K},w)$.
Then we have that

$\displaystyle\operatorname{Dgm}_{d}$
$\displaystyle=\\{w(\sigma):\ell(\sigma)=-1\\}\,=\\{w(\sigma):\sigma\in\operatorname{MSA}\\}$
$\displaystyle\operatorname{Dgm}_{b}$
$\displaystyle=\\{w(\sigma):\ell(\sigma)=1\\}\quad=\\{w(\sigma):\sigma\in\mathcal{F}_{k}\setminus\operatorname{MSA}\\}.$

###  2.4. Weak stabilization and central limit theorem for Poisson functionals

We now introduce Poisson processes formally and state the central limit
theorem for statistics of Poisson processes. We refer the reader to [28, 3]
for more details on point processes and in particular, Poisson point
processes.

Let $\mathcal{N}$ be the set of all locally-finite point sets (or equivalently
simple Radon counting measures) in $\mathbb{R}^{d}$. By a locally-finite point
set ${\mathcal{X}}$, we mean a point set ${\mathcal{X}}$ such that
${\mathcal{X}}(B):=|{\mathcal{X}}\cap B|<\infty$ for all bounded Borel subsets
$B$. We shall also view ${\mathcal{X}}$ as a counting measure
$\sum_{x\in{\mathcal{X}}}\delta_{x}$ and ${\mathcal{X}}$ is said to be a
simple counting measure if ${\mathcal{X}}(\\{x\\})\in\\{0,1\\}$ for all
$x\in\mathbb{R}^{d}$. The associated $\sigma$-algebra (called the evaluation
$\sigma$-algebra) is the smallest $\sigma$-algebra such that
${\mathcal{X}}\mapsto{\mathcal{X}}(B)$ is measurable for all Borel subsets
$B\subset\mathbb{R}^{d}$. Here, we have used $|\cdot|$ to denote cardinality
and later we shall also use it to denote Lebesgue measure.

By a point process, we mean a random element of the space $\mathcal{N}$ i.e.,
a measurable mapping from a probability space
$(\Omega,\mathcal{F},\mathbb{P})$ to $\mathcal{N}$ equipped with the
evaluation $\sigma$-algebra. A point process $\mathcal{P}$ is said to be a
stationary Poisson point process on $\mathbb{R}^{d}$ with intensity $\lambda$
if it satisfies the following two properties:

  1. (1)

For every Borel subset $B\subset\mathbb{R}^{d}$, $\mathcal{P}(B)$ is a Poisson
random variable with mean $\lambda|B|$.

  2. (2)

For every $m\in\mathbb{N}$ and pairwise disjoint Borel subsets
$B_{1},\ldots,B_{m}$ of $\mathbb{R}^{d}$, the random variables
$\mathcal{P}(B_{1}),\ldots,\mathcal{P}(B_{m})$ are independent (complete
independence).

Given a bounded Borel subset $B$ of $\mathbb{R}^{d}$, the restriction of
Poisson point process to $B$ can be realized as follows:

$\mathcal{P}\cap B\stackrel{{\scriptstyle
d}}{{=}}\\{X_{1},\ldots,X_{N_{B}}\\},$

where $N_{B}$ is a Poisson random variable with mean $\lambda|B|$ and
$X_{1},X_{2},\ldots$ are i.i.d. random vectors in $\mathbb{R}^{d}$ with
uniform distribution in $B$ and independent of $N_{B}$. We note that
$\mathcal{P}$ is a locally-finite point set with points in general position.

We recall a general central limit theorem for functionals of Poisson point
processes due to [42]. Recall that
$W_{n}=\left[-\frac{n^{1/d}}{2},\frac{n^{1/d}}{2}\right]^{d}$, let
$\mathfrak{A}$ ($=\mathfrak{A}(\\{W_{n}\\})$) be the collection of all subsets
$A$ of $\mathbb{R}^{d}$ such that $A=W_{n}+x$ for some $W_{n}$ in the sequence
and some point $x\in\mathbb{R}^{d}$. For any $\mathfrak{A}$-valued sequence
$A_{n},n\geq 1$, we say that $A_{n}\to\mathbb{R}^{d}$, if $\bigcup_{n\geq
1}\bigcap_{m\geq n}A_{m}\ =\ \mathbb{R}^{d}$.

######  Theorem 2.3.

([42, Theorem 3.1]) Let $H$ be a real-valued functional defined for all finite
subsets of $\mathbb{R}^{d}$ and satisfying the following four conditions:

  1. (i)

_Translation invariance:_ $H({\mathcal{X}}+y)=H({\mathcal{X}})$ for all finite
subsets ${\mathcal{X}}\subset\mathbb{R}^{d}$ and $y\in\mathbb{R}^{d}$.

  2. (ii)

_Weak stabilization:_ $H$ is said to be weakly stabilizing if there exists a
random variable $D_{\infty}(H)$ such that for any $\mathfrak{A}$-valued
sequence $A_{n}\to\mathbb{R}^{d}$, the following holds.

(5) $\displaystyle(D_{\textbf{0}}H)(\mathcal{P}\cap
A_{n})\stackrel{{\scriptstyle a.s.}}{{\rightarrow}}D_{\infty}(H),\,\mbox{as
$n\to\infty$.}$

  3. (iii)

_Poisson bounded moments:_ $\sup_{A\in\mathfrak{A};\,0\in
A}\mathbb{E}\\!\left\\{\left[(D_{\textbf{0}}H)(\mathcal{P}\cap
A)\right]^{4}\right\\}<\infty$.

Then, there exists a constant $\sigma^{2}\geq 0$, such that, as $n\to\infty$,

$n^{-1}\mathsf{VAR}\\!\left(H(\mathcal{P}\cap
W_{n})\right)\to\sigma^{2},\qquad n^{-1/2}\left[H(\mathcal{P}\cap
W_{n})-\mathbb{E}\\!\left\\{H(\mathcal{P}\cap W_{n})\right\\}\right]\
{\Rightarrow}\ N(0,\sigma^{2}),$

where $\Rightarrow$ denotes convergence in distribution and $N(0,\sigma^{2})$
stands for normal random variable with mean $0$ and variance $\sigma^{2}$.
If $D_{\infty}(H)$ is a non-zero random variable (i.e.,
$\mathbb{P}(D_{\infty}(H)\neq 0)>0$), then $\sigma^{2}>0$.

The last statement on variance lower bound follows from [7, Remark 2.9]. The
proof in [35] uses a martingale-difference central limit theorem building upon
the results of [25]. A newer proof via Poincaré inequality was given recently
in [42, Theorem 3.1] and compared to [35], this did not require a growth
condition. We also note that the central limit theorem in [35] is stated for a
more general sequence of windows than $W_{n}$.

##  3\. Proofs

We first give a sketch of proof of stabilization for MST (i.e., in the special
case of $k=1$) in Section 3.1 expanding upon the proof overview given in the
introduction. Next we recall some basic lemmas on weighted complexes in
Section 3.2 and then prove stabilization under chain maps in Section 3.3. The
existence of chain maps between suitable Delaunay complexes is shown in
Section 3.4. We prove stabilization of Poisson Delaunay complexes in Section
3.5 and the proofs of main results are given in Section 3.6 with the proof of
variance lower bound alone postponed to Section 3.7.

The above subdivision of sections is also to segregate the deterministic parts
of the proof from the probabilistic parts. Sections 3.2-3.4 are purely
deterministic and the probabilistic proofs are in Sections 3.5-3.7.

###  3.1. Proof sketch in the case of $k=1$

To better illustrate the proof strategy sketched at the end of Section 1, we
expound upon this now in the case of $k=1$ and $\phi$ is identity. In this
case $\mathbf{M}(\mathcal{P}_{n})$ is simply the total weight of the minimal
spanning tree formed on $\mathcal{P}_{n}$. Though accounting for boundary
effects is an important part of our proof, we shall explain the proof steps
for minimal spanning tree ignoring the boundary effects. It makes it easier to
understand the crux of our proof.

Let $G:=G({\mathcal{X}})$ be the Delaunay graph on a locally-finite point set
${\mathcal{X}}$ and recall that the edge-weights $w$ is given by the distance
between the points. Consider also the Delaunay graph
$G^{\prime}:=G({\mathcal{X}}\cup\\{\textbf{0}\\})$. Let
$W_{n}=[-\frac{n^{1/d}}{2},\frac{n^{1/d}}{2}]^{d},n\geq 0$ be the sequence of
windows increasing to $\mathbb{R}^{d}$ and $G_{n},G^{\prime}_{n}$ be the
restriction of graphs $G,G^{\prime}$ to $W_{n}$. Further, let
$\operatorname{MST}_{n}:=\operatorname{MST}(G_{n})$,
$\operatorname{MST}^{\prime}_{n}:=\operatorname{MST}(G^{\prime}_{n})$ be the
corresponding MSTs and
$w(\operatorname{MST}_{n}),w(\operatorname{MST}^{\prime}_{n})$ be the total
weight of the respective MSTs. Recall that for an edge $e$, we denote the
subgraph of $G_{n}$ consisting of edges whose weight is smaller than that of
$e$ by $G_{n}(e^{-})$.

  1. (1)

Suppose that
$G_{n}^{\prime}=G_{n}-\\{e_{1},\ldots,e_{k}\\}+\\{e^{\prime}_{1},\ldots,e^{\prime}_{l}\\}$
for all $n\geq n_{0}$ and assume that the edges are all in $W_{n_{0}}$.

  2. (2)

The add-one cost for MST upon adding a point to the point process can be
decomposed as a finite sum of add-one cost (or its negative) of MST upon
adding an edge i.e.,

$\displaystyle
w(\operatorname{MST}^{\prime}_{n})-w(\operatorname{MST}_{n})=\sum_{i=1}^{k}w\big{(}\operatorname{MST}(G_{n}-\\{e_{1},\ldots,e_{i}\\})\big{)}-w\big{(}\operatorname{MST}(G_{n}-\\{e_{1},\ldots,e_{i-1}\\})\big{)}$
$\displaystyle+\sum_{i=1}^{l}w\big{(}\operatorname{MST}(G_{n}-\\{e_{1},\ldots,e_{k}\\}+\\{e^{\prime}_{1},\ldots,e^{\prime}_{i}\\})\big{)}-w\big{(}\operatorname{MST}(G_{n}-\\{e_{1},\ldots,e_{k}\\}+\\{e^{\prime}_{1},\ldots,e^{\prime}_{i-1}\\})\big{)}.$

  3. (3)

Thus, we will show convergence of add-one cost for $\operatorname{MST}_{n}$’s
of a suitable sequence of graphs under addition of a single edge and because
of the above identity, this suffices to show convergence of
$w(\operatorname{MST}^{\prime}_{n})-w(\operatorname{MST}_{n})$. Hence we may
assume that $G^{\prime}_{n}=G_{n}\cup\\{e_{0}\\}$ for $n$ large enough, say
$n\geq n_{0}$.

  4. (4)

When an edge $e_{0}$ is added to the graph, the MST can increase at most by
one and the symmetric difference of
$\operatorname{MST}_{n},\operatorname{MST}^{\prime}_{n}$ is at most two for
all $n$.

  5. (5)

Suppose $e_{0}$ is positive for $G_{n}$ for some $n\geq n_{0}$, i.e., it
creates a cycle in the graph for some $G_{n}(e_{0}^{-})$, then it must also
create a cycle for any larger graph $G_{m}(e_{0}^{-})$ for $m>n$. In this
case, the edge does not contribute to the difference of
$\operatorname{MST}_{m}$, $\operatorname{MST}_{m}^{\prime}$ for $m>n$ and so
$\operatorname{MST}_{m}=\operatorname{MST}_{m}^{\prime}$ for $m>n$.

  6. (6)

If $e_{0}$ is negative for all $n\geq n_{0}$ i.e., it reduces the number of
components when added for all $G_{n}(e_{0}^{-})$, then the following three
case can occur

    1. (a)

If $\operatorname{MST}_{m}^{\prime}=\operatorname{MST}_{m}+e_{0}$ for all
$m\geq n_{0}$ (i.e., $e_{0}$ is not part of any cycle in
$\operatorname{MST}_{m}$ for the entire sequence) then again stabilization
follows easily.

    2. (b)

If for some graph $G_{n}$,
$\operatorname{MST}_{n}\setminus\operatorname{MST}^{\prime}_{n}=e_{n}$ (for
some edge $e_{n}\in G_{n}$) then for any larger graph $G_{m}$,
$\operatorname{MST}_{m}\setminus\operatorname{MST}^{\prime}_{m}=e_{m}$ where
$w(e_{m})\leq w(e_{n})$. In other words, adding $e_{0}$ creates a cycle in
$\operatorname{MST}_{n}$ such that there is a larger edge
$e_{n}\in\operatorname{MST}_{n}$ and
$\operatorname{MST}^{\prime}_{n}=\operatorname{MST}_{n}-e_{n}+e_{0}.$ Then,
the same holds for $\operatorname{MST}_{m}$ as well with an edge $e_{m}$
($=e_{n}$ possibly) removed from $\operatorname{MST}_{m}$. Further, the edge
$w(e_{m})$ has to be at most $w(e_{n})$ else $e_{n}$ itself would have been
removed from $\operatorname{MST}_{m}$ as well.

    3. (c)

Thus
$w(\operatorname{MST}(G_{n}+e_{0}))-w(\operatorname{MST}(G_{n}))=w(e_{0})-w(e_{n})$
for all $n\geq n_{0}$ with $w(e_{n})$ being a decreasing sequence and hence
the add-one cost converges.

Formally, we must consider minimal spanning trees on $G({\mathcal{X}}_{n})$
and $G({\mathcal{X}}_{n}\cup\\{\textbf{0}\\})$. The difference between
$G({\mathcal{X}}_{n})$ and $G_{n}$ is that the latter has monotonicity in $n$
while the former does not. As discussed at the end of Section 1, this is true
for Delaunay complexes and we overcome this issue by using suitable chain maps
between $G({\mathcal{X}}_{n})$ and $G({\mathcal{X}}_{m})$ for $m>n$.

###  3.2. Basic lemmas on weighted complexes

We shall fix a $k\geq 1$ in this subsection and assume all our minimal
spanning acycles to be $k$-dimensional. Hence, for convenience, we shall drop
the subscript $k$ in all our notations. We prepare for the main proofs with
some preliminary lemmas on weighted complexes. Firstly, we recall the
stability result from [40, Theorem 4] but stated for MSAs using [40, Theorem
3].

######  Theorem 3.1.

([40, Theorem 4]) Let $\mathcal{K}$ be a finite complex with two weight
functions $w,w^{\prime}$. Let $\operatorname{MSA},\operatorname{MSA}^{\prime}$
be the two induced minimal spanning acycles respectively. Then for any
$p\in\\{0,1,\ldots,\infty\\}$ there exists a bijection between
$\pi:\operatorname{MSA}\to\operatorname{MSA}^{\prime}$ such that

$\sum_{\sigma\in\operatorname{MSA}}|w(\sigma)-w^{\prime}(\pi(\sigma))|^{p}\leq\sum_{\sigma\in\mathcal{F}_{k}}|w(\sigma)-w^{\prime}(\sigma)|^{p},$

where, $\sum_{i}|x_{i}|^{0}:=\sum_{i}\mathbf{1}[x_{i}\neq 0]$ and
$\sum_{i}|x_{i}|^{\infty}=\sup_{i}|x_{i}|$ for a real sequence $x_{i}$.

The following lemma shall help us to understand how minimal spanning acycle
changes upon addition of a simplex.

######  Lemma 3.2.

Let $\mathcal{K},\mathcal{K}_{\sigma}$ be weighted complexes on a finite point
set ${\mathcal{X}}$ such that
$\mathcal{K}_{\sigma}=\mathcal{K}\cup\\{\sigma\\}$ where $\sigma$ is a
$k$-simplex such that $\sigma\notin\mathcal{K}$ and $\mathcal{K}_{\sigma}$ is
a simplicial complex. We denote the labels of simplices on $\mathcal{K}$ by
$\ell$ and that on $\mathcal{K}_{\sigma}$ by $\ell_{\sigma}$. Then, we have
that

  1. (i)

$|\operatorname{MSA}(\mathcal{K}_{\sigma})\setminus\operatorname{MSA}(\mathcal{K})|,|\operatorname{MSA}(\mathcal{K})\setminus\operatorname{MSA}(\mathcal{K}_{\sigma})|\leq
1$ or equivalently,

$\sum_{\tau\in\mathcal{K}}\mathbf{1}(\ell(\tau)\neq\ell_{\sigma}(\tau))\leq
1.$

  2. (ii)

With the notation as above, if $\ell_{\sigma}(\sigma)=1$ then
$\operatorname{MSA}(\mathcal{K})=\operatorname{MSA}(\mathcal{K}_{\sigma})$ and
hence
$\mathbf{M}^{\phi}(\mathcal{K})=\mathbf{M}^{\phi}(\mathcal{K}_{\sigma}).$

###### Proof.

(i): This essentially follows from Theorem 3.1. We shall use $w$ to denote the
weight function on both $\mathcal{K},\mathcal{K}_{\sigma}$. Define a weighted
complex $\hat{\mathcal{K}}$ as follows :
$\hat{\mathcal{K}}=\mathcal{K}\cup\\{\sigma\\}$ where
$\hat{w}(\sigma)=\max_{\tau\in\mathcal{K}}w(\tau)+1$. Observe that
$\operatorname{MSA}(\mathcal{K})\subset\operatorname{MSA}(\hat{\mathcal{K}})\subset\operatorname{MSA}(\mathcal{K})\cup\\{\sigma\\}$.
Now, from Theorem 3.1, we have that for any $p\geq 0$, there exists a
bijection
$\Pi:\operatorname{MSA}(\mathcal{K}_{\sigma})\to\operatorname{MSA}(\hat{\mathcal{K}})$
such that

$\sum_{\tau\in\operatorname{MSA}(\mathcal{K}_{\sigma})}|w(\tau)-\hat{w}(\Pi(\tau))|^{p}\leq|\hat{w}(\sigma)-w(\sigma)|^{p}.$

For $p=0$, the above inequality is nothing but
$|\operatorname{MSA}(\mathcal{K}_{\sigma})\setminus\operatorname{MSA}(\hat{\mathcal{K}})|,|\operatorname{MSA}(\hat{\mathcal{K}})\setminus\operatorname{MSA}(\mathcal{K}_{\sigma})|\leq
1.$ Since
$\operatorname{MSA}(\mathcal{K})\subset\operatorname{MSA}(\hat{\mathcal{K}})$,
first of the above inequalities yields immediately
$|\operatorname{MSA}(\mathcal{K})\setminus\operatorname{MSA}(\mathcal{K}_{\sigma})|\leq
1$. If
$\operatorname{MSA}(\mathcal{K})=\operatorname{MSA}(\hat{\mathcal{K}})$, then
the proof is complete.

Suppose
$\operatorname{MSA}(\hat{\mathcal{K}})=\operatorname{MSA}(\mathcal{K})\cup\\{\sigma\\}$.
Further, if $\sigma\notin\operatorname{MSA}(\mathcal{K}_{\sigma})$ then
$\sigma\notin\operatorname{MSA}(\hat{\mathcal{K}})$ as
$w(\sigma)\leq\hat{w}(\sigma)$. Thus
$\sigma\in\operatorname{MSA}(\mathcal{K}_{\sigma})$ and so
$\operatorname{MSA}(\mathcal{K}_{\sigma})\setminus\operatorname{MSA}(\mathcal{K})=\operatorname{MSA}(\hat{\mathcal{K}})\setminus\operatorname{MSA}(\mathcal{K})=\\{\sigma\\}$
and so the proof is complete.

(ii): Assume that
$\operatorname{MSA}(\mathcal{K})\neq\operatorname{MSA}(\mathcal{K}_{\sigma})$.
There are two possible cases: there exists a
$\tau\in\operatorname{MSA}(\mathcal{K})\backslash\operatorname{MSA}(\mathcal{K}_{\sigma})$
or
$\tau^{\prime}\in\operatorname{MSA}(\mathcal{K}_{\sigma})\backslash\operatorname{MSA}(\mathcal{K})$.
In the first case, this implies that the boundary of $\tau$ can be written as
the linear combination using the boundary of $\sigma$. However since
$\ell_{\sigma}(\sigma)=1$, this boundary can be expressed in terms of the
boundaries of $\mathcal{K}$, contradicting
$\tau\in\operatorname{MSA}(\mathcal{K})$. In the latter case, we recall that
for $\tau^{\prime}\in\mathcal{K}\subseteq\mathcal{K}_{\sigma}$,
$\ell_{\sigma}(\tau^{\prime})=-1$ implies $\ell(\tau^{\prime})=-1$ ([40, Lemma
19]) . This implies that $\tau^{\prime}=\sigma$ which contradicts the
assumptions.

∎

###  3.3. Stablization under Chain Maps

In this section, we prove the topological lemmas regarding behaviour of
weighted complexes under chain maps. Throughout this section we will consider
the relationship of two weighted simplicial complexes $\mathcal{K}$ and
$\mathcal{K}^{\prime}$ (with the respective weight functions denoted
$w,w^{\prime}$) whose chain groups are related by a chain map, i.e.

$f:\bigoplus_{k}C_{k}(\mathcal{K})\rightarrow\bigoplus_{k}C_{k}(\mathcal{K}^{\prime})$

We observe that even if $\sigma\in\mathcal{K}\cap\mathcal{K}^{\prime}$, it
need not hold that $w(\sigma)=w^{\prime}(\sigma)$. We remind the reader that:
(1) $\partial$ is the boundary map and that boundary of a simplex $\sigma$ is
denoted by $\partial\sigma$; (2) since $\mathrm{dim}(\sigma)=k$,
$\partial\sigma\in C_{k-1}$; (3) by definition, a chain map commutes with the
boundary operator i.e., $f\circ\partial=\partial\circ f$.

######  Assumption 3.3.

We shall assume that the chain map satisfies following two properties:

  1. (1)

The restriction to any sublevel set of the weight function is a chain map
i.e.,

$f:\bigoplus_{k}C_{k}(\mathcal{K}(t))\rightarrow\bigoplus_{k}C_{k}(\mathcal{K}^{\prime}(t)),$

is a chain map for all $t\geq 0$.

  2. (2)

For any $\sigma\in\mathcal{K}(t)\cap\mathcal{K}^{\prime}(t)$ for some $t\geq
0$, $\sigma$ and $f(\sigma)$ are homologous as chains in
$C_{k}(\mathcal{K}^{\prime}(t))$.

Suppose that $\partial\sigma\in\mathcal{K}\cap\mathcal{K}^{\prime}$ for a
simplex $\sigma$. Then, we set

$\displaystyle\mathcal{K}_{\sigma}$ $\displaystyle:=\mathcal{K}\cup\sigma$
$\displaystyle\mathcal{K}^{\prime}_{\sigma}$
$\displaystyle:=\mathcal{K}^{\prime}\cup\sigma$

For each of the complexes, we denote the label on the simplices as
$\ell,\ell^{\prime},\ell_{\sigma}$, and $\ell^{\prime}_{\sigma}$ for
$\mathcal{K},\mathcal{K}^{\prime},\mathcal{K}_{\sigma}$ and
$\mathcal{K}^{\prime}_{\sigma}$ respectively.

######  Lemma 3.4.

  1. (i)

For any simplex $\tau\in\mathcal{K}\cap\mathcal{K}^{\prime}$, if
$\ell(\tau)=1$ then $\ell^{\prime}(\tau)=1$.

  2. (ii)

If $\ell^{\prime}_{\sigma}(\sigma)=-1$ then $\ell_{\sigma}(\sigma)=-1$.

###### Proof.

Note that it suffices to prove (i) as (ii) is its contrapositive applied to
$\mathcal{K}_{\sigma}$ and $\mathcal{K}^{\prime}_{\sigma}$. The proof of (i)
follows from the existence of the chain map.

(6)
${C_{k}(\mathcal{K})}$${C_{k}(\mathcal{K}^{\prime})}$${C_{k-1}(\mathcal{K})}$${C_{k-1}(\mathcal{K}^{\prime})}$$\scriptstyle{f_{k}}$$\scriptstyle{\partial}$$\scriptstyle{\partial^{\prime}}$$\scriptstyle{f_{k-1}}$

By $\ell(\tau)=1$, there exists a chain $c_{k}\in C_{k}(\tau^{-})$ such that
$\partial(\tau+c_{k})=0$. As $f$ is a chain map, by linearity,
$f(\tau+c_{k})=f(\tau)+f(c_{k})$, and hence by the commutativity of $\partial$
and $f$, we have that $\partial^{\prime}(f(\tau)+f(c_{k}))=0$. By assumption,
$\tau$ and $f(\tau)$ are homologous as chains, so
$\tau=f(\tau)+\partial^{\prime}c_{k+1}$, where $c_{k+1}$ is some chain in
$C_{k+1}(\mathcal{K}^{\prime})$. Applying the boundary operator, we obtain
$\partial^{\prime}(\tau+f(c_{k}))=\partial^{\prime}f(\tau)+\partial^{\prime}f(c_{k})+\partial^{\prime}\partial^{\prime}c_{k+1}=0$,
implying that $\ell^{\prime}(\tau)=1$. ∎

We will require one additional lemma which describes the relationship of the
four complexes.

######  Lemma 3.5.

Let $\tau\in\mathcal{K}\cap\mathcal{K}^{\prime}$ such that $\ell(\tau)=-1$ and
$\ell_{\sigma}(\tau)=1$. If $\ell^{\prime}_{\sigma}(\sigma)=-1$, there exists
a simplex $\tau^{\prime}\in\mathcal{K}^{\prime}$ such that

  * •

$\ell^{\prime}(\tau^{\prime})=-1$

  * •

$\ell^{\prime}_{\sigma}(\tau^{\prime})=1$

  * •

$w^{\prime}(\tau^{\prime})\leq w(\tau)$.

###### Proof.

The assumptions imply that $\partial\sigma$ is a non-trivial cycle prior to
the insertion of $\sigma$ in $C_{k}(\mathcal{K})$, and so represents a non-
trivial homology cycle in which must persist from at least $(a,w(\sigma))$ for
some $a\leq w(\sigma)$. Note that this may represent an ephemeral class, i.e.
$a=w(\sigma)$. We observe that $\ell^{\prime}_{\sigma}(\sigma)=-1$ implies
$\ell_{\sigma}(\sigma)=-1$ and $f(\sigma)=\sigma$. Note that this implies the
weight of $\sigma$ remains unchanged.

The assumptions further imply that $\partial\tau$ is homologous to
$\partial\sigma$ in $\mathcal{K}(\tau^{-})$. This can be seen since
$\ell(\tau)=-1$, the chain $\partial\tau$ is a non-trivial homology class in
$\mathcal{K}(\tau^{-})$. However, since $\ell_{\sigma}(\tau)=1$, $\tau$ bounds
the cycle $\partial_{k}\sigma$ in $\mathcal{K}$ and so the homology class
$[\partial\sigma]$ is non-trivial until $w(\tau)$. Now we show the existence
of $\tau^{\prime}$. Consider the following commutative diagram

(7)
${\mathrm{H}_{k}(\mathcal{K})}$${\mathrm{H}_{k}(\mathcal{K}_{\sigma})}$${\mathrm{H}_{k}(\mathcal{K}^{\prime})}$${\mathrm{H}_{k}(\mathcal{K}^{\prime}_{\sigma})}$$\scriptstyle{f}$$\scriptstyle{\varphi}$$\scriptstyle{f^{\prime}}$$\scriptstyle{\varphi^{\prime}}$

where $\varphi,\varphi^{\prime},f,f^{\prime}$ are the induced maps on homology
groups. Consider the homology class $[\partial\sigma]$, i.e. the equivalence
class of the cycle $\partial_{k}\sigma$. By assumption, as $\sigma$ is a
negative simplex in all four complexes, it follows that $\partial\sigma$ is a
representative of a non-trivial persistent homology class in an interval
$(a,w(\sigma))$ for some $a\leq w(\sigma)$ in all four complexes. We remark
that the bounds on the birth time, i.e. $a$, need not be the same in the four
spaces, but are all upper-bounded by the value in
$\mathrm{H}_{k}(\mathcal{K})$.

By the properties of persistence module homomorphisms, the death time of an
image (under $f$) of a persistence class is non-increasing. Since
$[\partial\sigma]$ is trivial in $\mathrm{H}_{k}(\mathcal{K}^{\prime})$ at
$w(\tau)$, it follows that there must exist a bounding chain for
$\psi([\partial\sigma])$ in $\mathrm{H}_{k}(\mathcal{K}^{\prime})$ at or
before $w(\tau)$. Note that this upper bound, is with respect to the
filtration value in $\mathcal{K}$. Set $\tau^{\prime}$ to be the last simplex
in this bounding chain (where the ordering is induced by $w^{\prime}$). By
construction, it is negative in $\mathcal{K}$ and by the insertion of $\sigma$
in $\mathcal{K}^{\prime}$, it creates a new cycle – as it bounds
$\partial\sigma$, hence adding $\sigma$ creates a cycle, completing the proof.
∎

###  3.4. Existence of chain maps between Delaunay complexes

In order to use the results of the previous section, we need existence of
chain maps between Delaunay complexes built on two finite point sets
${\mathcal{X}}\subseteq{\mathcal{Y}}$ such that they satisfy the assumptions
in Assumption 3.3. We assume ${\mathcal{X}},{\mathcal{Y}}$ are _generic_ in
the sense that there are no co-linear or cocircular points. We first recall a
few standard definitions and facts which are used in this section.

######  Definition 3.6.

Given an open cover $\mathcal{U}:=\\{\mathcal{U}_{i}\\}_{i\in\mathcal{I}}$ of
a closed subset $U\subset\mathbb{R}^{d}$, the nerve $\mathcal{N}(\mathcal{U})$
is the set of finite subsets of $\mathcal{I}$ defined as follows. A finite set
$I\subseteq\mathcal{I}$ belongs to $\mathcal{N}(\mathcal{U})$ if and only if
the intersection of the $\mathcal{U}_{i}$ whose indices are in $I$, is non-
empty, i.e.

$\mathcal{U}_{I}=\bigcap\limits_{i\in I}\mathcal{U}_{i}\neq\emptyset$

If $I$ belongs to $\mathcal{N}(\mathcal{U})$, then so do all of its subsets
making $\mathcal{N}(\mathcal{U})$ an abstract simplicial complex. If a cover
satisfies the condition that all finite non-empty intersections are
contractible, then it is said to be a _good cover_.

If an open cover is good, the corresponding nerve captures the same
topological information combinatorially. This is formalized in the Nerve
Theorem; see [5, Theorem 10.7] for example.

######  Theorem 3.7.

If $\mathcal{U}$ is a good open cover of a closed subset
$U\subset\mathbb{R}^{d}$, then $U$ is homotopy equivalent to the nerve
$\mathcal{N}(U)$.

We show that the sequence of simplex deletions and additions which occur when
adding a point to ${\mathcal{X}}$ can be realized as a sequence of topological
spaces with the Voronoi cells inducing a good cover of each space. This allows
us to pass back and forth from the combinatorial description of the Delaunay
complex to the geometric realization of the union of balls around point in
${\mathcal{X}}$ via the Nerve Theorem. This allows us to relate the Delaunay
complexes on point sets ${\mathcal{X}}\subset{\mathcal{Y}}$, by defining a
chain map which meets the requirements of Assumption 3.3. We remark more on
the necessity for considering such a sequence of complexes at the end of this
subsection.

First, we use the fact the Delaunay complex is the nerve of the cover induced
by the Voronoi diagram of a generic point set $\mathcal{X}$. Define the
$\varepsilon$-offset of the Voronoi cell of a point $x\in\mathcal{X}$ as

$\mathrm{Vor}^{\varepsilon}_{\mathcal{X}}(x)=\\{p\in\mathbb{R}^{d}:\exists
y\in\mathrm{Vor}_{\mathcal{X}}(x)\,\mbox{such that}\,|p-y|<\varepsilon\\}$

We now give a straightforward result whose proof will be sketched for
completeness.

######  Lemma 3.8.

For $\varepsilon>0$ small enough, the cover induced by

$\mathrm{Vor}^{\varepsilon}_{\mathcal{X}}(x)\cap B_{r}(x)\qquad\forall
x\in{\mathcal{X}}$

form a good cover of the $\bigcup_{x\in{\mathcal{X}}}B_{r}(x)$ for all $r$. We
call this cover the Voronoi-induced cover of ${\mathcal{X}}$.

###### Proof.

As ${\mathcal{X}}$ is finite, we can choose $\varepsilon>0$ small enough such
that the intersections of the $\varepsilon$-offsets of the Voronoi cells are
in one-to-one correspondence with the adjacencies of the Voronoi cells. The
Voronoi cells (and their $\varepsilon$-offsets) are convex, hence they form a
good cover of the full space. Additionally, the balls centered on the points
are also convex, hence all intersections between balls and cells are either
empty or convex, and hence contractible, implying the result. ∎

Note that the choice of $\varepsilon$ depends on the point set and can be
arbitrarily small. We simply require that for any finite generic point set
(without multiplicity), an $\varepsilon>0$ exists. Assume that
${\mathcal{X}}\subset{\mathcal{Y}}$ are generic finite point sets as above.
First, we define

${\mathcal{X}}^{\prime}={\mathcal{X}}\cup\\{\textbf{0}\\},\qquad\qquad{\mathcal{Y}}^{\prime}={\mathcal{Y}}\cup\\{\textbf{0}\\},$

and let $\mathcal{K}=\mathcal{D}({\mathcal{X}})$,
$\mathcal{L}=\mathcal{D}({\mathcal{Y}})$ the Delaunay complex of
${\mathcal{X}},{\mathcal{Y}}$ respectively. Similarly let
$\mathcal{K}^{\prime}$ and $\mathcal{L}^{\prime}$ be the Delaunay complexes on
${\mathcal{X}}^{\prime}$ and ${\mathcal{Y}}^{\prime}$ respectively. Observe
that $\mathcal{K},\mathcal{K}^{\prime},\mathcal{L},\mathcal{L}^{\prime}$ are
complexes that correspond to Voronoi-induced covers on
${\mathcal{X}},{\mathcal{X}}^{\prime},{\mathcal{Y}},{\mathcal{Y}}^{\prime}$
respectively.

We assume that

(8)
$\mathcal{K}\triangle\mathcal{K}^{\prime}=\mathcal{L}\triangle\mathcal{L}^{\prime}=\\{\sigma_{0},\sigma_{1},\ldots,\sigma_{k}\\}.$

We can choose $\varepsilon$ small enough, but dependent on the point sets
${\mathcal{X}},{\mathcal{Y}}$, so that the nerve of this cover is
combinatorially equivalent to the Delaunay complex. This follows from the
finiteness of the point sets.

There exists an ordering of the the simplices in (8) such that

$\mathcal{K}^{i}=\begin{cases}\mathcal{K}^{i-1}-\sigma_{i}&0<i\leq l_{1}\\\
\mathcal{K}^{i-1}\cup\sigma_{i}&l_{1}<i\leq
l\end{cases}\quad;\quad\mathcal{L}^{i}=\begin{cases}\mathcal{L}^{i-1}-\sigma_{i}&0<i\leq
l_{1}\\\ \mathcal{L}^{i-1}\cup\sigma_{i}&l_{1}<i\leq l\end{cases}$
$\displaystyle\mathcal{K}$
$\displaystyle=\mathcal{K}^{0}\supseteq\mathcal{K}^{1}\supseteq\ldots\supseteq\mathcal{K}^{l_{1}}=\mathcal{K}\cap\mathcal{K}^{\prime}\subseteq\mathcal{K}^{l_{1}+1}\subseteq\ldots\subseteq\mathcal{K}^{l}=\mathcal{K}^{\prime},$
(9) $\displaystyle\mathcal{L}$
$\displaystyle=\mathcal{L}^{0}\supseteq\mathcal{L}^{1}\supseteq\ldots\supseteq\mathcal{L}^{l_{1}}=\mathcal{L}\cap\mathcal{L}^{\prime}\subseteq\mathcal{L}^{l_{1}+1}\subseteq\ldots\subseteq\mathcal{L}^{l}=\mathcal{L}^{\prime}.$

In proving the main result of this section, we recount the following result

######  Theorem 3.9.

([4, Theorem 5.10]) Let ${\mathcal{X}}$ be a finite set of points in general
position in $\mathbb{R}^{d}$, then there is a simplicial collapse from the
Delaunay-Čech complex to the Delauany complex for any weight $w\in\mathbb{R}$.

######  Lemma 3.10.

For each $i$, there exists a chain map

$f_{i}:\bigoplus\limits_{k}C_{k}(\mathcal{K}^{i})\rightarrow\bigoplus\limits_{k}C_{k}(\mathcal{L}^{i}),$

which satisfies the conditions listed in Assumption 3.3.

###### Proof.

Define

$\displaystyle X_{r}$
$\displaystyle=\bigcup\limits_{p\in{\mathcal{X}}}B_{r}(p)\cap\mathrm{Vor}_{\mathcal{X}}(p)$
$\displaystyle Y_{r}$
$\displaystyle=\bigcup\limits_{q\in{\mathcal{Y}}}B_{r}(p)\cap\mathrm{Vor}_{\mathcal{Y}}(q)$

By standard results for the Delaunay complex, there exist chain maps for
$i=0,L$ i.e.,

(10)
$C_{*}(\mathcal{K}_{r})\xhookrightarrow{\alpha}C_{*}(X_{r})\xhookrightarrow{\beta}C_{*}(Y_{r})\xrightarrow{\gamma}C_{*}(\mathcal{L}_{r}).$

Note that from this point on, we omit the radius/weight parameter as $\alpha$
and $\gamma$ are homotopy equivalences for any value of the radius and they
commute with inclusion, e.g. [4]. For $i\neq 0,L^{\prime}$, the homotopy
equivalences are no longer obvious as the underlying complex is not simply the
nerve of a cover of the space, as we are deleting and adding simplices. To
prove the existence of chain maps, we introduce a sequence of topological
spaces where the nerve of the Voronoi-induced cover is $\mathcal{K}^{i}$ and
forms a good cover, implying the existence of the homotopy equivalences and
the chain maps. We define the topological spaces corresponding to $X^{i}(r)$
and $Y^{i}(r)$.

For each simplex $\tau$ in a Delaunay complex, there is a corresponding face
in the Voronoi diagram. Denote this face by $\nu^{\mathcal{X}}(\tau)$ and its
$\varepsilon$-offset by $\nu^{\mathcal{X}}_{\varepsilon}(\tau)$.

$\displaystyle X^{i}(r)$
$\displaystyle=\bigcup\limits_{p\in{\mathcal{X}}}B_{r}(p)\cap\mathrm{Vor}_{\mathcal{P}}(p)-\bigcup\limits_{\tau\in\sigma_{i}}\nu^{\mathcal{X}}_{\varepsilon}(\tau)$
$\displaystyle Y^{i}(r)$
$\displaystyle=\bigcup\limits_{q\in{\mathcal{Y}}}B_{r}(q)\cap\mathrm{Vor}_{\mathcal{Y}}(q)-\bigcup\limits_{\tau\in\sigma_{i}}\nu^{\mathcal{Y}}_{\varepsilon}(\tau)$

where $\varepsilon$ is arbitrarily small and depends on ${\mathcal{X}}$ and
${\mathcal{Y}}$. As $\nu^{\mathcal{Y}}(\tau)\subseteq\nu^{\mathcal{X}}(\tau)$,
it follows that $X^{i}(r)\subseteq Y^{i}(r)$.

By construction the nerves of these covers are $\mathcal{K}^{i}$ and
$\mathcal{L}^{i}$ respectively, as the intersections corresponding to missing
simplices (and their cofaces) are empty, since they have been removed from the
space. It remains a good cover, as all the cover elements and non-empty
intersections are star-shaped and so contractible. We can now define the chain
map

$\psi_{i}=\gamma_{i}\circ\beta_{i}\circ\alpha_{i}$

Applying the standard good cover homotopy equivalence argument to these
intermediate spaces we obtain a chain map. This proves the existence of a
chain map satisfying Assumption 3.3(1).

To show that the map satisfies Assumption 3.3 (2), we show that the following
diagram for $s<t$,

${\mathcal{K}^{i}_{s}}$${\mathcal{L}^{i}_{s}}$${\mathcal{K}^{i}_{t}}$${\mathcal{L}^{i}_{t}}$$\scriptstyle{f_{s}}$$\scriptstyle{f_{t}}$

commutes up to chain homotopy, which implies the that $f(\sigma)$ and $\sigma$
are homologous. If $\sigma\in\mathcal{K}^{i}_{s}\cap\mathcal{L}^{i}_{s}$, then
$f_{s}(\sigma)=f_{t}(\sigma)=\sigma$, and the diagram commutes. However, we
must also show that the diagram commutes when
$\sigma\in\mathcal{L}^{i}_{t}\backslash\mathcal{L}^{i}_{s}$. In this case, we
insert an intermediate step in the above diagram using the Delaunay-Čech
complex, which we denote by $\mathcal{D}\mathcal{C}$. We observe that it can
be constructed as a cover of the $i$-th space, so we denote the corresponding
complex by $\mathcal{D}\mathcal{C}^{i}$. This follows from the fact that
$\mathcal{D}\mathcal{C}$ is equal to the Delaunay complex, with a different
weight function (see Definition 1.1). Including the complex in the diagram, we
obtain

${\mathcal{K}^{i}_{s}}$${\mathcal{D}\mathcal{C}^{i}_{s}}$${\mathcal{L}^{i}_{s}}$${\mathcal{K}^{i}_{t}}$${\mathcal{D}\mathcal{C}^{i}_{t}}$${\mathcal{L}^{i}_{t}}$

As the weight function for the Delaunay-Čech cannot decrease all the maps in
the left-hand square are inclusions, so the square commutes up to homotopy. By
Theorem 3.9, the horizontal maps
$\mathcal{D}\mathcal{C}^{i}\rightarrow\mathcal{L}^{i}$ are simplicial
collapses which commute with inclusions, hence the original diagram commutes
up to homotopy.

∎

######  Remark 3.11.

At first glance, the intermediate step of the spaces may seem unnecessary as
one could pass to the Čech complex rather than the topological spaces.
However, in this case inserting and removing simplices is complicated by the
fact that we need to insert and remove the corresponding cofaces in the Čech
complex, which no longer corresponds to the cover by balls of a given radius
complicating the analysis. By constructing the sequence of spaces, we are able
to define the appropriate maps for all intermediate steps which allows us to
use the results of the previous section.

###  3.5. Stabilization of Poisson Delaunay Complexes

To use the approach of Section 3.3 for showing stabilization of death times in
Poisson-Delaunay complex, we need to establish (8) which is essentially the
stabilization of simplices in the Poisson-Delaunay complex. Recall the set of
boxes $\mathfrak{A}$ defined before Theorem 2.3.

######  Proposition 3.12.

Let $\mathcal{P}$ be a stationary Poisson point process of unit intensity and
$A_{n}\in\mathfrak{A}$ be a sequence of sets such that
$A_{n}\to\mathbb{R}^{d}$. Let $\mathcal{D}_{n}=\mathcal{D}(\mathcal{P}\cap
A_{n})$ and $\mathring{\mathcal{D}}_{n}=\mathcal{D}((\mathcal{P}\cap
A_{n})\cup\\{\textbf{0}\\})$ be the sequence of Delaunay complexes on
$\mathcal{P}\cap A_{n}$ and $(\mathcal{P}\cap A_{n})\cup\\{\textbf{0}\\}$,
$n\geq 1$ respectively. There exist a.s. finite random variables $L,M$ such
that for all $n>M$,

$D_{n}\bigtriangleup\mathring{\mathcal{D}}_{n}=\\{\sigma_{1},\ldots,\sigma_{L}\\}$

and furthermore $w(\sigma_{i})\leq M$ for all $i\leq L$.

The proof is a modification of arguments from [34, Lemma 5.1] with more
quantitative estimates provided in Proposition 3.13. Similar arguments are
used in the case of $d=2$ in [31, Section 4] and [35, Section 8].

###### Proof.

Let $\Lambda_{i},1\leq i\leq m$ be infinite open cones with apex at 0 and
angular radius $\pi/6$ such that $\mathbb{R}^{d}=\cup_{i}\Lambda_{i}$. Let
$R_{i}=d(\textbf{0},\mathcal{P}\cap\Lambda_{i})$ i.e., distance from origin to
the closest point in the cone $\Lambda_{i}$. Define $R=\max R_{i}$. Since
$\Lambda_{i}$’s have infinite volume,
$\mathcal{P}\cap\Lambda_{i}\neq\emptyset$ a.s. and so $R_{i}<\infty$ a.s. for
all $1\leq i\leq m$. Thus $R<\infty$ a.s. and also adding 0 does not affect
the Voronoi cells outside $B_{R}(\textbf{0})$ i.e., if
$\mathrm{Vor}_{\mathcal{P}_{n}\cup\\{\textbf{0}\\}}(X)\cap\mathrm{Vor}_{\mathcal{P}_{n}\cup\\{\textbf{0}\\}}(\textbf{0})\neq\emptyset$
or $\textbf{0}\in\mathrm{Vor}_{\mathcal{P}_{n}}(X)$ then $|X|\leq R$. This
also gives that
$\mathrm{Vor}_{\mathcal{P}_{n}\cup\\{\textbf{0}\\}}(X)=\mathrm{Vor}_{\mathcal{P}_{n}}(X)$
if $|X|\geq 2R$. So, we have that if $\sigma\in\mathcal{D}(\mathcal{P}\cap
W_{j})\bigtriangleup\mathring{\mathcal{D}}(\mathcal{P}\cap W_{j})$ then
$\sigma\cap B_{2R}(\textbf{0})\neq\emptyset$. This implies that Delaunay faces
outside $B_{3R}(\textbf{0})$ are unchanged by adding 0.

We now consider the case $A_{n}=W_{n},n\geq 1$. Set $M^{\prime}:=3R$. Thus in
this case for all $j\geq M^{\prime}$

$\mathcal{D}(\mathcal{P}\cap
W_{j})\bigtriangleup\mathring{\mathcal{D}}(\mathcal{P}\cap
W_{j})\subset\\{\sigma\in D_{j}:\sigma\subset
B_{3R}(\textbf{0})\\}\cup\\{\sigma^{\prime}\in\mathring{\mathcal{D}}_{j}:\sigma^{\prime}\subset
B_{3R}(\textbf{0})\\}.$

If $\sigma\subset B_{3R}(\textbf{0})$, then $w(\sigma)\leq 3R$ and similarly
for $\sigma^{\prime}$. So, we get the first claim in the Proposition when
$A_{n}=W_{n}$, $n\geq 1$ and with $M=M^{\prime}$. As for $L$ in this case,
observe that

$|\mathcal{D}(\mathcal{P}\cap W_{M})|\leq|\mathcal{P}\cap
W_{M}|^{k+1}\,\,;|\mathring{\mathcal{D}}(\mathcal{P}\cap
W_{M})|\leq(|\mathcal{P}\cap W_{M}|+1)^{k+1},$

and these bounds together with a.s. finiteness of $M$ give the a.s. finiteness
of $L$.

Set $M^{\prime}=3R$. Suppose that $A_{n}\to\mathbb{R}^{d}$ is an arbitrary
sequence of boxes in $\mathfrak{A}$. Then there exists an a.s. finite random
variable $M$ such that $\mathcal{P}\cap W_{M^{\prime}}\subset\mathcal{P}\cap
A_{M}$ as $\mathcal{P}\cap W_{M^{\prime}}$ is a.s. finite. Thus by the above
argument, we obtain that for $j>M$

$\mathcal{D}(\mathcal{P}\cap
A_{j})\bigtriangleup\mathring{\mathcal{D}}(\mathcal{P}\cap
A_{j})\subset\\{\sigma\in D_{j}:\sigma\subset
B_{3R}(\textbf{0})\\}\cup\\{\sigma^{\prime}\in\mathring{\mathcal{D}}_{j}:\sigma^{\prime}\subset
B_{3R}(\textbf{0})\\}.$

The a.s. finiteness of $L$ in this case follows as in the special case of
$A_{n}=W_{n}$. ∎

As indicated after Proposition 3.12, we provide some tail estimates for the
random variables therein and for arbitrary boxes $A\in\mathfrak{A}$ to verify
the moment conditions for our CLT.

######  Proposition 3.13.

([34, Section 5.1]) Let $\mathcal{P}$ be a stationary Poisson point process of
unit intensity and let $A\in\mathfrak{A}$ such that $\textbf{0}\in A$. Let
$\mathcal{D}_{A}=\mathcal{D}(\mathcal{P}\cap A)$ and
$\mathring{\mathcal{D}}_{A}=\mathcal{D}((\mathcal{P}\cap
A)\cup\\{\textbf{0}\\})$ be the Delaunay complexes on $\mathcal{P}\cap A$ and
$(\mathcal{P}\cap A)\cup\\{\textbf{0}\\}$ respectively. There exists a.s.
finite random variables $L_{A},M_{A}$ such that

$D_{A}\bigtriangleup\mathring{\mathcal{D}}_{A}=\\{\sigma_{1},\ldots,\sigma_{L_{A}}\\}$

and further $w(\sigma_{i})\leq M_{A}$ for all $i\leq L_{A}$. Also, we have
that $L_{A},M_{A}$ have exponentially decaying tails uniformly in $A$ i.e.,
there exist constants $C,c>0$ (depending on $d$) such that for all $t\geq 1$,

$\sup_{A\in\mathfrak{A},\textbf{0}\in A}\mathbb{P}(M_{A}>t)\leq
Ce^{-ct^{d}}\,\,;\,\,\sup_{A\in\mathfrak{A},\textbf{0}\in
A}\mathbb{P}(L_{A}>t)\leq Ce^{-ct^{1/(d+1)}}.$

We sketch the proof from [34, Lemma 5.1] for sake of completeness.

###### Proof.

Let $\Lambda_{i},1\leq i\leq m$ be infinite open cones with apex at 0 and
angular radius $\pi/12$ such that
$\mathbb{R}^{d}=\cup_{i=1}^{m}\Lambda_{i}\cup\\{\textbf{0}\\}$. Let
$\Lambda_{i}^{+}$ be the open cone concentric to $\Lambda_{i}$ with apex at 0
and angular radius $\pi/6$. Set $d_{i}(A):=\operatorname{diam}(\Lambda_{i}\cap
A)$. Define

$\displaystyle R_{i}(A)$
$\displaystyle:=\min\\{\min\\{|X|:X\in\mathcal{P}\cap\Lambda^{+}_{i}\cap
B_{d_{i}(A)}(\textbf{0})\\},d_{i}(A)\\},1\leq i\leq m,$ $\displaystyle R(A)$
$\displaystyle:=\max_{1\leq i\leq m}R_{i}(A).$

By geometric considerations, we see that $\mathrm{Vor}_{(\mathcal{P}\cap
A)\cup\\{\textbf{0}\\}}(\textbf{0})\cap\Lambda_{i}\subset
B_{R_{i}(A)}(\textbf{0})\cap\Lambda_{i}$ and so
$\mathrm{Vor}_{(\mathcal{P}\cap A)\cup\\{\textbf{0}\\}}(\textbf{0})\subset
B_{R(A)}(\textbf{0})$. Thus, arguing as in the proof of Proposition 3.12, we
have that

$D_{A}\bigtriangleup\mathring{\mathcal{D}}_{A}\subset B_{3R_{A}}(\textbf{0}).$

Now, we shall derive tail bounds for $R_{A}$ and using that, derive suitable
bounds for $M_{A},L_{A}$. Suppose that for some $1\leq i\leq m$, $R_{i}(A)\geq
t$ for some $t\geq 1$. Then there is a $y\in\Lambda_{i}\cap A$ such that
$|y|=t$ and also $B_{at}(y/2)\subset\Lambda^{+}_{i}$ for some $a>0$. Here $a$
depends on $d$ but not on $A$. Since $R_{i}(A)\geq t$, it holds that
$\mathcal{P}\cap A\cap B_{at}(y/2)=\emptyset$. As $A=W_{n}+x$ for some $n,x$
and $\textbf{0}\in A$, we have that $y/2\in A$ and $|A\cap B_{at}(y/2)|\geq
c^{\prime}a^{d}t^{d}$ for some constant $c^{\prime}>0$ dependent on $d$ but
not on $A$. Thus, we derive that for $t\geq 1$,

$\mathbb{P}(R_{i}(A)\geq t)\leq\mathbb{P}(\mathcal{P}\cap A\cap
B_{at}(y/2)=\emptyset)\leq e^{-c^{\prime}a^{d}t^{d}}.$

This yields that if $\sigma\in D_{A}\bigtriangleup\mathring{\mathcal{D}}_{A}$
then $w(\sigma)\leq M_{A}:=3R_{A}$ and the required bound as well.

To bound $L_{A}$ observe that $L_{A}\leq 2(d+1)(|\mathcal{P}\cap
B_{M_{A}}(\textbf{0})|+1)^{d+1}$ as $|\mathcal{P}\cap
B_{M_{A}}(\textbf{0})|+1$ is the total number of vertices in $(\mathcal{P}\cap
A\cap B_{M_{A}}(\textbf{0}))\cup\\{\textbf{0}\\}$ and $d$ is the maximum
dimension of the Delaunay complex. For $t\geq 1$, set $s=s(t)$ such that
$\theta_{d}s^{d}=(\frac{t}{2(d+1)})^{1/(d+1)}-1)$ where $\theta_{d}$ is the
volume of the unit ball. Using the concentration inequality for Poisson random
variables from [33, Lemma 1.4], we can derive that

$\displaystyle\mathbb{P}(L_{A}\geq t)$
$\displaystyle\leq\mathbb{P}\Big{(}|\mathcal{P}\cap
B_{s/2}(\textbf{0})|\geq\theta_{d}s^{d}\Big{)}+\mathbb{P}(M_{A}\geq s/2)$
$\displaystyle\leq\mathbb{P}\Big{(}\Big{|}|\mathcal{P}\cap
B_{s/2}(\textbf{0})|-\theta_{d}(s/2)^{d}|\geq\theta_{d}(1-1/2^{d})s^{d}\Big{)}+Ce^{-cs^{d}/2^{d}}$
$\displaystyle\leq\tilde{C}e^{-\tilde{c}s^{d}}+Ce^{-cs^{d}/2^{d}}.$

Now substituting the choice of $s$ into the above bound completes the proof of
the proposition. ∎

###  3.6. Proofs of main results - Proposition 1.2 and Theorem 1.3.

We now prove weak stabilization of the sum of death times in the Poisson-
Delaunay complex and thereby prove also weak stabilization of the sum of birth
times and lifetimes as well. We use this to prove the central limit theorem
for all three quantities. The starting point is a stablization result for the
sum of death times for Delaunay complexes on locally finite point sets but
along increasing windows $W_{n}$.

######  Proposition 3.14.

Let ${\mathcal{X}}$ be a locally-finite point set with points in general
position and as before, $W_{n}=[-\frac{n^{1/d}}{2},\frac{n^{1/d}}{2}]^{d}$,
$n\geq 1$. Set ${\mathcal{X}}_{n}={\mathcal{X}}\cap W_{n}$ and let
$\mathcal{D}_{n}=\mathcal{D}({\mathcal{X}}_{n}),\mathring{\mathcal{D}}_{n}=\mathcal{D}({\mathcal{X}}_{n}\cup\\{0\\})$
and $\mathcal{D}=\mathcal{D}({\mathcal{X}})$ be the Delaunay complexes on
${\mathcal{X}}_{n},{\mathcal{X}}_{n}\cup\\{\textbf{0}\\}$ and ${\mathcal{X}}$
respectively. Assume that $\mathcal{D}_{n}$ stabilizes i.e., there exists a
$n_{0}$ such that for all $n\geq n_{0}$,

(11)
$\mathcal{D}_{n}\triangle\mathring{\mathcal{D}}_{n}=\\{\sigma_{1},\ldots,\sigma_{l}\\},$

where $\sigma_{k}\subset W_{n_{o}}$ for all $1\leq j\leq l$. Then there exists
a constant $\mathbf{M}^{\phi}_{k}(\mathcal{D})\in[0,\infty)$ such that
$\mathbf{M}^{\phi}_{k}(\mathring{\mathcal{D}}_{n})-\mathbf{M}^{\phi}_{k}(\mathcal{D}_{n})\stackrel{{\scriptstyle
n\to\infty}}{{\to}}\mathbf{M}^{\phi}_{k}(\mathcal{D}).$

###### Proof.

We shall fix $k\in\\{1,\ldots,d\\}$ and drop the subscript $k$ everywhere. Let
$n\geq n_{0}$. Firstly, let us set that
$\\{\sigma_{1},\ldots,\sigma_{l_{1}}\\}=\mathring{\mathcal{D}}_{n}\setminus(\mathring{\mathcal{D}}_{n}\cap\mathcal{D}_{n})$
and
$\\{\sigma_{l_{1}+1},\ldots,\sigma_{l}\\}=\mathcal{D}_{n}\setminus(\mathring{\mathcal{D}}_{n}\cap\mathcal{D}_{n})$.
Thus, as in (9), we have the following decomposition

$\mathcal{D}_{n}=\mathcal{K}^{0}_{n}\supseteq\mathcal{K}^{1}_{n}\supseteq\ldots\supseteq\mathcal{K}^{l_{1}}_{n}=\mathcal{D}_{n}\cap\mathring{\mathcal{D}}_{n}\subseteq\mathcal{K}^{l_{1}+1}_{n}\subseteq\ldots\subseteq\mathcal{K}^{l}_{n}=\mathring{\mathcal{D}}_{n},$

where $\mathcal{K}^{j}_{n}\triangle\mathcal{K}^{j-1}_{n}=\\{\sigma_{j}\\}$.
Thus, we obtain that

$\mathbf{M}^{\phi}(\mathcal{D}_{n})-\mathbf{M}^{\phi}(\mathring{\mathcal{D}}_{n})=\sum_{j=1}^{l}\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})$

and so convergence of
$\mathbf{M}^{\phi}(\mathcal{D}_{n})-\mathbf{M}^{\phi}(\mathring{\mathcal{D}}_{n}))$
follows if we show that for all $1\leq j\leq l$ that

(12)
$\lim_{n\to\infty}\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})=\mathbf{M}^{\phi}(\mathcal{K}^{j}).$

The rest of the proof will be devoted to showing (12). Without loss of
generality, we assume
$\mathcal{K}^{j}_{n}=\mathcal{K}^{j-1}_{n}\cup\\{\sigma_{j}\\}$. If
$\sigma_{j}$ is not a $k$-face,
$\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})=0$
for all $n$ and so we assume that $\sigma_{j}$ is a $k$-face. Denote the label
of a simplex in $\mathcal{K}^{j}_{n}$ by $\ell^{j}_{n}$ i.e.,
$\ell^{j}_{n}(\sigma):=\ell_{\mathcal{K}^{j}_{n}}(\sigma)$ for
$\sigma\in\mathcal{K}^{j}_{n}$. Since
${\mathcal{X}}_{n}\subset{\mathcal{X}}_{m}$ for $m\geq n$, Lemma 3.10 gives us
a chain map from $\mathcal{K}^{j}_{n}$ to $\mathcal{K}^{j}_{m}$ satisfying
assumptions in Assumption 3.3 for all $m\geq n$. Thus, we shall use the
results on stabilization under chain maps in Section 3.3. We shall now prove
(12) by breaking into 3 cases.

  * Case (i):

Suppose that $\ell^{j}_{m}(\sigma_{j})=1$ for some $n\geq n_{0}$. Thus, by
Lemma 3.4(i) $\ell^{j}_{m}(\sigma_{j})=1$ for all $m\geq n$ and so we have by
Lemma 3.2(2) that
$\operatorname{MSA}(\mathcal{K}^{j}_{m})=\operatorname{MSA}(\mathcal{K}^{j-1}_{m})$
for all $m\geq n$. Consequently
$\mathbf{M}^{\phi}(\mathcal{K}^{j}_{m})=\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{m})$
for all $m\geq n$. Thus (12) holds with limit being $0$.

  * Case (ii):

Suppose that $\ell^{j}_{n}(\sigma_{j})=-1$ for all $n\geq n_{0}$. Thus
$\operatorname{MSA}(\mathcal{K}^{j}_{n})\setminus\operatorname{MSA}(\mathcal{K}^{j-1}_{n})=\\{\sigma_{j}\\}$
(see Theorem 2.2 and Lemma 3.2(1)). We subdivide this into two further cases.

    * (a):

Suppose
$\operatorname{MSA}(\mathcal{K}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{K}^{j}_{n})=\emptyset$
for all $n\geq n_{0}$ i.e., no negative faces in $\mathcal{K}^{j-1}_{n}$ turns
positive upon adding $\sigma_{j}$. Then we have that
$\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})=\phi(w(\sigma_{j}))$
and so (12) holds trivially with the limit being $\phi(w(\sigma_{j}))$.

    * (b):

Suppose that
$\operatorname{MSA}(\mathcal{K}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{K}^{j}_{n})\neq\emptyset$
for some $n\geq i_{0}$. Let us set
$\\{\tau^{j}_{n}\\}=\operatorname{MSA}(\mathcal{K}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{K}^{j}_{n})$
i.e., $\ell_{n}^{j}(\tau^{j}_{n})=1$ and $\ell_{n}^{j-1}(\tau^{j}_{n})=-1$.

From Lemma 3.5, we have that for all $m\geq n$, there exists
$\tau^{j}_{m}\in\mathcal{K}^{j-1}_{m}$ such that
$\ell_{m}^{j}(\tau^{j}_{m})=1$ and $\ell_{m}^{j-1}(\tau^{j}_{m})=-1$.
Furthermore, $w(\tau^{j}_{m})$ is decreasing in $m$. Thus $w(\tau^{j}_{n})$
converges as $n\to\infty$ and consequently

$\lim_{n\to\infty}\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})=\phi(w(\sigma_{j}))-\lim_{n\to\infty}\phi(w(\tau^{j}_{n}))=:\mathbf{M}^{\phi}(\mathcal{K}^{j}).$

Hence (12) holds with the limit being $\mathbf{M}^{\phi}(\mathcal{K}^{j})$ as
defined above.

∎

###### Proof of Proposition 1.2..

We shall again fix $k\in\\{1,\ldots,d\\}$ and drop the subscript $k$
everywhere. Suppose $\mathbf{F}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$
and $\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$ satisfy weak
stabilization (i.e., (4) holds) then so does
$\mathbf{B}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$. This is because of
linearity of weak stabilization and that
$\mathbf{B}^{\phi}(\mathcal{D}(\mathcal{P}\cap
A_{n}))=\mathbf{F}^{\phi}(\mathcal{D}(\mathcal{P}\cap
A_{n}))-\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$. Thus, to
conclude the proof, we show weak stabilization of
$\mathbf{F}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$ and
$\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$. Weak stabilization of
$\mathbf{F}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$ follows from
Proposition 3.12 as $D_{\textbf{0}}(F^{\phi}(\mathcal{D}_{n}))$ remains
unchanged for $n>M$ and so the rest of the proof will be devoted to showing
weak stabilization of $\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$.

Assume that we have an arbitrary sequence of sets $A_{n}$ as in the statement
of the proposition i.e., $A_{n}\to\mathbb{R}^{d},A_{n}\in\mathfrak{A}$. Hence,
we have that for all $n\geq 1$, there exists an a.s. finite random variable
$M_{n}$ and also a finite $m_{n}\in\mathbb{N}$ such that the following
inclusions hold.

(13) $A_{n}\subset W_{m_{n}}\,\,\mbox{and}\,\,\mathcal{P}\cap
W_{n}\subset\mathcal{P}\cap A_{m},\,\forall m\geq M_{n}.$

We can assume without loss of generality that $m_{n}\geq n$ and $M_{n}\geq n$
a.s.

By Proposition 3.12, there exists a.s. finite random variables $N_{0},L$ such
that for all $n\geq N_{0}$, we have that a.s.,

(14) $\mathcal{D}(\mathcal{P}\cap
W_{n})\triangle\mathring{\mathcal{D}}(\mathcal{P}\cap
W_{n})=\mathcal{D}(\mathcal{P}\cap
A_{n})\triangle\mathring{\mathcal{D}}(\mathcal{P}\cap
A_{n})=\\{\sigma_{1},\ldots,\sigma_{L}\\}\subset W_{N_{0}}.$

Furthermore, as in (9), we have the following decompositions

$\mathcal{D}(\mathcal{P}\cap
W_{n})=\mathcal{K}^{0}_{n}\supseteq\mathcal{K}^{1}_{n}\supseteq\ldots\supseteq\mathcal{K}^{L_{1}}_{n}=\mathcal{D}_{n}\cap\mathring{\mathcal{D}}_{n}\subseteq\mathcal{K}^{L_{1}+1}_{n}\subseteq\ldots\subseteq\mathcal{K}^{l}_{n}=\mathring{\mathcal{D}}(\mathcal{P}\cap
W_{n}),$

and

$\mathcal{D}(\mathcal{P}\cap
A_{n})=\mathcal{L}^{0}_{n}\supseteq\mathcal{L}^{1}_{n}\supseteq\ldots\supseteq\mathcal{L}^{L_{1}}_{n}=\mathcal{D}_{n}\cap\mathring{\mathcal{D}}_{n}\subseteq\mathcal{L}^{L_{1}+1}_{n}\subseteq\ldots\subseteq\mathcal{L}^{l}_{n}=\mathring{\mathcal{D}}(\mathcal{P}\cap
A_{n}),$

where
$\mathcal{K}^{j}_{n}\triangle\mathcal{K}^{j-1}_{n}=\mathcal{L}^{j}_{n}\triangle\mathcal{L}^{j-1}_{n}=\\{\sigma_{j}\\}$.
So we obtain that

$D_{\textbf{0}}(\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap
A_{n}))=\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap
A_{n}))-\mathbf{M}^{\phi}(\mathring{\mathcal{D}}(\mathcal{P}\cap
A_{n}))=\sum_{j=1}^{L}\mathbf{M}^{\phi}(\mathcal{L}^{j-1}_{n})-\mathbf{M}^{\phi}(\mathcal{L}^{j}_{n})$

From Propositions 3.14 and 3.12, we have that

(15)
$\lim_{n\to\infty}\mathbf{M}^{\phi}(\mathcal{K}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{n})=\mathbf{M}^{\phi}(\mathcal{K}^{j}),$

where the limit $\mathbf{M}^{\phi}(\mathcal{K}^{j})$ is explicitly identified
in Cases (i), (ii)(a) and (ii)(b) of the proof of Proposition 3.14. So the
a.s. convergence of
$D_{\textbf{0}}(\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A_{n}))$ follows
if we show that for all $1\leq j\leq L$ that a.s.,

(16)
$\lim_{n\to\infty}\mathbf{M}^{\phi}(\mathcal{L}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{L}^{j-1}_{n})=\mathbf{M}^{\phi}(\mathcal{K}^{j})$

with $\mathcal{K}^{j}_{n}$ as in (15).

The labels $\ell_{n}$ are with respect to $A_{n}$ but to distinguish labels
with respect to $W_{n}$ , the latter are denoted by $\ell_{W_{n}}$. We also
use $\ell_{n}^{j},\ell_{n}^{j-1}$ to represent labels with respect to
$\mathcal{L}^{j}_{n},\mathcal{L}^{j-1}_{n}$ respectively. We shall work with
realizations for which $N_{0},L<\infty$ and furthermore (14) holds. We shall
again divide into cases as in the proof of Proposition 3.14.

Without loss of generality assume that
$\mathcal{K}_{n}^{j}=\mathcal{K}_{n}^{j-1}\cup\\{\sigma_{j}\\}$ and
$\mathcal{L}_{n}^{j}=\mathcal{L}_{n}^{j-1}\cup\\{\sigma_{j}\\}$.

  * Case (i):

Suppose that $\ell^{j}_{W_{n}}(\sigma_{j})=1$ for some $n\geq N_{0}$. From
(13), (14) and Lemma 3.10, we obtain that there exists a chain map from
$\mathcal{K}^{j}_{n}$ to $\mathcal{L}^{j}_{m}$ satisfying Assumption 3.3 for
all $m\geq M_{n}$. Thus $\ell^{j}_{m}(\sigma_{j})=1$ for all $m\geq M_{n}$. So
we have that
$\operatorname{MSA}(\mathcal{K}^{j}_{m})=\operatorname{MSA}(\mathcal{K}^{j-1}_{m})$
for all $m\geq M_{n}$ and consequently
$\mathbf{M}^{\phi}(\mathcal{K}^{j}_{m})=\mathbf{M}^{\phi}(\mathcal{K}^{j-1}_{m})$
for all $m\geq M_{n}$ (see Lemmas 3.4(i) and 3.2(ii)). Hence (16) holds with
limit being $0$ for both the LHS and RHS.

  * Case (ii):

Suppose that $\ell^{j}_{W_{n}}(\sigma_{j})=-1$ for all $n\geq N_{0}$. Using
Lemma 3.10, (13) and (14), we see that there is chain map from
$\mathcal{L}^{j}_{n}$ and $\mathcal{K}^{j}_{m_{n}}$ for all $n\geq N_{0}$ that
satisfies Assumption 3.3. Thus we have that $\ell^{j}_{n}(\sigma_{j})=-1$ for
all $n\geq M_{0}:=M_{N_{0}}$ (see Lemma 3.4(ii)). So by the stability result
(Lemma 3.2(i)) ,we have that
$\operatorname{MSA}(\mathcal{K}^{j}_{n})\setminus\operatorname{MSA}(\mathcal{K}^{j-1}_{n})=\operatorname{MSA}(\mathcal{L}^{j}_{n})\setminus\operatorname{MSA}(\mathcal{L}^{j-1}_{n})=\\{\sigma_{j}\\}$
for all $n\geq M_{0}$. We subdivide this into two further cases.

    * (a):

Suppose
$\operatorname{MSA}(\mathcal{L}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{L}^{j}_{n})=\emptyset$
for all $n\geq M_{0}$ i.e., no negative faces in $\mathcal{L}^{j-1}_{n}$ turns
positive upon adding $\sigma_{j}$. Then we have that
$\mathbf{M}^{\phi}(\mathcal{L}^{j}_{n})-\mathbf{M}^{\phi}(\mathcal{L}^{j-1}_{n})=\phi(w(\sigma_{j}))$
and so (16) holds trivially with the limit being $\phi(w(\sigma_{j}))$ for
both the LHS and RHS.

    * (b):

Suppose that
$\operatorname{MSA}(\mathcal{L}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{L}^{j}_{n})\neq\emptyset$
for some $n\geq M_{0}$. Let us set
$\\{\tau^{j}_{n}\\}=\operatorname{MSA}(\mathcal{L}^{j-1}_{n})\setminus\operatorname{MSA}(\mathcal{L}^{j}_{n})$
i.e., $\ell_{m}^{j}(\tau^{j}_{n})=1$ and $\ell_{n}^{j-1}(\tau^{j}_{n})=-1$.

From (13), (14) and Lemma 3.10, we have that there exists a chain map between
$\mathcal{L}^{j}_{n}$ and $\mathcal{K}^{j}_{m_{n}}$. Lemma 3.5 now gives that
for all $m\geq m_{n}$, there exists $\pi^{j}_{m}\in\mathcal{K}^{j-1}_{m}$ such
that $\ell_{W_{m}}^{j}(\pi^{j}_{m})=1$, $\ell_{W_{m}}^{j-1}(\pi^{j}_{m})=-1$
and $w(\pi^{j}_{m})\leq w(\tau^{j}_{n})$. Thus using that $\phi$ is increasing

$\liminf_{n\to\infty}\phi(w(\tau^{j}_{n}))\geq\liminf_{m\to\infty}\phi(w(\pi^{j}_{n}))=\phi(w(\sigma_{j}))-\mathbf{M}^{\phi}(\mathcal{K}^{j}),$

where the limit follows from Case(ii)(b) in the proof of Proposition 3.14. Now
again using (13), (14), Lemmas 3.10 and 3.5, we can deduce that
$w(\pi^{j}_{n})\geq w(\tau^{j}_{m})$ for all $m\geq M_{n}$ and $n\geq N_{0}$.
Thus,

$\limsup_{n\to\infty}\phi(w(\tau^{j}_{n}))\leq\limsup_{m\to\infty}\phi(w(\pi^{j}_{m}))=\phi(w(\sigma_{j}))-\mathbf{M}^{\phi}(\mathcal{K}^{j}).$

This yields that
$\lim_{n\to\infty}\phi(w(\tau^{j}_{n}))=\phi(w(\sigma_{j}))-\mathbf{M}^{\phi}_{k}(\mathcal{K}^{j})$
and hence (16) holds always.

∎

###### Proof of Theorem 1.3.

The proof proceds by verifying the conditions of Theorem 2.3. The difficult
condition to verify is weak stabilization. Weak stabilization has already been
shown to hold in Proposition 1.2. Since translation invariance holds
trivially, we only have to show the fourth moment bound.

Now, all that remains is to verify the Poisson bounded moments condition. Let
$0\in A$ for some $A\in\mathfrak{A}$. From Proposition 3.13, we have that
there exist random variables $L_{A},M_{A}$ such that

(17) $\mathcal{D}(\mathcal{P}\cap
A\cup\\{0\\})\triangle\mathcal{D}(\mathcal{P}\cap
A)=\\{\sigma_{1},\ldots,\sigma_{L_{A}}\\}$

and $w(\sigma_{i})\leq M_{A}$ for all $1\leq i\leq L_{A}$. Then by Hölder’s
inequality, growth condition on $\phi$ and Theorem 3.1, we obtain

$|D_{\textbf{0}}(\mathbf{M}^{\phi}(\mathcal{D}(\mathcal{P}\cap A)))|^{4}\leq
16L_{A}M_{A}^{4p}.$

The Poisson bounded moment condition now follows by applying Cauchy-Schwarz
inequality and the tail bounds for $L_{A},M_{A}$ in Proposition 3.13.

It remains to show that the limiting variances
$\sigma^{2}(\mathbf{M}_{k},\varphi),\sigma^{2}(B_{k},\varphi)$ and
$\sigma^{2}(L_{k},\varphi)$ are non-zero. This is shown in upcoming
Proposition 3.17 by proving that these are non-zero random variables. ∎

###  3.7. Proof of variance lower bound

The key to our variance lower bound proof is the existence of a particular
robust configuration of points that gives non-trivial lower bounds on the add-
one cost for the total weight of minimal spanning acycles.

######  Lemma 3.15.

Let $\phi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a strictly increasing function.
For any $r>0$, there exists $\varepsilon>0$ (depending on $d$), a finite set
of points $\mathcal{Q}:=\mathcal{Q}(r)=\\{x_{1},\ldots,x_{2d+2}\\}\subset
B_{r}(\textbf{0})$ and disjoint sets $A(x_{i})\subset B_{\epsilon}(x_{i})$
with $|A(x_{i})|\geq c\theta_{d}\epsilon^{d}$ for some $c>0$ such that for any
finite point-set ${\mathcal{X}}$ with ${\mathcal{X}}\cap
B_{3r}(\textbf{0})=\\{y_{1},\ldots,y_{2d+2}\\}$ and $y_{i}\in A(x_{i})$ for
all $1\leq i\leq m$, the following inequalities hold:

(18)
$0<\phi(r/4)<D_{\textbf{0}}(\mathbf{M}^{\phi}_{k}({\mathcal{X}}))=\mathbf{M}^{\phi}_{k}({\mathcal{X}}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}({\mathcal{X}})\quad\mbox{for}\;\;1\leq
k\leq d,$ (19)
$0<\phi(r/4)<D_{\textbf{0}}(\mathbf{B}^{\phi}_{k}({\mathcal{X}}))=\mathbf{B}^{\phi}_{k}({\mathcal{X}}\cup\\{\textbf{0}\\})-\mathbf{B}^{\phi}_{k}({\mathcal{X}})\quad\mbox{for}\;1\leq
k<d.$

######  Remark 3.16.

We note that the proof of the above lemma also implies the result for
$D_{\textbf{0}}(\mathbf{L}_{k})$ for $1\leq k<d$. An upper bound of
$2^{d+1}\phi(dr)$ also holds for the above the add-one costs -
$D_{\textbf{0}}(\mathbf{M}^{\phi}_{k}({\mathcal{X}})),D_{\textbf{0}}(\mathbf{B}^{\phi}_{k}({\mathcal{X}})),D_{\textbf{0}}(\mathbf{L}_{k})$
\- and follow easily from our proofs. See Lemma 3.19 and proof of Lemma 3.15.

Assuming the above lemma, we prove the required condition for variance lower
bound and then work towards the proof of the lemma. Recall
$D_{\infty}(\mathbf{M}^{\phi}_{k})$, $D_{\infty}(\mathbf{B}^{\phi}_{k})$, and
$D_{\infty}(\mathbf{L}_{k})$ as defined in Proposition 1.2.

######  Proposition 3.17.

Let assumptions be as in Theorem 1.3. The random variables
$D_{\infty}(\mathbf{M}^{\phi}_{k})$, $D_{\infty}(\mathbf{B}^{\phi}_{k})$ and
$D_{\infty}(\mathbf{L}_{k})$ are non-zero.

###### Proof.

We shall use Proposition 1.2 and Lemma 3.15 to prove that
$D_{\infty}(\mathbf{M}^{\phi}_{k})$ is non-zero. The same proof may be
followed to show that $D_{\infty}(\mathbf{B}^{\phi}_{k})$ and
$D_{\infty}(\mathbf{L}_{k})$ are non-zero; see also Remark 3.16. So, we shall
skip the details for the proofs for $D_{\infty}(\mathbf{B}^{\phi}_{k})$ and
$D_{\infty}(\mathbf{L}_{k})$. We shall again drop the subscript $k$.

From Proposition 1.2, we have that
$D_{\textbf{0}}\mathbf{M}^{\phi}(\mathcal{P}\cap W_{n})\to
D_{\infty}(\mathbf{M}^{\phi})$ a.s. as $n\to\infty$. Thus, we have that

(20)
$\mathbb{P}(D_{\infty}(\mathbf{M}^{\phi})>0)=\lim_{n\to\infty}\mathbb{P}(D_{\textbf{0}}\mathbf{M}^{\phi}(\mathcal{P}\cap
W_{n})>0).$

Since $\phi$ is strictly increasing and non-negative, we have that
$\phi(r/4)>0$ for $r>0$. Let $n$ be such that $n>4r$. We shall show that there
exists $C_{0}>0$ (depending on $r,\varepsilon,d$) such that for all $n>4r$

(21) $\mathbb{P}(D_{\textbf{0}}\mathbf{M}^{\phi}(\mathcal{P}\cap
W_{n})>0)\geq\mathbb{P}(D_{\textbf{0}}\mathbf{M}^{\phi}(\mathcal{P}\cap
W_{n})\geq\phi(r/4))>C_{0}.$

Thus, we obtain that $D_{\infty}(\mathbf{M}^{\phi})$ is a non-zero random
variable. Hence, to complete the proof it suffices to show (21).

Set $\mathcal{P}_{n}:=\mathcal{P}\cap W_{n}$. From Lemma 3.15 and using that
$n>4r$ we have that

$\displaystyle\mathbb{P}(D_{\textbf{0}}\mathbf{M}^{\phi}(\mathcal{P}\cap
W_{n})\geq\phi(r/4))$ $\displaystyle\geq\mathbb{P}(|\mathcal{P}_{n}\cap
B_{3r}(\textbf{0})|=2d+2,|\mathcal{P}_{n}\cap A(x_{i})|=1\,\forall 1\leq i\leq
2d+2)$ $\displaystyle\geq\mathbb{P}(|\mathcal{P}\cap
B_{3r}(\textbf{0})|=2d+2,|\mathcal{P}\cap A(x_{i})|=1\,\forall 1\leq i\leq
2d+2)>0,$

where the last probability is non-zero can be shown using that $|A(x_{i})|\geq
c\theta_{d}\epsilon^{d},i=1,\ldots,2d+2$ (i.e., $A(x_{i})$’s have non-trivial
measure) and the two properties of the Poisson process (see Section 2.4).
Thus, we have proved (21) and that $D_{\infty}(\mathbf{M}^{\phi})$ is a non-
zero random variable as required. ∎

Now we shall we focus on the proof of Lemma 3.15. We first introduce the
configuration then prove the required properties. Without loss of generality,
we set $r=1$ and $d\geq 2$. The case of MSAs on 1-dimensional spaces is
straightforward. Consider $(d+1)$ points which lie the unit $d$-sphere and
form a regular $d$-simplex, i.e. all points are mutually equidistant. These
form a $d$-simplex which we denote $[p_{1},\ldots,p_{d+1}]$. For each
$(d-1)$-face, we add a point on the ray from the origin to the center of the
face but lying on the hypersphere of radius $\rho$ where $\rho>20d$. Note that
by the center of the face, we are referring to the center of the minimum
enclosing ball of the vertices of the face. We denote these points
$\\{q_{1},\ldots,q_{d+1}\\}$ such that $q_{i}$ corresponds to the $(d-1)$-face
with $p_{i}$ removed. The configuration for $d=2$ is shown in Figure 3.

Figure 3.  Configuration of points $\mathcal{Q}(r)$ in $\mathbb{R}^{2}$.

Setting
$\mathcal{Q}:=\mathcal{Q}(1)=\\{p_{1},\ldots,p_{d+1},q_{1},\ldots,q_{d+1}\\}$,
let $\mathcal{D}(\mathcal{Q})$ denote the Delaunay complex built on
$\mathcal{Q}$ and $\mathring{\mathcal{D}}(\mathcal{Q})$ denote the Delauanay
complex built on $\mathcal{Q}\cup\\{\textbf{0}\\}$.

######  Lemma 3.18.

Let $\mathcal{Q}:=\mathcal{Q}(1)$ as above and in $\mathcal{D}(\mathcal{Q})$,
consider the $d$-simplex $\\{q_{1},\allowbreak
p_{2},\allowbreak\ldots,\allowbreak p_{d+1}\\}$. Let $a$ and $\rho^{\prime}$
denote the center and radius of its corresponding circumsphere, then

$||a||-\rho^{\prime}>\frac{1}{10d}.$

The above bound also holds for all $d$-simplices
$\\{p_{1},\ldots,p_{i-1},q_{i},p_{i+1},\ldots,p_{d}\\},i=1,\ldots,d.$

######  Lemma 3.19.

Let $\mathcal{Q}:=\mathcal{Q}(1)$ be as above and $k\leq d$. Then the
following holds. (1)
$\mathring{\mathcal{D}}(\mathcal{Q})\setminus\mathcal{D}(\mathcal{Q})$
consists of at most $2^{d+1}$ simplices whose maximum weight is $\frac{d}{2}$
and minimum weight is $1/2$. (2)
$\mathcal{D}(\mathcal{Q})\setminus\mathring{\mathcal{D}}(\mathcal{Q})$
consists of a single $d$-simplex of weight $1$.

###### Proof.

Lemma 3.18 implies that the $d$-simplices in $\mathcal{D}(\mathcal{Q})$ are

$[p_{1},\ldots,p_{d+1}]\cup\\{[p_{1},\ldots,p_{i-1},q_{i},p_{i+1},\ldots,p_{d+1}]:i=1,\ldots,d+1\\}$

and the $d$-simplices in $\mathring{\mathcal{D}}(\mathcal{Q})$ are

$\\{[\textbf{0},p_{1},\ldots,p_{i-1},p_{i+1},\ldots,p_{d+1}],[p_{1},\ldots,p_{i-1},q_{i},p_{i+1},\ldots,p_{d+1}]:i=1,\ldots,d+1\\}.$

Note that the two complexes are nothing but the above $d$-simplices and all
the lower dimensional ones contained in these $d$-simplices. These are
consequences of the fact that the circumspheres of the $d$-simplices are empty
in $\mathcal{Q}$ or $\mathcal{Q}\cup\\{0\\}$ as required and hence the
$d$-simplices are in $\mathcal{D}(\mathcal{Q})$ or
$\mathring{\mathcal{D}}(\mathcal{Q})$ as needed.

Thus (2) now follows easily as the only $d$-simplex in
$\mathring{\mathcal{D}}(\mathcal{Q})\setminus\mathcal{D}(\mathcal{Q})$ is
$[p_{1},\ldots,p_{d+1}]$ which is weight $1$ by construction.

In $\mathring{\mathcal{D}}$, the simplex
$[p_{1},\ldots,p_{d+1}]\in\mathcal{D}$ is replaced by the simplices

$\\{[\textbf{0},p_{i_{1}},\ldots,p_{i_{k}}]:1\leq k\leq
d,\\{i_{1},\ldots,i_{k}\\}\subset\\{1,\ldots,d+1\\}\\}.$

This gives the upper bound of at most $2^{d+1}$ simplices. The minimum weight
is achieved by a $1$-simplex. For example, we may take $[\textbf{0},p_{i}]$
for any $1\leq i\leq d+1$ and check that $w([\textbf{0},p_{i}])=1/2$.

The maximum weight is achieved by any of the $d$-simplices. For example,
consider $[\textbf{0},p_{2},\ldots,p_{d+1}]$. While all the simplices are
contained in the unit sphere, the weight for a simplex in the Delaunay complex
may be larger. To bound the new weight we must find where 0 and $p_{i}$ are
all equidistant. Since the weight function is known to induce a filtration,
the $d$-simplices must have the largest weight. We can directly compute the
radius as $\frac{dr}{2}$ using straightforward geometry (see Appendix A). ∎

###### Proof of Lemma 3.15.

Let $\mathcal{Q}=\mathcal{Q}(r):=r\mathcal{Q}(1)$, where $\mathcal{Q}(1)$ is
as above. With an abuse of notation, we shall denote the weights on
$\mathcal{D}(\mathcal{Q}(r))$ and $\mathcal{D}(\mathcal{Q}(1))$ by $w$.
Observe that $[v_{0},\ldots,v_{k}]\in\mathcal{D}_{\mathcal{Q}(1)}$ iff
$[rv_{0},\ldots,rv_{k}]\in\mathcal{D}_{\mathcal{Q}(r)}$ and thus trivially

$w([rv_{0},\ldots,rv_{k}])=rw([v_{0},\ldots,v_{k}]).$

Hence, the weights in Lemma 3.19 when applied to $\mathcal{Q}(r)$ undergo a
simple scaling by $r$. We first give bounds for $\mathcal{Q}=\mathcal{Q}(r)$
and then derive bounds for ${\mathcal{X}}$ by a perturbation argument. Set
$\mathbf{M}^{\phi}_{k}(\mathcal{Q})=\mathbf{M}^{\phi}_{k}(\mathcal{D}(\mathcal{Q}))$
and similarly for $\mathcal{Q}\cup\\{\textbf{0}\\}$ and
$\mathbf{B}^{\phi}_{k}$.

We consider two cases. First for $k<d$, $k$-simplices are only added. While
the weights of the simplices which are in both complexes may change, the
weights may only increase. Since we add at least one $k$-simplex with weight
at least $\frac{r}{2}$ and the added edges have weight $\frac{r}{2}$, all
other simplices must have higher weight. Also we observe that we add at least
one positive and at least one negative simplex for $k<d$ (see Lemma 2.1).
Using Theorem 2.2, this gives the following bound for $k<d$.

(22)
$\mathbf{M}^{\phi}_{k}(\mathcal{Q}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}(\mathcal{Q})\geq\phi\left(\frac{r}{2}\right)\,;\,\mathbf{B}^{\phi}_{k}(\mathcal{Q}\cup\\{\textbf{0}\\})-\mathbf{B}^{\phi}_{k}(\mathcal{Q})\geq\phi\left(\frac{r}{2}\right).$

For $k=d$, we need only consider $\mathbf{M}^{\phi}_{d}$, since there are no
births in dimension $d$. We note that we add $(d+1)$ $d$-simplices, one for
each $(d-1)$-face, each of weight $\frac{dr}{2}$ and we remove one $d$-simplex
of weight $r$. This gives the lower bounds

(23)
$\displaystyle\begin{split}\mathbf{M}^{\phi}_{d}(\mathcal{Q}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{d}(\mathcal{Q})&\geq(d+1)\phi\left(\frac{dr}{2}\right)-\phi(r)\\\
&\geq
d\phi\left(\frac{dr}{2}\right)\geq\phi\left(\frac{r}{2}\right)>0\end{split}$

The final inequalities follow since $\phi$ is a strictly increasing function
and $d>1$.

We extend this to ${\mathcal{X}}$ as in statement of the lemma by a
perturbation argument for $\varepsilon>0$ small enough. For $d\geq 3$, choose
$\varepsilon>0$ such that

(24) $2(d+2)\varepsilon<\frac{r}{4},$

Now let ${\mathcal{X}}$ be as in the statement of the lemma and assume that
$\mathcal{Q}^{\prime}:={\mathcal{X}}\cap
B_{3r}(\textbf{0})=\\{p^{\prime}_{1},\ldots,p^{\prime}_{d+1},q^{\prime}_{1},\ldots,q^{\prime}_{d+1}\\}$
where $|p_{i}-p^{\prime}_{i}|,|q_{i}-q^{\prime}_{i}|\leq\varepsilon$ for all
$i=1,\ldots,d+1$, i.e. $A(p_{i})=B_{\varepsilon}(p_{i})$ and
$A(q_{i})=B_{\varepsilon}(q_{i})$.

Observe that there is a bijection between simplices in
$\mathcal{D}_{\mathcal{Q}^{\prime}}$ (resp.
$\mathring{\mathcal{D}}_{\mathcal{Q}}$) and $\mathcal{D}_{\mathcal{Q}}$ (resp.
$\mathcal{D}_{\mathcal{Q}^{\prime}}$) with the difference between the
corresponding weights bounded above by $2(d+2)\varepsilon$. Thus by assumption
on ${\mathcal{X}}$ and construction of $\mathcal{Q}$, we have that

$\mathbf{M}^{\phi}_{k}({\mathcal{X}}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}({\mathcal{X}})=\mathbf{M}^{\phi}_{k}(\mathcal{Q}^{\prime}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}(\mathcal{Q}^{\prime}),$

and similarly for $\mathbf{B}^{\phi}_{k}$. Now following the derivation as in
(22) and using our choice of $\varepsilon$, we derive that for $1\leq k<d$

$\phi(r/4)<\mathbf{M}^{\phi}_{k}(\mathcal{X}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}(\mathcal{X}),$
$\phi(r/4)<\mathbf{B}^{\phi}_{k}(\mathcal{X}\cup\\{\textbf{0}\\})-\mathbf{B}^{\phi}_{k}(\mathcal{X}),$

Using (23) in the above argument, we can also derive for $k=d$, $d>3$ that

$\phi(r/4)<\mathbf{M}^{\phi}_{k}(\mathcal{X}\cup\\{\textbf{0}\\})-\mathbf{M}^{\phi}_{k}(\mathcal{X}).$

These prove (19) with $A(x_{i})=B_{\varepsilon}(x_{i})$. Thus, the above
arguments have shown (18) for $1\leq k<d,d\geq 2$ and $k=d\geq 3$ with
$A(x_{i})=B_{\varepsilon}(x_{i})$. This leaves the case of $k=d=2$ open in
(18).

Let $k=d=2$. As we only require $\phi$ to be a positive increasing function,
the above perturbation argument does not work for $d=2$ as is for the lower
bound. In (23), it is sufficient to show that after perturbation, at least one
of the added simplices has a weight higher than the removed simplex. Once this
is established, the rest of the proof remains the same. As in the higher
dimensional case, we must choose $\varepsilon>0$ small enough so that the
combinatorial structure of the complex changes in a predictable way.
Therefore, as in (24), we can choose $\varepsilon<\frac{r}{40}$, and set
$A(q_{i})=B_{\varepsilon}(q_{i})$. Let a cone at a point $x$ in the direction
$\overrightarrow{v}$ of angle $\alpha$ be denoted by
$\mathrm{Cone}(x,\overrightarrow{v},\alpha)$. We the set:

$\displaystyle A(p_{1})$
$\displaystyle=B_{\varepsilon}(p_{1})\cap\mathrm{Cone}(p_{1},(-2,-1),\pi/12)$
$\displaystyle A(p_{2})$
$\displaystyle=B_{\varepsilon}(p_{2})\cap\mathrm{Cone}(p_{2},(0,-1),\pi/12)$
$\displaystyle A(p_{3})$
$\displaystyle=B_{\varepsilon}(p_{3})\cap\mathrm{Cone}(p_{3},(2,-1),\pi/12)$

This can be seen in Figure 4.

Figure 4. Balls around the points in the configuration for $d=2$ are shown in
gray. The corresponding cones $A(p_{i})$ are shown in green.

Let $p^{\prime}_{i}\in A(p_{i})$ for all $i$. To complete the proof of bounds
in (18) and (19), it suffices to show that

$w([p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}])\leq
w([p^{\prime}_{1},\textbf{0},p^{\prime}_{3}]).$

We observe that the angle
$\angle(p^{\prime}_{1},\textbf{0},p^{\prime}_{3})\geq\frac{2\pi}{3}$, which we
denote by $\alpha$. Further, let $c$ denote the center of the circumcircle of
the points $\\{p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}\\}$. It is
straightforward to also check that the angle
$\angle(p^{\prime}_{1},c,p^{\prime}_{3})\geq\frac{2\pi}{3}$, which we denote
by $\alpha^{\prime}$.

The weight $w([p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}])$ can be related
with $||\overline{p^{\prime}_{1}p^{\prime}_{3}}||$ and $\alpha$.

$||\overline{p^{\prime}_{1}p^{\prime}_{3}}||^{2}=2w^{2}([p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}])(1-\cos\alpha^{\prime})$

Likewise, the $w([p^{\prime}_{1},\textbf{0},p^{\prime}_{3}]$ may be expressed
as

$\displaystyle
w([p^{\prime}_{1},\textbf{0},p^{\prime}_{3}]=\frac{||\overline{p^{\prime}_{1}p^{\prime}_{3}}||}{2\sin\alpha}$

Combining these we obtain

$\displaystyle\frac{w^{2}([p^{\prime}_{1},\textbf{0},p^{\prime}_{3}]}{w^{2}([p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}])}=\frac{(1-\cos\alpha^{\prime})}{2\sin^{2}\alpha}$

Rewriting $\alpha=2\pi/3+\delta$ and $\alpha^{\prime}=2\pi/3+\delta^{\prime}$
for $\delta,\delta^{\prime}>0$, we must show that

$\displaystyle\frac{(1-\cos(2\pi/3+\delta^{\prime}))}{2\sin^{2}(2\pi/3+\delta)}\geq
1$

We note that $\delta^{\prime}\geq\delta$, which are functions of
$\varepsilon$, where $\delta^{\prime}\rightarrow 0$ as $\varepsilon\rightarrow
0$. So as $\delta^{\prime}\rightarrow 0$, we can directly verify that this
expression approaches 1 from above proving the result for $\varepsilon$ small
enough. Using the triangle inequality on the points, one can directly verify
that the above inequality holds for $\varepsilon<\frac{r}{40}$. As stated
above, this implies that the weight of at least one added simplex is greater
that the removed simplex, so the lower bound of $\phi(r/2)$ holds.

∎

######  Remark 3.20.

The construction above does not hold for all $\phi$ if we are using the
Delaunay-Čech weights rather than Alpha weights. Rather, the configuration
must be changed to achieve similar bounds. The alternate configuration is
moving one of the inner points to the origin (and suitable adjusting the outer
points), resulting in a flattened $d$-simplex, which is translated so that the
centroid of the simplex is the origin. For this case, the upper bound as
stated holds, but the lower bound can be shown to be strictly positive and
depending on $r$ for all $\phi$.

## Acknowledgements

DY’s research was partially supported by SERB-MATRICS Grant MTR/2020/000470,
DST-INSPIRE Faculty grant and CPDA from the Indian Statistical Institute. The
project also benefitted from discussion between the authors during their visit
to Banff International Research Station in August 2017 and would like to thank
the institution for its support. The authors would like to thank Omer
Bobrowski and Gugan Thoppe for discussions at an early stage of the project.
DY is very thankful to K. D. Trinh for pointing out some simplifications
regarding growth conditions and variance lower bound using results from [42,
7]. DY is thankful to Xiaochuan Yang for some comments on an earlier draft.

## References

  * Aldous and Steele [1992] D. Aldous and J. M. Steele.  Asymptotics for Euclidean minimal spanning trees on random points.  _Probability Theory and Related Fields_ , 92(2):247–258, 1992.
  * Alexander [1996] K. S. Alexander.  The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees.  _The Annals of Applied Probability_ , 6(2):466–494, 1996.
  * Baccelli et al. [2020] F. Baccelli, B. Błaszczyszyn, and M. Karray.  Random measures, point processes, and stochastic geometry.  Lecture Notes, 2020.  URL https://hal.inria.fr/hal-02460214.
  * Bauer and Edelsbrunner [2017] U. Bauer and H. Edelsbrunner.  The Morse theory of Čech and Delaunay complexes.  _Transactions of the American Mathematical Society_ , 369(5):3741–3762, 2017.
  * Björner [1995] A. Björner.  Topological methods.  _Handbook of combinatorics_ , 2:1819–1872, 1995.
  * Błaszczyszyn et al. [2019] B. Błaszczyszyn, D. Yogeshwaran, and J. E. Yukich.  Limit theory for geometric statistics of point processes having fast decay of correlations.  _The Annals of Probability_ , 47(2):835–895, 2019\.
  * Can and Trinh [2022] V. H. Can and K. D. Trinh.  Random connection models in the thermodynamic regime: central limit theorems for add-one cost stabilizing functionals.  _Electronic Journal of Probability_ , 27:1–40, 2022.
  * Cao [2021] S. Cao.  Central limit theorems for combinatorial optimization problems on sparse Erdős–Rényi graphs.  _The Annals of Applied Probability_ , 31(4):1687–1723, 2021.
  * Carlsson [2009] G. Carlsson.  Topology and data.  _Bulletin of the Ameriancan Mathematical Society_ , 46(2):255–308, 2009.
  * Carlsson [2014] G. Carlsson.  Topological pattern recognition for point cloud data.  _Acta Numerica_ , 23:289–368, 2014.
  * Chatterjee and Sen [2017] S. Chatterjee and S. Sen.  Minimal spanning trees and Stein’s method.  _The Annals of Applied Probability_ , 27(3):1588–1645, 2017.
  * Cohen-Steiner et al. [2007] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer.  Stability of persistence diagrams.  _Discrete and Computational Geometry_ , 37(1):103–120, 2007.
  * Delfinado and Edelsbrunner [1993] C. J. A. Delfinado and H. Edelsbrunner.  An incremental algorithm for Betti numbers of simplicial complexes.  In _Proceedings of the ninth annual Symposium on Computational geometry_ , pages 232–239. ACM, 1993.
  * Divol and Polonik [2019] V. Divol and W. Polonik.  On the choice of weight functions for linear representations of persistence diagrams.  _Journal of Applied and Computational Topology_ , 3(3):249–283, 2019.
  * Edelsbrunner and Harer [2010] H. Edelsbrunner and J. L. Harer.  _Computational Topology, An Introduction_.  American Mathematical Society, Providence, RI, 2010.
  * Edelsbrunner and Ölsböck [2020] H. Edelsbrunner and K. Ölsböck.  Tri-partitions and bases of an ordered complex.  _Discrete & Computational Geometry_, 64(3):759–775, 2020.
  * Hatcher [2002] A. Hatcher.  _Algebraic Topology_.  Cambridge University Press, Cambridge, New York, 2002.
  * Hino and Kanazawa [2019] M. Hino and S. Kanazawa.  Asymptotic behavior of lifetime sums for random simplicial complex processes.  _Journal of the Mathematical Society of Japan_ , 71(3):765–804, 2019.
  * Hiraoka and Shirai [2017] Y. Hiraoka and T. Shirai.  Minimum spanning acycle and lifetime of persistent homology in the Linial–Meshulam process.  _Random Structures and Algorithms_ , 51(2):315–340, 2017.
  * Hiraoka and Tsunoda [2018] Y. Hiraoka and K. Tsunoda.  Limit theorems for random cubical homology.  _Discrete and Computational Geometry_ , 60(3):665–687, 2018.
  * Hiraoka et al. [2018] Y. Hiraoka, T. Shirai, and K. D. Trinh.  Limit theorems for persistence diagrams.  _The Annals of Applied Probability_ , 28(5):2740–2780, 2018.
  * Janson [1995] S. Janson.  The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph.  _Random Structures and Algorithms_ , 7(4):337–355, 1995.
  * Kalai [1983] G. Kalai.  Enumeration of $\mathbb{Q}$-acyclic simplicial complexes.  _Israel Journal of Mathematics_ , 45(4):337–351, 1983.
  * Kanazawa [2021] S. Kanazawa.  Law of large numbers for Betti numbers of homogeneous and spatially independent random simplicial complexes.  _Random Structures and Algorithms_ , 2021.
  * Kesten and Lee [1996] H. Kesten and S. Lee.  The central limit theorem for weighted minimal spanning trees on random points.  _The Annals of Applied Probability_ , pages 495–527, 1996.
  * Krebs and Polonik [2019] J. T. N. Krebs and W. Polonik.  On the asymptotic normality of persistent Betti numbers.  _arXiv:1903.03280_ , 2019.
  * Lachièze-Rey et al. [2020] R. Lachièze-Rey, G. Peccati, and X. Yang.  Quantitative two-scale stabilization on the Poisson space.  _arXiv:2010.13362_ , 2020.
  * Last and Penrose [2017] G. Last and M. Penrose.  _Lectures on the Poisson Process_ , volume 7.  Cambridge University Press, 2017.
  * Lee [1997] S. Lee.  The central limit theorem for Euclidean minimal spanning trees I.  _The Annals of Applied Probability_ , 7(4):996–1020, 1997.
  * Lee [1999] S. Lee.  The central limit theorem for Euclidean minimal spanning trees II.  _Advances in Applied Probability_ , 31(4):969–984, 1999.
  * McGivney and Yukich [1999] K. McGivney and J. E. Yukich.  Asymptotics for Voronoi tessellations on random samples.  _Stochastic Process. Appl._ , 83(2):273–288, 1999\.
  * Munkres [1984] J. R. Munkres.  _Elements of Algebraic Topology_.  Addison-Wesley, 1984.
  * Penrose [2003] M. D. Penrose.  _Random geometric graphs_ , volume 5 of _Oxford Studies in Probability_.  Oxford University Press, Oxford, 2003.
  * Penrose [2007] M. D. Penrose.  Laws of large numbers in stochastic geometry with statistical applications.  _Bernoulli_ , 13(4):1124–1150, 2007.
  * Penrose and Yukich [2001] M. D. Penrose and J. E. Yukich.  Central limit theorems for some graphs in computational geometry.  _The Annals of Applied Probability_ , 11(4):1005–1041, 2001.
  * Penrose and Yukich [2002] M. D. Penrose and J. E. Yukich.  Limit theory for random sequential packing and deposition.  _The Annals of Applied Probability_ , 12(1):272–301, 2002.
  * Penrose and Yukich [2003] M. D. Penrose and J. E. Yukich.  Weak laws of large numbers in geometric probability.  _The Annals of Applied Probability_ , 13(1):277–303, 2003.
  * Ramey [1983] D. B. Ramey.  A non-parametric test of bimodality with applications to cluster analysis.  Technical report, NASA, 1983.
  * Skraba and Bobrowski [2020] P. Skraba and O. Bobrowski.  Homological percolation: The formation of giant k-cycles.  _International Mathematics Research Notices_ , 2020.
  * Skraba et al. [2020] P. Skraba, G. Thoppe, and D. Yogeshwaran.  Randomly weighted $d-$complexes: Minimal spanning acycles and persistence diagrams.  _The Electronic Journal of Combinatorics_ , 27(2):P2.11, 2020.
  * Steele [1997] J. M. Steele.  _Probability theory and combinatorial optimization_ , volume 69 of _CBMS-NSF Regional Conference Series in Applied Mathematics_.  SIAM, Philadelphia, 1997.
  * Trinh [2019] K. D. Trinh.  On central limit theorems in stochastic geometry for add-one cost stabilizing functionals.  _Electronic Communications in Probability_ , 24, 2019.
  * Yogeshwaran et al. [2017] D. Yogeshwaran, E. Subag, and R. J. Adler.  Random geometric complexes in the thermodynamic regime.  _Probability Theory and Related Fields_ , 167(1):107–142, 2017.
  * Yukich [1998] J. E. Yukich.  _Probability Theory of Classical Euclidean Optimization problems_ , volume 1675 of _Lecture Notes in Mathematics_.  Springer-Verlag, Berlin, 1998.
  * Zomorodian and Carlsson [2005] A. Zomorodian and G. Carlsson.  Computing persistent homology.  _Discrete and Computational Geometry_ , 33(2):249–274, 2005.

##  Appendix A Some geometric computations.

###### Proof of Lemma 3.18.

This follows from elementary geometry. Let $z$ be the center point of the
simplex $[p_{2},\ldots,p_{d+1}]$, where the ray from the origin to $q_{1}$
intersects the simplex. See Figure 3 for an illustration. We note that

$\displaystyle||z||=\frac{1}{d},\qquad\qquad||\overline{zp_{i}}||=\frac{\sqrt{d^{2}-1}}{d},\,i=2,\ldots,d+1.$

We may rewrite:

$||a||-\rho^{\prime}=||\overline{zq_{1}}||+||z||-2\rho^{\prime}=||\overline{zq_{1}}||+\frac{1}{d}-2\rho^{\prime}$

We set $||\overline{zq_{1}}||\geq 10d$, so that $\rho\geq 20d\geq
10d+\frac{1}{d}$. Let $\alpha$ denote the angle of $zq_{1}p_{2}$. Then we have

$\cos\alpha=\frac{||\overline{zq_{1}}||}{||\overline{p_{2}q_{1}}||},\qquad\rho^{\prime}=\frac{||\overline{p_{2}q_{1}}||}{2\cos\alpha}$

Combining these we obtain,

$2\rho^{\prime}=||\overline{zq_{1}}||+\frac{d^{2}-1}{d^{2}||\overline{zq_{1}}||}$

Substituting above

$\displaystyle||a||-\rho^{\prime}$
$\displaystyle=||\overline{zq_{1}}||+\frac{1}{d}-2\rho^{\prime}$
$\displaystyle=\frac{1}{d}-\frac{d^{2}-1}{d^{2}||\overline{zq_{1}}||}$

Setting $||\overline{zq_{1}}||\geq 10d$,

$\displaystyle||a||-\rho^{\prime}$
$\displaystyle\geq\frac{1}{d}-\frac{d^{2}-1}{10d^{3}}$
$\displaystyle=\frac{9d^{2}+1}{10d^{3}}\geq\frac{1}{10d}$

yielding the result. ∎

We give a derivation of the geometric fact used in the proof of Lemma 3.19.

##### Weight of added $d$-simplex in $\mathcal{Q}(r)$:
$w([0,p_{2},\ldots,p_{d+1}]=dr/2$.

Here we compute the weight of the added $d$-simplices in the Delaunay complex
for the configuration $\mathcal{Q}(r)$ in Section 3.7. Without loss of
generality, we can consider the simplex
$\sigma=[\textbf{0},p_{1},p_{2},\ldots,p_{d}]$. We now compute $w=w(\sigma)$.
Let $z$ be the center of $\tau$, and $s$ denote the circumcenter of
$\\{p_{1},p_{2},\ldots,p_{d}]\\}$ and $w$ the radius of the circumsphere (see
Figure 5 below).

Figure 5. An illustration of how the weight of the added simplex, denoted $w$,
is computed, i.e. the distance to the circumcenter $a$.

We have the following identity $\cos\alpha=1/d$. Applying the cosine rule:

$\displaystyle w^{2}=r^{2}+w^{2}-2wr\cos\alpha\quad\Rightarrow\quad
w=\frac{dr}{2}$

we obtain the result.