disposition title author date section sectionentry subsection

# Morse Theory for Chromatic Delaunay Triangulations

Abhinav Natarajan Mathematical Institute, University of Oxford. Email:
<EMAIL_ADDRESS>Thomas Chaplin Mathematical Institute, University of
Oxford. Email<EMAIL_ADDRESS>Adam Brown  Maria-Jose Jimenez
Universidad de Sevilla. Email<EMAIL_ADDRESS>
(March 2024)

###### Abstract

The chromatic alpha filtration is a generalization of the alpha filtration
that can encode spatial relationships among classes of labelled point cloud
data, and has applications in topological data analysis of multi-species data.
In this paper we introduce the chromatic Delaunay–Čech and chromatic
Delaunay–Rips filtrations, which are computationally favourable alternatives
to the chromatic alpha filtration. We use generalized discrete Morse theory to
show that the Čech, chromatic Delaunay–Čech, and chromatic alpha filtrations
are related by simplicial collapses. Our result generalizes a result of Bauer
and Edelsbrunner from the non-chromatic to the chromatic setting. We also show
that the chromatic Delaunay–Rips filtration is locally stable to perturbations
of the underlying point cloud. Our results provide theoretical justification
for the use of chromatic Delaunay–Čech and chromatic Delaunay–Rips filtrations
in applications, and we demonstrate their computational advantage with
numerical experiments.

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Contributions
    3. 1.3 Related Work
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Offset and Čech Filtrations
    3. 2.3 Alpha Filtration
    4. 2.4 Chromatic Alpha Filtration
    5. 2.5 Chromatic Delaunay Triangulation and General Position Conditions
    6. 2.6 Chromatic Delaunay–Čech and Chromatic Delaunay–Rips Filtrations
    7. 2.7 Generalities on Geometric Simplicial Complexes
    8. 2.8 Generalized Discrete Morse Theory
    9. 2.9 Karush-Kuhn-Tucker Conditions
  3. 3 Collapsing the Chromatic Delaunay Triangulation
    1. 3.1 Construction of Generalized Vector Field Inducing the Collapse
    2. 3.2 Proof that the Generalized Vector Field is a Generalized Gradient
  4. 4 Morse Theoretic Structure of the Chromatic Alpha Filtration Function
    1. 4.1 Showing that the Filtration Function is Morse
    2. 4.2 Pairing Lemmas
  5. 5 Proof of Main Results
    1. 5.1 Proof of Theorem A
    2. 5.2 Proof of Theorem B
  6. 6 Consequences for Practical Computations
    1. 6.1 Chromatic Delaunay–Čech Filtration
    2. 6.2 Chromatic Delaunay–Rips Filtration
    3. 6.3 Numerical Experiments
    4. 6.4 Summary
  7. 7 Future Directions
  8. 8 Acknowledgements
  9. A General Position Assumptions
    1. A.1 Genericity Results
    2. A.2 General Position and Chromatic Genericity

##  1 Introduction

###  1.1 Motivation

The field of topological data analysis (TDA) is founded on the idea of
interpreting datasets as geometric objects that can be studied with tools from
algebraic topology. When the dataset is a point cloud
$X\subset\mathbb{R}^{d}$, we build a filtration of topological spaces,
typically a filtered simplicial complex, to serve as a multiscale
approximation of the hypothetical space from which the data are assumed to be
sampled. We can then describe the geometry of the dataset through topological
invariants of the filtration, such as persistent homology [ELZ00, ZC05], that
are stable with respect to perturbations of the data.

More recent data collection techniques in fields like cancer biology,
geospatial analysis, and ecology produce chromatic (labelled) data with
interactions between the points of each colour. In these cases one is
interested not just in the spatial structure of the data as a whole, but also
in the spatial relationships among subsets of the data produced by the
colouring; see Figure 1.

Figure 1:  The point cloud above does not have interesting topological
features a priori, but when considering the colouring, the blue points enclose
a void that is filled in by the orange points. This spatial relationship can
be captured by the chromatic alpha filtration.

One way to formalize this is to study the inclusion maps among such subsets of
points. Mathematically speaking, a chromatic set is given by a set of points
$X\subset\mathbb{R}^{d}$ and a surjective function $\mu:X\to\\{0,\ldots,s\\}$
for some $s\in\mathbb{N}$. Given sets of colours $I\subset
J\subset\\{0,\ldots,s\\}$, the spatial relationship between the set of points
with colours in $I$ and $J$ respectively is captured by the spatial properties
of the inclusion map $\mu^{-1}(I)\hookrightarrow\mu^{-1}(J)$. Here too $X$ is
represented by a filtered simplicial complex. If the subsets of $X$ produced
by the colouring correspond to filtered subcomplexes of the original
filtration—in other words, the construction of the filtration is functorial
with respect to the input dataset—then we can study the induced inclusion maps
among these filtered subcomplexes.

Common choices for building a filtration in TDA are the Čech filtration
$\operatorname{\check{C}}_{\bullet}(X)$, the Vietoris–Rips filtration
$\operatorname{VR}_{\bullet}(X)$, and the alpha filtration
$\operatorname{\mathcal{A}}_{\bullet}(X)$. The Čech and Vietoris–Rips
filtrations have the necessary functoriality property—indeed,
$\operatorname{\check{C}}_{\bullet}(\mu^{-1}(I))$ and
$\operatorname{VR}_{\bullet}(\mu^{-1}(I))$ are sub-filtrations of
$\operatorname{\check{C}}_{\bullet}(\mu^{-1}(J))$ and
$\operatorname{VR}_{\bullet}(\mu^{-1}(J))$ respectively. Unfortunately, both
of these constructions are filtrations of the complete simplicial complex on
the vertex set $X$, in which the number of simplices scales exponentially with
the number of data points $n$. This makes their computation impractical for
large datasets. On the other hand, if $X$ is in general position, then the
alpha filtration, which was first defined in [Ede95], is a filtration of the
Delaunay triangulation $\operatorname{Del}(X)$ associated to $X$ [Del34]. The
number of simplices in $\operatorname{Del}(X)$ is bounded by a polynomial in
$n$ of degree $\left\lfloor\frac{d}{2}\right\rfloor$ [McM70, Sei95], and when
the points of $X$ are sampled independently and uniformly from the unit ball,
then the expected number of simplices of $\operatorname{Del}(X)$ is linear in
$n$ [Dwy91]. This makes it feasible to compute the alpha filtration when the
ambient space is low-dimensional. Moreover,
$\operatorname{\mathcal{A}}_{r}(X)$ is homotopy equivalent to
$\operatorname{\check{C}}_{r}(X)$ for any $r\geq 0$, so the alpha filtration
captures the same topological information as the Čech filtration.
Unfortunately, alpha filtrations and the underlying Delaunay triangulations
are not functorial with respect to inclusions of point clouds; that is,
$\operatorname{Del}(\mu^{-1}(I))$ is not necessarily a sub-complex of
$\operatorname{Del}(\mu^{-1}(J))$ (see Figure 2). This deficiency is addressed
by the chromatic Delaunay triangulation $\operatorname{Del}^{\mu}(X)$,
introduced by Biswa et al. [Bis+22], and the corresponding chromatic alpha
filtration $\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X)$, introduced by
[Mon+24]. The chromatic alpha filtration has the following properties:

  1. 1.

$\operatorname{\mathcal{A}}_{r}^{\mu}(X)$ is a deformation retract of
$\operatorname{\check{C}}_{r}(X)$ for any colouring $\mu$ of the data.

  2. 2.

Given sets of colours $I\subset J\subset\\{0,\ldots,s\\}$, the chromatic alpha
filtration associated to the subset of points with colours in $I$ is a
filtered subcomplex of the chromatic alpha filtration associated to the subset
of points with colours in $J$.

  3. 3.

For a random colouring, the expected number of simplices in
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$ is
$O(n^{\lceil\frac{d}{2}\rceil})$ [Bis+22], which is far fewer than the number
of simplices in the Čech filtration.

Thus, the chromatic alpha filtration interpolates between the functoriality of
the Čech filtration and the sparsity of the alpha filtration, while preserving
the same spatial information. In fact, the Čech and alpha filtrations are
extremal cases of chromatic alpha filtrations (see Section 2.4 for the precise
relationship).

$a$$b$$c$$d$ (a) $\operatorname{Del}(X)$

$a$$b$$c$$d$$e$ (b) $\operatorname{Del}(X\cup\\{e\\})$

Figure 2:  In the above, $a=(0.6,0.8)$, $b=(0.4,0.15)$, $c=(0.75,-0.05)$,
$d=(0.95,0.15)$, and $e=(0.6,0.45)$. Denoting $X=\\{a,b,c,d\\}$, the inclusion
$X\hookrightarrow X\cup\\{e\\}$ does not induce a simplicial map
$\operatorname{Del}(X)\hookrightarrow\operatorname{Del}(X\cup\\{e\\})$ since
$\operatorname{Del}(X)$ contains the 1-simplex $bd$ while
$\operatorname{Del}(X\cup\\{e\\})$ does not.

###  1.2 Contributions

The properties stated above make the chromatic alpha filtration an attractive
choice for quantifying spatial relations in low-dimensional data. However, the
sparsity of the filtration is partially offset by the computational complexity
of producing the filtration values themselves. To simplify computations, we
introduce the chromatic Delaunay–Čech filtration
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\mu}_{\bullet}(X)$
and the chromatic Delaunay–Rips filtration
$\operatorname{\operatorname{Del}VR}_{\bullet}^{\mu}(X)$. Under a general
position assumption, these are filtrations of the chromatic Delaunay
triangulation where the filtration value of each simplex is given by its
filtration value in the Čech and Vietoris–Rips filtration respectively (see
Section 2.6 for the precise definitions). Previous work has already shown the
effectiveness of the monochromatic Delaunay–Rips filtration in machine
learning applications [MM23]. Moreover, our constructions are substantially
faster to compute than the chromatic alpha filtration for large datasets (see
Section 6). Our goal in this paper is to provide theoretical justification for
the use of our constructions.

If $\mu$ and $\nu$ are labellings of $X$, we say that $\nu$ is a refinement of
$\mu$ if the partition of $X$ induced by $\nu$ is a refinement of the
partition of $X$ induced by $\mu$. In this case, for fixed $r\geq 0$ the
various filtrations mentioned above fit into the following commutative
diagram, where
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{\bullet}(X)$ in
the bottom row denotes the monochromatic Delaunay–Čech filtration (cf. (16) in
Section 2).

${\operatorname{\mathcal{A}}^{\nu}_{r}(X)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\nu}_{r}(X)}$${\operatorname{\check{C}}_{r}(X)}$${\operatorname{\mathcal{A}}^{\mu}_{r}(X)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\mu}_{r}(X)}$${\operatorname{\check{C}}_{r}(X)}$${\operatorname{\mathcal{A}}_{r}(X)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}(X)}$${\operatorname{\check{C}}_{r}(X)}$
(1)

Using a generalization of discrete Morse theory, Bauer and Edelsbrunner [BE16]
showed that the complexes in the bottom row are related by simplicial
collapses—in particular, the inclusions are simple homotopy equivalences and
induce isomorphisms on homology. Montesano et al. [Mon+24] proved that the
inclusions in the left column are homotopy equivalences. We use generalized
discrete Morse theory to prove that there are simplicial collapses in the
middle column and in each row. More precisely we prove the following results:

######  Theorem A.

Let $X\subset\mathbb{R}^{d}$ be a finite set of points in general position,
and let $\mu,\nu$ be colourings of $X$ such that $\nu$ refines $\mu$. For any
$r\geq 0$ there are simplicial collapses
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\nu}(X)\searrow\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\mu}(X)$.

######  Theorem B.

Let $X\subset\mathbb{R}^{d}$ be a finite set of points in general position and
let $\mu$ be a colouring of $X$. Then for any $r\geq 0$ there are simplicial
collapses
$\operatorname{\check{C}}_{r}(X)\searrow\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\mu}_{r}(X)\searrow\operatorname{\mathcal{A}}_{r}^{\mu}(X)$.

Theorem B generalizes the main result of [BE16] to the chromatic case, thereby
answering a question posed in [Mon+24].

Our proof of Theorem A relies on the construction of a novel generalized
discrete Morse function on the chromatic Delaunay triangulation that is
structurally compatible with the Čech filtration. The details of this
construction are given in Section 3. On the other hand, our proof of Theorem B
is an adaptation of the proof in [BE16] to the chromatic setting. To enable
this adaptation, in Section 4 we use tools from convex optimization to study
the discrete Morse-theoretic structure of a family of filtrations which
includes the Čech, chromatic alpha, and chromatic Delaunay–Čech filtrations.
We prove that for each of these filtrations, its filtration function (which
assigns to each simplex its filtration value) is a generalized discrete Morse
function, and we relate the combinatorial structure of the corresponding Morse
gradient to the geometry of the underlying point cloud. The Morse theoretic
structure of filtration functions has been described before for the Čech
filtration [ALS13] and alpha filtration [Ede03, MS24], and these results were
unified in [BE16]. More recently, it was shown in [Mon+24] that the chromatic
alpha filtration function is a generalized discrete Morse function. Our work
simultaneously extends each of these results to a larger class of filtrations.
Finally, in Section 5 we prove Theorems A and B using the results from
Sections 3 and 4.

Simplicial expansions and collapses are examples of simple homotopy
equivalence, which is a combinatorial strengthening of the notion of homotopy
equivalence for CW-complexes, and which is algebraically characterized by the
vanishing of Whitehead torsion [Coh73]. In light of this, Theorems A and B
immediately imply the following result.

######  Corollary C.

For any $r\geq 0$, each inclusion in (1) is a simple homotopy equivalence, and
therefore each simplicial complex in that diagram has the same simple homotopy
type.

We note that our result does not imply that there are simplicial collapses
along the first column in (1); indeed our methods used to prove Theorem A
cannot be adapted for this case (see Remark 5.4 for more details).

From a computational perspective, the main consequences of our results are:

  1. 1.

The inclusion of the chromatic Delaunay–Čech filtration into the Čech
filtration is a homotopy equivalence at each filtration level, which makes the
chromatic Delaunay–Čech filtration a drop-in alternative to the Čech and
chromatic alpha filtrations for the purpose of quantifying spatial
relationships through persistent homology.

  2. 2.

The chromatic Delaunay–Rips filtration, which is related to the chromatic
Delaunay–Čech filtration via nested inclusions (see Section 6), serves to
approximate the Čech filtration for persistent homology computations.

To further justify the use of the chromatic Delaunay–Rips filtration in
practical computations, in Section 6 we show that the chromatic Delaunay–Rips
filtration associated to a point cloud is locally stable to perturbations of
the underlying point cloud. In fact, we show that this local stability extends
to maps between chromatic Delaunay–Rips filtrations that are induced by
inclusions of the underlying point clouds (Proposition 6.7). This is a
generalization of the stability result in [MM23], in which the authors prove
that the monochromatic Delaunay–Rips filtration is locally stable to
perturbations of the underlying point cloud. In Section 6 we also document the
empirical runtime performance of the chromatic Delaunay–Čech and chromatic
Delaunay–Rips filtrations, vis-à-vis the chromatic alpha filtration. The
numerical evidence suggests that the former two filtrations are significantly
faster to compute than the chromatic alpha, Čech, and Vietoris–Rips
filtrations, and are therefore viable alternatives for analysing spatial
relationships in low-dimensional point clouds.

###  1.3 Related Work

The Čech filtration originated in the work of Alexandroff and Čech in
algebraic topology, and gained importance in TDA due to the work of E.
Carlsson, G. Carlsson, and de Silva [CCD06, SC04]. Its foundational role in
TDA is justified by the fact that the Čech complex
$\operatorname{\check{C}}_{r}(X)$ has the same homotopy type as the union of
closed balls of radius $r$ centred on the points in $X$ (see Section 2.2).
Vietoris–Rips complexes originated in the work of Vietoris [Vie27], and were
popularized in the work of Rips and Gromov [Gro87]. While the Vietoris–Rips
filtration does not have the same geometric interpretation as the Čech
filtration, it still contains meaningful information about the spatial
structure of $X$ [Hau96, Lat01, Cha+10, ALS13]. Moreover, it is much faster to
compute the filtration values of the Vietoris–Rips filtration, and this
advantage carries over to the chromatic Delaunay–Rips filtration. The
chromatic alpha filtration was first defined for the special case of a bi-
colouring $\mu:X\to\\{0,1\\}$ by Reani and Bobrowski [RB23], under the name
coupled alpha filtration.

The chromatic alpha filtration is also related to the Delaunay bi-filtration
[Alo+23], which is defined for a function on a point cloud, in the case when
the class labels are hierarchically nested. We leave the consideration of this
special case for future work. Aside from chromatic alpha filtrations, other
approaches for studying spatial relations have been previously considered.
Bauer and Edelsbrunner [BE16] generalize alpha filtrations to “selective
Delaunay filtrations”. Given point clouds $X\subset Y$, they construct
filtrations
$\operatorname{Del}_{\bullet}(Y,Y)\subset\operatorname{Del}_{\bullet}(X,Y)$
that are pointwise homotopy equivalent to
$\operatorname{\check{C}}_{\bullet}(Y)$ and
$\operatorname{\check{C}}_{\bullet}(X)$ respectively (see Section 4.1 for more
details). We will make use of their construction in our proofs, but we remark
that the chromatic filtrations in this paper are functorial over a larger
class of inclusions (for example, see Remark 2.1 for a precise description of
the functoriality of the chromatic alpha filtration). Stolz et al. [Sto+23]
analyse spatial relations using Dowker filtrations [Dow52, CM18] and multi-
species witness filtrations. The multi-species witness filtration is based
upon the witness complex [DC04], which can often be seen as a Delaunay
triangulation with respect to an intrinsic metric on the data points [Sil08].

Discrete Morse theory, the analogue of Morse theory for finite CW-complexes,
was originally formulated by Forman [For98] in terms of real-valued functions
on the set of cells of the complex. Chari [Cha00] showed that the theory could
equivalently be described in terms of pairings in the face poset of the
complex. In our work we use a generalization of discrete Morse theory,
proposed by [Fre09], that considers arbitrary intervals in the face poset
instead of pairings. Similar ideas have been considered earlier in the form of
the “Cluster Lemma” [Her05, Jon03]. Separately, the idea of collapsing
simplicial complexes along intervals in the face poset has been considered
before [Weg75, Koz00].

##  2 Preliminaries

In this section we will briefly lay out the relevant background material for
the rest of the paper. In Sections 2.2 to 2.6 we recall the definition and
properties of the offset, Čech, alpha, and chromatic alpha filtrations, and
the Delaunay and chromatic Delaunay triangulations. We also define the
chromatic Delaunay–Čech and chromatic Delaunay–Rips filtrations. In Section
2.7 we will define some general notions relating to geometric realizations of
simplicial complexes. In Section 2.8 we recall results from a generalization
of discrete Morse theory allowing for intervals larger than pairs. Finally, in
Section 2.9 will state the Karush-Kuhn-Tucker conditions from the theory of
convex optimization, which we will use to study the filtration function of the
various filtrations we work with.

###  2.1 Notation

$X$ will always denote a finite point cloud in $\mathbb{R}^{d}$. All point
clouds and simplicial complexes are assumed to be finite unless otherwise
stated. If $s$ is a positive integer then $[s]$ will denote the set
$\\{0,\ldots,s-1\\}$. For a point cloud $X\subset\mathbb{R}^{d}$ we define a
colouring of $X$ to be a surjective function $\mu:X\to[s+1]$, and a chromatic
set is a point cloud with a colouring. There is an induced labelled partition
of $X$ into disjoint non-empty subsets $X_{m}=\mu^{-1}(m)$, and by abuse of
notation we will write $\mu=\\{X_{0},\ldots,X_{s}\\}$. We can equivalently
define a colouring of $X$ to be a labelled partition of $X$ into disjoint non-
empty subsets. Now let $X\subset Y\subset\mathbb{R}^{d}$, $s\leq s^{\prime}$,
and let $\mu=\\{X_{0},\ldots,X_{s}\\}$ and
$\nu=\\{Y_{0},\ldots,Y_{s^{\prime}}\\}$ be colourings of $X$ and $Y$
respectively. We say that $\nu$ is a refinement of $\mu$, and we write
$\mu\preceq\nu$, if for each $i\in[s+1]$ there exists $J\subset[s^{\prime}+1]$
such that $X_{i}=\bigcup_{j\in J}Y_{j}$.

If $K$ is an (abstract or geometric) simplicial complex and $\sigma$ is an
$n$-simplex in $K$ we write $\sigma^{(n)}\in K$. If $\tau$ is a face (resp.
strict face) of $\sigma$ we write $\tau\leq\sigma$ (resp. $\tau<\sigma$). A
filtration $K_{\bullet}$ is a functor from the poset $[0,\infty]$ to the
category of topological spaces or simplicial complexes, such that the map
$K_{s}\hookrightarrow K_{t}$ is an inclusion of spaces or subcomplexes
whenever $0\leq s\leq t\leq\infty$. The underlying space (resp. underlying
simplicial complex) of the filtration is $K_{\infty}$, and we say that
$K_{\bullet}$ is a filtration of $K_{\infty}$. When $K_{\bullet}$ is a
filtered simplicial complex, the filtration function of $K_{\bullet}$ is the
function $K_{\infty}\to\mathbb{R}$ defined by
$\sigma\mapsto\inf\\{t\in\mathbb{R}\mid\sigma\in K_{t}\\}$, and the filtration
value of a simplex $\sigma\in K_{\infty}$ is the value of this function at
$\sigma$.

If $\mathcal{C}$ and $\mathcal{D}$ are categories then we use
$[\mathcal{C},\mathcal{D}]$ to denote the category of functors from
$\mathcal{C}$ to $\mathcal{D}$. If $c$ is an object of $\mathcal{C}$, then
$\mathcal{C}\downarrow c$ will denote the slice category; that is, the
category whose objects are morphisms $d\to c$ in $\mathcal{C}$ and whose
morphisms are commuting triangles:

${d}$${e}$${c}$

###  2.2 Offset and Čech Filtrations

For $x\in X$ and $r\geq 0$ let $D_{r}(x)=\\{y\in\mathbb{R}^{d}\mid|x-y|\leq
r\\}$ denote the closed $d$-dimensional ball of radius $r$ centred on $x$. The
offset filtration $\mathcal{O}_{\bullet}(X)$ is a filtration of
$\mathbb{R}^{d}$ defined by $\mathcal{O}_{r}(X)=\cup_{x\in X}D_{r}(x)$. The
Čech filtration $\operatorname{\check{C}}_{\bullet}(X)$ is a filtration of the
complete simplicial complex on the vertex set $X$, and
$\operatorname{\check{C}}_{r}(X)$ is defined as the nerve of the cover
$\\{D_{r}(x)\\}_{x\in X}$ of $\operatorname{\mathcal{O}}_{r}(X)$:

$\displaystyle\operatorname{\check{C}}_{r}(X)$
$\displaystyle\mathrel{\coloneqq}\left\\{\sigma\subset
X\mid\bigcap_{x\in\sigma}D_{r}(x)\neq\emptyset\right\\}$ (2)
$\displaystyle=\\{\sigma\subset X\mid\text{$\sigma$ is contained in a closed
ball of radius $r$}\\}.$ (3)

Let $\mathsf{Point}_{d}$ be the category of finite point sets in
$\mathbb{R}^{d}$ and their inclusions. If $X\subset Y\subset\mathbb{R}^{d}$
and $0\leq s\leq t\leq\infty$ then
$\operatorname{\mathcal{O}}_{s}(X)\subset\operatorname{\mathcal{O}}_{t}(Y)$,
so the offset filtration defines a functor
$\mathsf{Point}_{d}\times[0,\infty]\to\mathsf{Top}$. Similarly, an inclusion
of point sets induces an inclusion of the respective Čech filtrations, so the
Čech filtration defines a functor from $\mathsf{Point}_{d}\times[0,\infty]$ to
the category of simplicial complexes $\mathsf{SimpComp}$. We let
$|\cdot|:\mathsf{SimpComp}\to\mathsf{Top}$ denote the functor that sends a
simplicial complex to its geometric realization, which is well-defined up to
homeomorphism. Then there is a functor
$\mathsf{Point}_{d}\times[0,\infty]\to\mathsf{Top}$ defined by
$(X,t)\mapsto|\operatorname{\check{C}}_{t}(X)|$.

We say that two functors $F,G:[0,\infty]\to\mathsf{Top}$ have the same
persistent homotopy type if there is a natural transformation $F\Rightarrow G$
whose components are homotopy equivalences. By a functorial version of the
Nerve lemma (Theorem B in [Bau+23]), there is a natural transformation from
the geometric realization of the Čech filtration to the offset filtration that
is a pointwise homotopy-equivalence. More explicitly there are homotopy
equivalences
$|\operatorname{\check{C}}_{t}(X)|\to\operatorname{\mathcal{O}}_{t}(X)$ for
each $(X,t)\in\mathsf{Point}_{d}\times[0,\infty]$, and if $0\leq s\leq
t\leq\infty$ and $X\subset Y$ then these maps fit into the following
commutative diagram.

${{|\operatorname{\check{C}}_{s}(Y)|}}$${{|\operatorname{\check{C}}_{t}(Y)|}}$${{|\operatorname{\check{C}}_{s}(X)|}}$${{|\operatorname{\check{C}}_{t}(X)|}}$${{\operatorname{\mathcal{O}}_{s}(Y)}}$${{\operatorname{\mathcal{O}}_{t}(Y)}}$${{\operatorname{\mathcal{O}}_{s}(X)}}$${{\operatorname{\mathcal{O}}_{t}(X)}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$
(4)

In particular the Čech filtration and the offset filtration have the same
persistent homotopy type (and hence persistent homology) for any fixed
$X\in\mathsf{Point}_{d}$, and any homotopy-invariant of the inclusion
$\operatorname{\mathcal{O}}_{\bullet}(X)\hookrightarrow\operatorname{\mathcal{O}}_{\bullet}(Y)$
(such as the induced map on persistent homology) is isomorphic to the
corresponding invariant of the inclusion
$|\operatorname{\check{C}}_{\bullet}(X)|\hookrightarrow|\operatorname{\check{C}}_{\bullet}(Y)|$.

###  2.3 Alpha Filtration

For $x\in X$ the Voronoi domain of $x$, and the Voronoi ball of $x$ with
radius $r\geq 0$ are defined as

$\displaystyle\operatorname{dom}(x,X)$
$\displaystyle\mathrel{\coloneqq}\\{y\in\mathbb{R}^{d}\mid\|y-x\|\leq\|y-x^{\prime}\|\text{
for all }x^{\prime}\in X\\},$ (5) $\displaystyle D^{\prime}_{r}(x,X)$
$\displaystyle\mathrel{\coloneqq}D_{r}(x)\cap\operatorname{dom}(x,X).$ (6)

The alpha filtration $\operatorname{\mathcal{A}}_{\bullet}(X)$ is the nerve of
the collection $\\{D_{\bullet}^{\prime}(x,X)\\}_{x\in X}$:

$\operatorname{\mathcal{A}}_{r}(X)\mathrel{\coloneqq}\left\\{\sigma\subset
X\mid\bigcap_{x\in\sigma}D^{\prime}_{r}(x,X)\neq\emptyset\right\\}.$ (7)

By construction the underlying simplicial complex of the alpha filtration has
vertex set $X$.

We say that a sphere in $\mathbb{R}^{d}$ is empty of $E\subset X$ if it does
not bound any points of $E$. Then the alpha filtration can be equivalently
defined by

$\operatorname{\mathcal{A}}_{r}(X)=\\{\sigma\subset X\mid\text{$\sigma$ has a
circumsphere of radius $r$ empty of $X$}\\}.$ (8)

For fixed $X$ the alpha filtration defines a functor
$[0,\infty]\to\mathsf{SimpComp}$. It is straightforward to check that the
union of Voronoi balls equals the union of closed balls: $\cup_{x\in
X}D^{\prime}_{r}(x,X)=\cup_{x\in X}D_{r}(x)$. Then the functorial nerve lemma
(Theorem B in [Bau+23]) implies that the alpha filtration has the same
persistent homotopy type as the offset filtration.

The Voronoi domains comprise a polyhedral decomposition of $\mathbb{R}^{d}$
called the Voronoi tessellation associated to $X$. The geometric dual to the
Voronoi tessellation is called the Delaunay mosaic of $X$ and denoted by
$\operatorname{Del}(X)$, and is a polyhedral decomposition of the convex hull
of $X$. If the Delaunay mosaic is simplicial then we call it the Delaunay
triangulation of $X$, and in this case it is the unique geometric realization
of $\operatorname{\mathcal{A}}_{\infty}(X)$ whose vertices coincide with $X$.
Using Equation 8, the Delaunay mosaic is guaranteed to be simplicial if $X$
satisfies the following general position condition.

######  (GP1).

We say $X\subset\mathbb{R}^{d}$ satisfies (GP1) if for all $0\leq k<d$, no
$k+3$ points of $X$ lie on a common $k$-sphere.

The condition (GP1) is mild; for example, it is satisfied almost surely when
$X$ is the realization of a stationary Poisson point process (see Lemma 2.1 in
[ENR17]).

###  2.4 Chromatic Alpha Filtration

Now we describe chromatic alpha filtrations, which generalize alpha
filtrations to chromatic sets. We follow the terminology of [Mon+24] in this
section.

Let $\mu=\\{X_{0},\ldots,X_{s}\\}$ be a colouring of $X$. For each $m\in[s+1]$
we have a collection of open sets $\\{D^{\prime}_{r}(x,X_{m})\\}_{x\in
X_{m}}$, that is, the collection of Voronoi balls of radius $r$ with respect
to the set of $m$-coloured points. The chromatic alpha filtration is defined
as the nerve of the union of this collection
$\cup_{m=0}^{s}\\{D^{\prime}_{r}(x,X_{m})\\}_{x\in X_{m}}$ (see Figure 3):

$\operatorname{\mathcal{A}}^{\mu}_{r}(X)\mathrel{\coloneqq}\left\\{\sigma\subset
X\mid\bigcap_{x\in\sigma}D^{\prime}_{r}(x,X_{\mu(x)})\neq\emptyset\right\\}.$
(9)

Figure 3: A bi-chromatic set in $\mathbb{R}^{2}$, and the associated
collection of Voronoi balls whose nerve is the chromatic alpha filtration.

By construction, the underlying simplicial complex of the chromatic alpha
filtration has vertex set $X$. The filtration is invariant to a permutation of
the labels $\\{0,\ldots,s\\}$ and only depends on the induced (unlabelled)
partition. As in the case of the alpha filtration, the functorial nerve lemma
shows that the chromatic alpha filtration has the same persistent homotopy
type as the offset filtration.

The alpha filtration and Čech filtrations are extremal cases of the chromatic
alpha filtration. When $\mu$ gives each point the same colour (that is, $X$ is
monochromatic) then $X_{\mu(x)}=X$ for all $x\in X$, and in this case the
chromatic alpha filtration reduces to the alpha filtration. When $\mu$ gives
each point a distinct colour (the maximal colouring) then
$\operatorname{dom}(x,X_{\mu(x)})=\operatorname{dom}(x,\\{x\\})=\mathbb{R}^{d}$,
and hence the Voronoi balls are just Euclidean balls:
$D_{r}^{\prime}(x,X_{\mu(x)})=D_{r}(x)$. In this case the chromatic alpha
filtration is isomorphic to the Čech filtration.

The two most important properties of the chromatic alpha filtration are its
sparsity and its functoriality. For example, if $X$ has $n$ points and the
colouring is chosen uniformly randomly, then the expected number of simplices
of the chromatic alpha filtration is
$O\left(n^{\left\lceil\frac{d}{2}\right\rceil}\right)$; we refer the reader to
[Bis+22] for more details. We focus here on the functoriality.

From the definition we see that the chromatic alpha filtration is functorial
with respect to inclusions of points in the following sense. Suppose
$I\subset[s+1]$ is some subset of colours,
$X_{I}\mathrel{\coloneqq}\mu^{-1}(I)$ is the set of $I$-coloured points, and
$\mu_{I}$ is the restriction of $\mu$ to $X_{I}$. Then for each $r\geq 0$,
$\operatorname{\mathcal{A}}^{\mu_{I}}_{r}(X_{I})$ is the full subcomplex of
$\operatorname{\mathcal{A}}^{\mu}_{r}(X)$ spanned by the vertices in $X_{I}$.

Slightly less obvious is the fact that the chromatic alpha filtration is
functorial with respect to refinement of class labels. That is, if
$\mu=\\{X_{0},\ldots,X_{s}\\}$ and
$\nu=\\{X_{0}^{\prime},\ldots,X_{s^{\prime}}^{\prime}\\}$ are colourings of
$X$ such that $\mu\preceq\nu$, then
$\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X)$ is a sub-filtration of
$\operatorname{\mathcal{A}}^{\nu}_{\bullet}(X)$. To see this, observe that for
any $x\in X$, we have $X_{\mu(x)}\supset X^{\prime}_{\nu(x)}$ and hence
$\operatorname{dom}(x,X_{\mu(x)})\subset\operatorname{dom}(x,X^{\prime}_{\nu(x)})$.
Then if $\sigma\in\operatorname{\mathcal{A}}^{\mu}_{r}(X)$ we have by
definition

$\displaystyle\emptyset\neq\bigcap_{x\in\sigma}D^{\prime}_{r}(x,X_{\mu(x)})\subset\bigcap_{x\in\sigma}D^{\prime}_{r}(x,X^{\prime}_{\nu(x)})$

and hence $\sigma\in\operatorname{\mathcal{A}}^{\nu}_{r}(X)$. An important
consequence of this fact is that $\operatorname{\mathcal{A}}^{\mu}_{r}(X)$ is
a strong deformation retract of $\operatorname{\mathcal{A}}_{r}^{\nu}(X)$ for
every $r\geq 0$. This is a consequence of Corollary 0.20 in [Hat02] applied to
the inclusion
$\operatorname{\mathcal{A}}_{r}^{\mu}(X)\hookrightarrow\operatorname{\mathcal{A}}_{r}^{\nu}(X)$,
which is a homotopy equivalence by the nerve lemma.

######  Remark 2.1.

We can summarize the functoriality of the chromatic alpha filtration in terms
of a category of chromatic sets. Let $\mathsf{ChrSet}_{d}$ be the category
defined as follows:

  * •

Objects are pairs $(X,\mu)$ where $X\subset\mathbb{R}^{d}$ is a finite point
set and $\mu$ is a colouring of $X$.

  * •

There is a morphism $(X,\mu)\to(Y,\nu)$ if $X\subset Y$ and $\mu\preceq\nu$.

Then the chromatic alpha filtration is a functor

$\begin{array}[]{rcl}\operatorname{\mathcal{A}}:\mathsf{ChrSet}_{d}\times[0,\infty]&\to&\mathsf{SimpComp},\\\
(X,\mu,r)&\mapsto&\operatorname{\mathcal{A}}_{r}^{\mu}(X)\end{array}$ (10)

that takes morphisms in the domain to inclusions of subcomplexes. More
precisely, the inclusion
$\operatorname{\mathcal{A}}_{s}^{\mu}(X)\hookrightarrow\operatorname{\mathcal{A}}^{\nu}_{t}(Y)$
is the simplicial map induced by the vertex map that is the inclusion of $X$
into $Y$. Let $\mathcal{F}$ be the forgetful functor
$\mathsf{ChrSet}_{d}\to\mathsf{Point}_{d}$ that forgets the colouring. Then
the persistent homotopy equivalence between the chromatic alpha filtration and
the offset filtration can be restated as follows: there is a natural
transformation
$\operatorname{\mathcal{A}}\Rightarrow\operatorname{\mathcal{O}}\circ(\mathcal{F}\times\operatorname{\mathbf{1}}_{[0,\infty]})$
that is a pointwise homotopy equivalence, yielding commutative diagrams of the
form:

${{|\operatorname{\mathcal{A}}^{\nu}_{s}(Y)|}}$${{|\operatorname{\mathcal{A}}^{\nu}_{t}(Y)|}}$${{|\operatorname{\mathcal{A}}^{\mu}_{s}(X)|}}$${{|\operatorname{\mathcal{A}}^{\mu}_{t}(X)|}}$${{\operatorname{\mathcal{O}}_{s}(Y)}}$${{\operatorname{\mathcal{O}}_{t}(Y)}}$${{\operatorname{\mathcal{O}}_{s}(X)}}$${{\operatorname{\mathcal{O}}_{t}(X)}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$
(11)

Similar to the alpha filtration, there is an equivalent characterization of
the chromatic alpha filtration in terms of spheres. Suppose
$\sigma\in\operatorname{\mathcal{A}}_{r}^{\mu}(X)$. By definition there exists
a point $z\in\bigcap_{x\in\sigma}D^{\prime}_{r}(x,X_{\mu(x)})$. In particular
for each $m\in\mu(\sigma)$ we have $\displaystyle z\in\bigcap_{x\in\sigma\cap
X_{m}}D^{\prime}_{r}(x,X_{m})$. This implies that for each $m\in\mu(\sigma)$,
there is a sphere $S_{m}$ of radius at most $r$ and centred at $z$ such that
$S_{m}$ is empty of points in $X_{m}$ and passes through all the points of
$\sigma$ of colour $m$. This motivates the following definitions. For any
subset of colours $\gamma\subset[s+1]$ we define a $\gamma$-stack to be a
collection of $|\gamma|$ concentric $(d-1)$-spheres $S=(S_{m})_{m\in\gamma}$.
The radius of the stack $S$ is the radius of the largest sphere in $S$,
denoted $\operatorname{Rad}(S)$, and the centre of the stack $S$ is the common
centre of all the spheres in $S$. We say that a $\gamma$-stack
$S=(S_{m})_{m\in\gamma}$ passes through $\sigma$ if each $S_{m}$ is a
circumsphere of the points of $\sigma$ of colour $m$ and each point of
$\sigma$ lies on a sphere in $S$. We say that $S$ is an empty stack if each
$S_{m}$ is empty of points of $X$ of colour $m$ (see Figure 4(a)). Hence, we
have

$\operatorname{\mathcal{A}}_{r}^{\mu}(X)=\\{\sigma\subset X\mid\text{there
exists an empty stack of radius $\leq r$ passing through $\sigma$}\\}.$ (12)

If $\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X)$ then we let
$S^{\mu}(\sigma)$ denote the empty stack of minimum radius that passes through
$\sigma$. Notice that if $X$ is monochromatic then $S^{\mu}(\sigma)$ is the
empty circumsphere of minimum radius for $\sigma$, and when $\mu$ is the
maximal colouring then the largest sphere of $S^{\mu}(\sigma)$ is simply the
minimum bounding ball of $\sigma$.

###  2.5 Chromatic Delaunay Triangulation and General Position Conditions

We now describe a particular geometric realization of the underlying
simplicial complex of the chromatic alpha filtration. Let
$\\{e_{0},\ldots,e_{s}\\}\subset\mathbb{R}^{s}$ be the vertices of the
$s$-simplex in $\mathbb{R}^{s}$ formed by the zero vector and the standard
basis vectors. We define the chromatic lift of $X$ with respect to $\mu$ as
the subset of $\mathbb{R}^{d+s}$ given by

$X^{\mu}=\bigcup_{m=0}^{s}X_{m}\times\\{e_{m}\\},$ (13)

i.e., points of distinct colours are lifted to distinct parallel $d$-planes of
$\mathbb{R}^{d+s}$. For $x\in X$ we let $x^{\mu}$ denote its lift in
$X^{\mu}$.

Lemma 3.6 in [Mon+24] shows that there is a bijective correspondence between
$[s+1]$-stacks in $\mathbb{R}^{d}$ and $(d+s-1)$-spheres in $\mathbb{R}^{d+s}$
that intersect each of the $d$-planes $\mathbb{R}^{d}\times e_{m}$ for
$m\in\\{0,\ldots,s\\}$. In one direction, a $(d+s-1)$-sphere $S$ in
$\mathbb{R}^{d+s}$ corresponds to the stack comprised of the $(d-1)$-spheres
obtained by intersecting $S$ with each of the $d$-planes
$\mathbb{R}^{d}\times\\{e_{m}\\}$ for each $m\in[s+1]$ (see Figure 4).

$a$$c$$b$$d$$o$ (a) An empty stack passing through the chromatic set
$\\{a,b,c,d\\}$.

$\mathbb{R}^{d}\times e_{1}$$\mathbb{R}^{d}\times
e_{0}$$a^{\mu}$$c^{\mu}$$b^{\mu}$$d^{\mu}$ (b) An empty circumsphere passing
through the chromatic lift of $\\{a,b,c,d\\}$.

Figure 4:  Correspondence between stacks and spheres. For $X$ given by the set
of orange and blue points above, the abstract 3-simplex $abcd$ belongs to
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$, and has geometric realization
as the tetrahedron $(abcd)^{\mu}$ in $\operatorname{Del}^{\mu}(X)$.

Under this correspondence, an $[s+1]$-stack passing through $\sigma\subset X$
corresponds to a $(d+s-1)$-sphere passing through $\sigma^{\mu}\subset
X^{\mu}$, and empty stacks correspond to empty spheres. In light of Equations
8 and 12, the correspondence implies that there is an isomorphism
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)\cong\operatorname{\mathcal{A}}_{\infty}(X^{\mu})$.
Therefore, the chromatic Delaunay mosaic $\operatorname{Del}^{\mu}(X)$ is
defined to be the Delaunay mosaic $\operatorname{Del}(X^{\mu})$. If
$\operatorname{Del}^{\mu}(X)$ is simplicial then it is the unique geometric
realization of $\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$ with vertex set
$X^{\mu}$, and it is called the chromatic Delaunay triangulation of $X$. We
will need a condition on $X$ to ensure that $\operatorname{Del}^{\mu}(X)$ is
simplicial for all colourings $\mu$ of $X$, namely that $X^{\mu}$ satisfies
(GP1) for all $\mu$. By the correspondence between stacks and spheres, this
requirement can be formulated in terms of stacks.

######  (GP2).

We say $X\subset\mathbb{R}^{d}$ satisfies (GP2) if for any colouring
$\mu:X\to[s+1]$ any $[s+1]$-stack passes through at most $(d+s+1)$-points.

Notice that (GP2) is a generalization of (GP1), in that $X$ satisfies (GP1) if
it satisfies (GP2) for the monochromatic colouring. Now suppose $X$ satisfies
(GP2). By construction, $\operatorname{Del}^{\mu}(X)$ is a triangulation of
the convex hull of $X^{\mu}$, and the projection of $\mathbb{R}^{d+s}$ to the
first $d$ coordinates sends this convex hull to the convex hull of $X$. Unlike
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$, the geometric complex
$\operatorname{Del}^{\mu}(X)$ is not invariant to permuting the class labels
of $\mu$. However, such a permutation induces an isometry of the ambient space
$\mathbb{R}^{d+s}$. If $\mu^{\prime}$ is the colouring of $X$ after changing
$\mu$ by a permutation of class labels, then there is an isometric isomorphism
of geometric simplicial complexes
$\operatorname{Del}^{\mu^{\prime}}(X)\cong\operatorname{Del}^{\mu}(X)$, which
is the restriction of the ambient isometry.

For our proofs we will also need a condition to ensure that the chromatic
Delaunay mosaic has non-empty interior in $\mathbb{R}^{d+s}$ if $X$ has
sufficiently many points.

######  Example 2.2.

Let $a=(0,0)$, $b=(0,1)$, $c=(1,0)$, and $d=(1,2)$. Then $X=\\{a,b,c,d\\}$
comprises the four corners of a non-rectangular trapezium in $\mathbb{R}^{2}$
with $ab$ parallel to $cd$. Define the colouring
$\mu=\\{\\{a,b\\},\\{c,d\\}\\}$; then one can check that
$\operatorname{Del}^{\mu}(X)$ is a 2-dimensional simplicial complex in
$\mathbb{R}^{3}$.

To avoid situations like the one above, we impose a transversality condition
on the linear subspaces generated by subsets of $X$. The lineality space of
$P\subset X$ is the linear subspace of $\mathbb{R}^{d}$ that passes through
the origin and is parallel to the affine hull of $P$. It is equivalently the
set of linear combinations $\sum_{p\in P}\lambda_{p}p$ of elements in $P$ with
coefficients that sum to zero: $\sum_{p\in P}\lambda_{p}=0$.

######  (GP3).

We say that $X\subset\mathbb{R}^{d}$ satisfies (GP3) if for all $k\geq 0$, all
subsets $P\subset X$ with $|P|\leq d+k+1$, and any partition of $P$ into $k+1$
disjoint non-empty subsets $(P_{0},\ldots,P_{k})$, we have

$\dim\left(\sum_{i=0}^{k}\operatorname{Lin}(P_{i})\right)=\sum_{i=0}^{k}\dim(\operatorname{Lin}(P_{i}))=|P|-k-1.$
(14)

######  Remark 2.3.

Notice that for any partition we have

$\displaystyle\dim\left(\sum_{i=0}^{k}\operatorname{Lin}(P_{i})\right)\leq\sum_{i=0}^{k}\dim(\operatorname{Lin}(P_{i}))\leq|P|-k-1.$

Thus, (GP3) is the assertion that the inequalities in the above expression are
equalities. The first inequality is an equality if and only if
$\sum_{i=0}^{k}\operatorname{Lin}(P_{i})$ is a direct sum, and the second
inequality is an equality if and only if each $P_{i}$ is an affinely
independent set.

######  Example 2.4.

A set of points in $\mathbb{R}^{2}$ satisfies (GP3) if and only if no three
points are collinear and no two lines formed by pairs of points are parallel.

######  Lemma 2.5.

Let $X\subset\mathbb{R}^{d}$ and let $\mu=\\{X_{0},\ldots,X_{s}\\}$ be any
colouring of $X$. Suppose $X$ satisfies (GP3). Then the affine hull of
$X^{\mu}$ has dimension $k=\min(|X|-1,d+s)$.

###### Proof.

We will find set of $k+1$ points in $X^{\mu}$ that are affinely independent.
Choose a subset $P^{\mu}=\\{x_{0}^{\mu},\ldots,x_{k}^{\mu}\\}$ of points in
$X^{\mu}$ that contains a point of every colour, i.e., $P\cap
X_{i}\neq\emptyset$ for each $i\in[s+1]$. Suppose there exist coefficients
$\\{\lambda_{i}\\}_{i=0}^{k}$ such that $\sum_{i=0}^{k}\lambda_{i}=0$ and
$\sum_{i=0}^{k}\lambda_{i}x_{i}^{\mu}=0$. We will show that each
$\lambda_{i}=0$, thereby showing affine independence of $P^{\mu}$.

Now notice that for each $x\in P_{i}$, by construction we have
$x^{\mu}=(x^{T},0,\ldots,0,1,0,\ldots,0)^{T}$ where the unit entry appears in
the $(d+i)$th position. Therefore, we must have
$\sum_{\mu(x_{j})=m}\lambda_{j}=0$ for each $i\in I$. Let
$y_{i}=\sum_{\mu(x_{j})=i}\lambda_{j}x_{j}$; then
$y_{i}\in\operatorname{Lin}(P_{i})$. Now $y_{i}$ is the projection of
$\sum_{\mu(x_{j})=i}\lambda_{j}x_{j}^{\mu}$ to $\mathbb{R}^{d}$ from
$\mathbb{R}^{d+s}$, and hence

$0=\sum_{x_{i}\in P}\lambda_{i}x_{i}^{\mu}\implies\sum_{i\in I}y_{i}=0.$

Since $X$ satisfies (GP3), we have that $y_{i}=0$ for each $i\in I$. Moreover,
(GP3) also implies affine independence of each $P_{j}$, whence it follows that
$\lambda_{i}=0$ for all $i$. This shows that $P^{\mu}$ is an affinely
independent set as desired. ∎

We say that $X$ is in general position if it satisfies (GP2) and (GP3). Our
terminology is justified by the following statement which we prove in Section
A.1: for any $d,n\geq 1$, the space of $d$-dimensional point clouds with $n$
points that are not in general position is contained in a semi-algebraic
subset of $\mathbb{R}^{nd}$ of dimension at most $nd-1$. We note that in
Section 4.1 of [Mon+24], the authors define a notion of ‘chromatic genericity’
that is very similar to our definition for general position. However, our
notion of general position is strictly stronger than chromatic genericity; see
Section A.2 for details.

The previous lemma immediately implies the following.

######  Corollary 2.6.

Suppose $X\subset\mathbb{R}^{d}$ is in general position and $\mu:X\to[s+1]$ is
a colouring of $X$. Then the chromatic Delaunay mosaic
$\operatorname{Del}^{\mu}(X)$ is a pure $k$-dimensional simplicial complex
with $k=\min(|X|-1,d+s)$.

######  Remark 2.7.

If $X$ is in general position and $\mu$ is any colouring of $X$ then $X^{\mu}$
is in general position. If $E$ is any subset of $X$ then $E$ is in general
position.

######  Remark 2.8.

Chromatic Delaunay triangulations retain the functoriality of the chromatic
alpha filtrations, in that whenever $X$ and $Y$ are in general position and
$(X,\mu)\to(Y,\nu)$ is a morphism in $\mathsf{ChrSet}_{d}$ (the category
defined in Remark 2.1), then there is an embedding of
$\operatorname{Del}^{\mu}(X)$ as a subcomplex of
$\operatorname{Del}^{\nu}(Y)$. This is because
$\operatorname{Del}^{\mu}(X)\cong\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$
and
$\operatorname{Del}^{\nu}(Y)\cong\operatorname{\mathcal{A}}_{\infty}^{\nu}(Y)$,
and by Remark 2.1 we know that there is an inclusion
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)\subset\operatorname{\mathcal{A}}_{\infty}^{\nu}(Y)$
induced by the inclusion of $X$ in $Y$. Correspondingly, the embedding of
$\operatorname{Del}^{\mu}(X)$ into $\operatorname{Del}^{\nu}(Y)$ is induced by
the vertex map that sends $x^{\mu}\in X^{\mu}$ to $x^{\nu}\in Y^{\nu}$.

######  Remark 2.9.

Suppose $\mu:X\to[2]$ is a colouring of $X$. By Remark 2.8 there is an
embedding of simplicial complexes
$\iota:\operatorname{Del}(X)\hookrightarrow\operatorname{Del}^{\mu}(X)$
induced by the vertex map $x\mapsto x^{\mu}$. Let
$h:\mathbb{R}^{d+1}\to\mathbb{R}$ be the projection to the last coordinate. It
is straightforward to check that $\iota(\operatorname{Del}(X))$ is the graph
of the piecewise-linear function
$h\circ\iota:\operatorname{Del}(X)\to\mathbb{R}$. See Figure 5 for an example.

More generally suppose $\mu$ and $\nu$ are colourings of $X$ such that $\mu$
is obtained from $\nu$ by merging the last two classes of $\nu$. That is,
$\mu:X\to[s+1]$ and $\nu:X\to[s+2]$, where $\mu(x)=\nu(x)$ if $\nu(x)\leq s$
and $\mu(x)=s$ if $\nu(x)=s+1$. Then by Remark 2.8, there is an embedding
$\iota:\operatorname{Del}^{\mu}(X)\hookrightarrow\operatorname{Del}^{\nu}(X)$
induced by the vertex map $x^{\mu}\mapsto x^{\nu}$. Let $\zeta:X^{\mu}\to[2]$
be the colouring that sends $x^{\mu}$ to $0$ if $\mu(x)=\nu(x)$, and $1$
otherwise. Then $X^{\nu}$ is the chromatic lift $(X^{\mu})^{\zeta}$. It
follows from our discussion of the bicoloured case that
$\iota(\operatorname{Del}^{\mu}(X))$ is the graph of the function
$h\circ\iota:\operatorname{Del}^{\mu}(X)\to\mathbb{R}$ where
$h:\mathbb{R}^{d+s+1}\to\mathbb{R}$ is the projection to the last coordinate.

$v_{3}$$v_{4}$$v_{5}$$v_{0}$$v_{1}$$v_{2}$

(a)

$v_{3}$$v_{4}$$v_{5}$$v_{0}$$v_{1}$$v_{2}$

(b)

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ (c)

$v_{0}^{\mu}$$v_{1}^{\mu}$$v_{2}^{\mu}$$v_{3}^{\mu}$$v_{4}^{\mu}$$v_{5}^{\mu}$
(d)

$v_{0}^{\mu}$$v_{1}^{\mu}$$v_{2}^{\mu}$$v_{3}^{\mu}$$v_{4}^{\mu}$$v_{5}^{\mu}$
(e)

$x$$y$$z$

Figure 5:  Chromatic Delaunay triangulation of a bi-chromatic set
$X\subset\mathbb{R}^{d}$. (a) Voronoi tessellation of $X$. (b) Overlay of
Voronoi tessellations of blue and orange points in $X$. (c) Delaunay
triangulation $\operatorname{Del}(X)$ of $X$. (d) Chromatic Delaunay
triangulation $\operatorname{Del}^{\mu}(X)$ with bicoloured 2- and 3-simplices
left unshaded for clarity. (e) Embedded image $\iota(\operatorname{Del}(X))$
of the Delaunay triangulation in $\operatorname{Del}^{\mu}(X)$, shaded gray.
The 1-simplices of $\operatorname{Del}(X)$ are shown with dashed lines, and
$\iota(\operatorname{Del}(X))$ is the graph of a piecewise-linear function on
$\operatorname{Del}(X)$. For figures (d) and (e) the coordinate axes are shown
for reference at the bottom right.

###  2.6 Chromatic Delaunay–Čech and Chromatic Delaunay–Rips Filtrations

Given a chromatic set $(X,\mu)$, we define the chromatic Delaunay–Čech
filtration as follows:

$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{t}^{\mu}(X)\mathrel{\coloneqq}\operatorname{\check{C}}_{t}(X)\cap\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$
(15)

In other words, the chromatic Delaunay–Čech filtration has the same underlying
simplicial complex as the chromatic alpha filtration, and the simplices are
assigned filtration values from the Čech filtration. By combining (4) and (11)
and noting that
$\operatorname{\check{C}}_{\bullet}(X)=\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X)$
when $\mu$ is the maximal colouring, we see that the chromatic alpha
filtration is a sub-filtration of the chromatic Delaunay–Čech filtration. More
precisely, if $\mathsf{ChrSet}_{d}$ is the category defined in Remark 2.1,
then $\operatorname{\operatorname{Del}\operatorname{\check{C}}}$ is a functor
from $\mathsf{ChrSet}_{d}\times[0,\infty]$ to $\mathsf{SimpComp}$, and if
$(X,\mu)\to(Y,\nu)$ is a morphism in $\mathsf{ChrSet}_{d}$ and $0\leq s\leq
t\leq\infty$ then the following diagram commutes.

${\operatorname{\mathcal{A}}_{s}^{\nu}(Y)}$${\operatorname{\mathcal{A}}_{t}^{\nu}(Y)}$${\operatorname{\mathcal{A}}_{s}^{\mu}(X)}$${\operatorname{\mathcal{A}}_{t}^{\mu}(X)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{s}^{\nu}(Y)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{t}^{\nu}(Y)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{s}^{\mu}(X)}$${\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{t}^{\mu}(X)}$${\operatorname{\check{C}}_{s}(Y)}$${\operatorname{\check{C}}_{t}(Y)}$${\operatorname{\check{C}}_{s}(X)}$${\operatorname{\check{C}}_{t}(X)}$
(16)

We define the chromatic Delaunay–Rips filtration similarly. Recall that the
Vietoris–Rips filtration on $X$, denoted by $\operatorname{VR}_{\bullet}(X)$,
is defined by 111With our convention of including the constant $2$ in the
definition of the Rips filtration, the 1-skeleta of the Rips and Čech
filtrations are isomorphic for Euclidean point clouds.

$\operatorname{VR}_{r}(X)\mathrel{\coloneqq}\\{\sigma\subset X\mid\forall
x,y\in\sigma:\ \|x-y\|\leq 2r\\}.$ (17)

Then the chromatic Delaunay–Rips filtration is given by

$\operatorname{\operatorname{Del}VR}_{t}^{\mu}(X)\mathrel{\coloneqq}\operatorname{VR}_{t}^{\mu}(X)\cap\operatorname{\mathcal{A}}_{\infty}^{\mu}(X).$
(18)

The Vietoris–Rips filtration is related to the Čech filtration by a series of
nested inclusions, and a similar property holds for their chromatic
counterparts as defined here. We will explore this aspect in more detail in
Section 6.

###  2.7 Generalities on Geometric Simplicial Complexes

In this section we define some notions related to geometric realizations of
simplicial complexes. A geometric $k$-simplex $\sigma^{(k)}$ in
$\mathbb{R}^{d+1}$ is a linear embedding of the standard $k$-simplex in
$\mathbb{R}^{d+1}$. We say that a vector
$z\in\mathbb{R}^{d+1}\setminus\\{0\\}$ is transverse to a geometric simplex
$\sigma^{(k)}$ if $z$ is not parallel to the affine hull of any of its
$m$-dimensional faces for $m\leq\min(k,d)$. Note that if $z$ is transverse to
$\sigma^{(k)}$ then $z$ is transverse to every face of $\sigma^{(k)}$, but the
converse is not necessarily true unless $k=d+1$. Now suppose $K$ is a
geometric simplicial complex in $\mathbb{R}^{d+1}$. We say that a non-zero
vector $z\in\mathbb{R}^{d+1}$ is transverse to $K$ if it is transverse to
$\sigma$ whenever $\sigma$ is a maximal simplex in $K$; in other words, if $z$
is not parallel to the affine hull of (the embedding of) any $k$-simplex in
$K$ where $k\leq d$.

Let $\tau^{(d)}<\sigma^{(d+1)}$ be geometric simplices in $\mathbb{R}^{d+1}$,
let $\operatorname{Aff}(\tau)$ be the affine hull of $\tau$ (i.e., the minimal
affine subspace of $\mathbb{R}^{d+1}$ that contains $\tau$), and let $v$ be
the vertex of $\sigma$ opposite to $\tau$. We say that a non-zero vector
$w\in\mathbb{R}^{d+1}$ is an outward-pointing normal vector to $\tau$ with
respect to $\sigma$ if $w\perp\operatorname{Aff}(\tau)$ and $v=x-\lambda w$
for some $x\in\operatorname{Aff}(\tau)$ and $\lambda>0$.

Suppose we are given $z\in\mathbb{R}^{d+1}\setminus\\{0\\}$ and geometric
simplices $\tau^{(d)}<\sigma^{(d+1)}$ in $\mathbb{R}^{d+1}$. We say that
$\tau$ is an upper (resp. lower) face of $\sigma$ with respect to $z$ if some
(and hence any) outward-pointing normal vector $w$ to the face $\tau$
satisfies $\langle w,z\rangle>0$ (resp. $\langle w,z\rangle<0$). If $k<d$ then
we say that $\eta^{(k)}<\sigma^{(d+1)}$ is an upper (resp. lower) face of
$\sigma$ with respect to $z$ if it is the intersection of $d$-dimensional
upper (resp. lower) faces of $\sigma$. When $z$ is implicit we will just use
the terms “upper face” and “lower face” respectively. We will use $\sigma^{*}$
and $\sigma_{*}$ to denote the minimal upper and lower faces of $\sigma$,
respectively. See Figure 6 for an illustration of the terms defined here.

$z$$a$$b$$c$$x$$w$ (a) The vector $w$ is an outward normal to $ac$ with
respect to $abc$ because $w\perp ac$, and $b=x-\lambda w$ for some
$\lambda>0$. Since $\langle w,z\rangle>0$, $ac$ is an upper face for $abc$
with respect to $z$.

$z$$a$$b$$c$$x$$y$ (b) Illustration of Lemma 2.11. Here $ac$ is an upper face
because there exists $\epsilon>0$ such that $\lambda_{x}=(-\epsilon,0)$.
Indeed, $y=x-\epsilon z$ and for any $\lambda\in(-\epsilon,0)$ we have
$(x+\lambda z)\in\operatorname{int}(abc)$.

Figure 6:  A geometric simplex $\sigma=abc$ in $\mathbb{R}^{2}$. The upper
faces of $\sigma$ are $ab,ac$ and $a$, and the only lower face is $bc$. The
minimal upper face is $\sigma^{*}=a$ and the minimal lower face is
$\sigma_{*}=bc$.

######  Remark 2.10.

If $z\in\mathbb{R}^{d+1}\setminus\\{0\\}$ is transverse to $\sigma^{(d+1)}$
then every $d$-dimensional face of $\sigma$ is either an upper or lower face
of $\sigma$ with respect to $z$. However, for $k<d$ there are $k$-dimensional
“side” faces of $\sigma$ which are neither upper nor lower. These are
precisely the faces that each lie in the intersection of both some upper and
lower $d$-dimensional faces simultaneously.

Now let $\sigma^{(d+1)}$ be a geometric simplex in $\mathbb{R}^{d+1}$ and let
$z\in\mathbb{R}^{d+1}\setminus\\{0\\}$ be transverse to $\sigma$. For any
$x\in\mathbb{R}^{d+1}$, if $x+\lambda_{1}z$ and $x+\lambda_{2}z$ are both in
$\sigma$ with $\lambda_{1}\leq\lambda_{2}$, then $x+\lambda z$ is in $\sigma$
for every $\lambda\in[\lambda_{1},\lambda_{2}]$ by convexity of $\sigma$. It
follows that the following set is an open interval:

$\lambda_{x}(\sigma)\mathrel{\coloneqq}\\{\lambda\in\mathbb{R}\mid x+\lambda
z\in\operatorname{int}(\sigma)\\}.$ (19)

It is not hard to see that if $x$ lies on an upper (resp. lower) face of
$\sigma$ (with respect to $z$), then these intervals must be of the form
$(-\epsilon,0)$ (resp. $(0,\epsilon)$). We state this observation as a lemma:

######  Lemma 2.11.

Let $\sigma^{(d+1)}$ be a geometric simplex in $\mathbb{R}^{d+1}$, let
$\tau<\sigma$, and let $z\in\mathbb{R}^{d+1}\setminus\\{0\\}$ be transverse to
$\sigma$. Let $\operatorname{relint}(\tau)$ denote the relative interior of
$\tau$. Then the following are equivalent:

  1. 1.

$\tau$ is an upper (resp. lower) face of $\sigma$.

  2. 2.

There exists $x\in\operatorname{relint}(\tau)$ and $\epsilon>0$ such that
$\lambda_{x}(\sigma)=(-\epsilon,0)$ (resp. $(0,\epsilon)$).

  3. 3.

For every $x\in\operatorname{relint}(\tau)$ there exists $\epsilon>0$ such
that $\lambda_{x}(\sigma)=(-\epsilon,0)$ (resp. $(0,\epsilon)$).

###  2.8 Generalized Discrete Morse Theory

Let $K$ be a simplicial complex. Let $\mathcal{H}(K)$ be the Hasse diagram of
the co-face poset of $K$, that is, the directed graph whose vertices are
simplices in $K$ with a directed edge $\sigma\to\tau$ if
$\sigma^{(p+1)}>\tau^{(p)}$. An interval in $\mathcal{H}(K)$ is a collection
of simplices of $K$ of the form

$[\tau,\sigma]=\\{\eta\in K\mid\tau\leq\eta\leq\sigma\\}.$ (20)

A generalized discrete vector field $V$ is a partition of the vertices of
$\mathcal{H}(K)$ by intervals. If $V$ is a generalized discrete vector field,
then a function $f:K\to\mathbb{R}$ is a generalized discrete Morse function
with generalized discrete Morse gradient $V$ if the following are true:

  1. 1.

$f$ is monotonic on $\mathcal{H}(K)$;

  2. 2.

For any pair $\tau\leq\sigma$, $f(\sigma)=f(\tau)$ if and only if $\sigma$ and
$\tau$ belong to a common interval in $V$.

In this case the singleton intervals in $V$ are called the critical simplices
of $V$ or $f$, and we denote the set of critical simplices by
$\operatorname{Crit}(V)$ or $\operatorname{Crit}(f)$. Under these definitions,
a discrete Morse gradient in the sense of Forman’s original discrete Morse
theory [For98] is nothing but a generalized gradient in which every interval
has at most two simplices. For simplicity, we will use the terms ‘generalized
vector fields’, ‘generalized gradients’, and ‘generalized Morse functions’,
with the implicit understanding that these refer to the discrete setting in
this paper. Generalized gradients are characterized by the following lemma.

######  Lemma 2.12 (Generalised Gradient Acyclicity Lemma).

Let $V$ be a generalized vector field on a simplicial complex $K$. Let
$\mathcal{H}(K)/V$ be the quotient graph induced by the equivalence relation
on $K$ defined by the intervals in $V$. Then $V$ is the generalized gradient
of some generalized Morse function $f$ (not necessarily unique) if and only if
$\mathcal{H}(K)/V$ is a directed acyclic graph.

###### Proof.

If $V$ is the generalized gradient of $f$, then $f$ descends to a well-defined
function on $\mathcal{H}(K)/V$ since it is constant on intervals in $V$.
Furthermore, $f$ is strictly increasing across the edges of
$\mathcal{H}(K)/V$, so $\mathcal{H}(K)/V$ must be acyclic. Conversely, if
$\mathcal{H}(K)/V$ is directed acyclic, let $P$ be the poset defined by the
reachability graph of $\mathcal{H}(K)/V$. Choose a linear extension of $P$,
and for $x\in\mathcal{H}(K)/V$ let $f(x)$ be the height of $x$ in this linear
extension. Then $f$ is a generalized Morse function on $K$ whose generalized
gradient is $V$. ∎

Generalized gradients are primarily useful because they can encode sequences
of elementary simplicial collapses. We have the following proposition [BE16,
Theorem 2.2].

######  Theorem 2.13 (Generalised Gradient Collapsing Theorem).

Let $K$ be a simplicial complex with a subcomplex $L$. Then there is a
simplicial collapse $K\searrow L$ if and only if there is a generalized
gradient $V$ (not necessarily unique) on $K$ such that $K\setminus L$ is a
union of non-critical intervals of $V$.

###### Proof.

The reverse implication is simply Theorem 2.2 in [BE16], and we lay out a
proof here for clarity. The gradient $V$ can be refined to a set $V^{\prime}$
of intervals of length two as follows. For each interval $[\tau,\sigma]$,
choose an arbitrary $x\in\sigma\setminus\tau$ and partition $[\tau,\sigma]$
into pairs $\\{\eta\setminus\\{x\\},\eta\cup\\{x\\}\\}$ for all
$\eta\in[\tau,\sigma]$. The set of pairs thus obtained is a genuine discrete
Morse gradient (i.e., non-generalised) by the Cluster Lemma [Her05, Jon03],
and clearly $\operatorname{Crit}(V)=\operatorname{Crit}(V^{\prime})$. It
follows from the results in [For98] that there is a simplicial collapse
$K\searrow L$, and the pairs in $V^{\prime}$ correspond to the elementary
collapses in the sequence of elementary collapses that define $K\searrow L$.

For the forward implication of the theorem, we induct on the number of
elementary collapses in the collapsing sequence $K\searrow L$. First suppose
$K=L\sqcup\\{\tau,\sigma\\}$. Then it is straightforward to check that
$V=\\{[\tau,\sigma]\\}\cup L$ is a generalized gradient on $K$ with
$\operatorname{Crit}(V)=L$. The result then follows using induction and the
Gradient Composition Lemma [BE16, Lemma 5.2]. ∎

In Forman’s original theory, the restriction of a discrete Morse function to a
subcomplex is also a discrete Morse function [For98, Lemma 4.1]. The following
lemma is the analogue of that result for the generalized case, and the proof
is a straightforward verification.

######  Lemma 2.14 (Generalised Gradient Restriction Lemma).

Let $V$ be a generalized gradient on a simplicial complex $K$ and let $L$ be a
subcomplex of $K$ such that $K\setminus L$ is a union of intervals of $V$.
Then the set of intervals of $V$ contained in $L$ is a generalized gradient on
$L$ which we denote as $V_{L}$, and
$\operatorname{Crit}(V_{L})=\operatorname{Crit}(V)\cap L$.

The following lemma, stated in [BE16], allows us to obtain a common refinement
of a family of generalized gradients.

######  Lemma 2.15 (Sum Refinement Lemma).

Suppose $f:K\to\mathbb{R}$ and $g:L\to\mathbb{R}$ are generalized Morse
functions with generalized gradients $V$ and $W$ respectively. Then $f+g$ is a
generalized Morse function on $K\cap L$ whose generalized gradient is given by

$Z=\\{I\cap J\mid I\in V,J\in W,I\cap J\neq\emptyset\\}.$ (21)

###  2.9 Karush-Kuhn-Tucker Conditions

In Section 4 we will show that the chromatic alpha filtration function is a
generalized discrete Morse function. A key observation is that the filtration
value of each simplex $\sigma\
\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$ is the solution to a convex
optimization problem with affine constraints. Such problems have solutions
that are characterized by the Karush-Kuhn-Tucker (KKT) conditions [Kar39,
KT51], which are a generalization of the method of Lagrange multipliers to
non-smooth convex functions. To state the KKT conditions we need a non-smooth
analogue of the differential of a function. If $f:\mathbb{R}^{d}\to\mathbb{R}$
is a convex function then the sub-differential of $f$ [MN14, Chapter 2] at a
point $x\in\mathbb{R}^{d}$ is the closed convex set $\partial
f(x)\subset\mathbb{R}^{d}$ defined by

$\partial f(x)\mathrel{\coloneqq}\\{v\in\mathbb{R}^{d}\mid f(x+h)\geq
f(x)+\langle v,h\rangle\text{ for all }h\in\mathbb{R}^{d}\\}.$ (22)

If $f$ is a smooth function then its sub-differential coincides with the
ordinary gradient, i.e., $\partial f(x)=\\{\nabla f(x)\\}$ [MN14, Proposition
2.36].

######  Theorem 2.16 (KKT Conditions).

Let $f$ be a convex function on $\mathbb{R}^{d}$, let
$\mathcal{I},\mathcal{J}$ be finite disjoint sets, let
$\mathcal{K}=\mathcal{I}\sqcup\mathcal{J}$, and let
$\\{g_{k}:\mathbb{R}^{d}\to\mathbb{R}\\}_{k\in\mathcal{K}}$ be a set of affine
linear functions. Then $x_{*}$ is a minimum of the following optimization
problem:

$\begin{array}[]{crcll}\textnormal{minimise}&f(x)\\\ \textnormal{subject
to}&g_{i}(x)&\geq&0&\text{ for all }i\in\mathcal{I},\\\ &g_{j}(x)&=&0&\text{
for all }j\in\mathcal{J},\end{array}$

if and only if there exist scalars
$\\{\lambda_{k}\\}_{k\in\mathcal{K}}\subset\mathbb{R}$ such that the following
conditions hold:

Primal feasibility |  $g_{i}(x_{*})\geq 0$ for all $i\in\mathcal{I}$ and $g_{j}(x_{*})=0$ for all $j\in\mathcal{J}$.
---|---
Stationarity |  The zero vector belongs to the set $\partial f(x_{*})+\sum_{k\in\mathcal{K}}\lambda_{k}\partial g_{k}(x_{*})\subset\mathbb{R}^{d}$, where $\partial f$ is the sub-differential of $f$ and $\partial g_{k}$ is the gradient of $g_{k}$.
Dual feasibility |  $\lambda_{i}\leq 0$ for all $i\in\mathcal{I}$.
Complementary slackness |  $\lambda_{i}g_{i}(x_{*})=0$ for all $i\in\mathcal{I}$.

We will also need the following well-known lemma from the theory of convex
sub-differentials [MN14, Theorem 2.93].

######  Lemma 2.17.

Suppose $\\{f_{1},\ldots,f_{m}\\}$ is a set of convex functions on
$\mathbb{R}^{d}$ and $f(x)\mathrel{\coloneqq}\max_{1\leq k\leq m}f_{k}(x)$.
Then $\partial f(x)$ is the convex hull of the union of sub-differentials of
the active functions of $f$ at $x$, i.e.,

$\partial f(x)=\operatorname{Conv}\left\\{\bigcup_{f_{k}(x)=f(x)}\partial
f_{k}(x)\right\\}.$ (23)

##  3 Collapsing the Chromatic Delaunay Triangulation

Throughout this section, we fix a point cloud $X\subset\mathbb{R}^{d}$ in
general position. The main goal of this section is to prove the following
theorem:

######  Theorem 3.1.

Suppose $X\subset\mathbb{R}^{d}$ is in general position, and $\mu$ and $\nu$
are colourings of $X$ such that $\nu$ is a refinement of $\mu$. Then there is
a simplicial collapse
$\operatorname{\mathcal{A}}_{\infty}^{\nu}(X)\searrow\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)$.

We will construct a generalized discrete Morse gradient that induces the
collapse in the theorem. We begin with a series of observations to reformulate
the problem. Since $X$ is in general position, we have isomorphisms
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X)\cong\operatorname{Del}^{\mu}(X)$
and
$\operatorname{\mathcal{A}}_{\infty}^{\nu}(X)\cong\operatorname{Del}^{\nu}(X)$
as abstract simplicial complexes. By Remark 2.8 there is an embedding
$\iota:\operatorname{Del}^{\mu}(X)\hookrightarrow\operatorname{Del}^{\nu}(X)$.
Therefore, it suffices to exhibit a simplicial collapse
$\operatorname{Del}^{\nu}(X)\searrow\iota(\operatorname{Del}^{\mu}(X))$.

Next, we may assume that $\nu$ is an elementary refinement of $\mu$, by which
we mean that $\nu$ is obtained from $\mu$ by splitting up some class. More
precisely if $\mu=\\{X_{0},\ldots,X_{s}\\}$ and
$\nu=\\{X^{\prime}_{0},\ldots,X^{\prime}_{s^{\prime}}\\}$ then we may assume
that $\mu\preceq\nu$ and $s^{\prime}=s+1$. This is because an arbitrary
refinement $\mu\preceq\nu$ can be written as a sequence of elementary
refinements $\mu=\mu_{0}\preceq\ldots\preceq\mu_{k}=\nu$, whereby there is a
sequence of embeddings
$\operatorname{Del}^{\mu}(X)=\operatorname{Del}^{\mu_{0}}(X)\hookrightarrow\ldots\hookrightarrow\operatorname{Del}^{\mu_{k}}(X)=\operatorname{Del}^{\nu}(X)$.
Then the result for elementary refinements applied to this sequence yields the
general result.

Since the chromatic alpha filtration is invariant to a permutation of class
labels, we may also assume that $\nu$ is obtained from $\mu$ by splitting up
specifically the last class. In other words, $X_{i}=X_{i}^{\prime}$ for $i<s$
and $X_{s}=X^{\prime}_{s}\cup X^{\prime}_{s+1}$. Then we are in the situation
of Remark 2.9, wherein the chromatic lift $X^{\nu}=(X^{\mu})^{\zeta}$ for some
colouring $\zeta:X\to\\{0,1\\}$. Using the definition of the chromatic
Delaunay triangulation gives

$\operatorname{Del}^{\nu}(X)=\operatorname{Del}(X^{\nu})=\operatorname{Del}((X^{\mu})^{\zeta})=\operatorname{Del}^{\zeta}(X^{\mu})\quad\text{and}\quad\operatorname{Del}^{\mu}(X)=\operatorname{Del}(X^{\mu}).$
(24)

Therefore, we must show that
$\operatorname{Del}^{\zeta}(X^{\mu})\searrow\iota(\operatorname{Del}(X^{\mu}))$,
for which it suffices to show that
$\operatorname{Del}^{\mu}(X)\searrow\iota(\operatorname{Del}(X))$ whenever
$\mu$ is a bi-colouring of $X$. Put together, these arguments show that
Theorem 3.1 is a corollary of the following special case:

######  Theorem 3.2.

Suppose $X\subset\mathbb{R}^{d}$ is in general position and
$\mu:X\to\\{0,1\\}$ is a bi-colouring of $X$. Then there is a simplicial
collapse $\operatorname{Del}^{\mu}(X)\searrow\iota(\operatorname{Del}(X))$,
where $\iota:\operatorname{Del}(X)\hookrightarrow\operatorname{Del}^{\mu}(X)$
is the embedding described in Remark 2.8.

The rest of the section is devoted to proving Theorem 3.2. We will assume that
$\mu$ is a fixed bi-colouring of $X$.

###  3.1 Construction of Generalized Vector Field Inducing the Collapse

By virtue of the  (Generalised Gradient Collapsing Theorem). (2.13), to prove
Theorem 3.2 it suffices to construct a generalized discrete Morse gradient on
$\operatorname{Del}^{\mu}(X)$ whose critical set is $\operatorname{Del}(X)$.
If $|X|\leq d$ then there is nothing to show since
$\operatorname{Del}^{\mu}(X)\cong\Delta^{|X|-1}\cong\operatorname{Del}(X)$ by
Lemma 2.5. Therefore, we assume without loss of generality that $|X|\geq d+1$.
Then the intuition behind our approach is given in Figure 7.

Figure 7:  Chromatic Delaunay triangulation
$\operatorname{Del}^{\mu}(X)\subset\mathbb{R}^{2}$ for a bi-chromatic set in
$\mathbb{R}$. The dashed line is the embedded image
$\iota(\operatorname{Del}(X))$ of the Delaunay triangulation, and the arrows
indicate the discrete Morse pairings inducing the collapse
$\operatorname{Del}^{\mu}(X)\searrow\iota(\operatorname{Del}(X))$.

In that figure, the 2-simplices can be partitioned into whether they lie above
or below $\iota(\operatorname{Del}(X))$, which is merely a curve in
$\mathbb{R}^{2}$. If a 2-simplex lies above $\iota(\operatorname{Del}(X))$, we
pair it with its uppermost face, and if it lies below
$\iota(\operatorname{Del}(X))$ we pair it with its lowermost face. The set of
pairings constitutes a discrete Morse gradient inducing the desired collapse.
For $d\geq 2$, the uppermost or lowermost face of a $(d+1)$-simplex $\sigma$
might not be $d$-dimensional, and instead of pairings we will consider
arbitrary intervals in the face poset of $\operatorname{Del}^{\mu}(X)$. For
example, in Figure 5, the intervals we will consider are
$[v_{0}v_{1},v_{0}v_{1}v_{2}v_{4}]$, $[v_{0}v_{3}v_{4},v_{0}v_{2}v_{3}v_{4}]$,
$[v_{1}v_{2},v_{1}v_{2}v_{3}v_{5}]$, $[v_{1}v_{2}v_{4},v_{1}v_{2}v_{4}v_{5}]$,
$[v_{2}v_{5},v_{2}v_{3}v_{4}v_{5}]$.

By Remark 2.9, the embedded image $\iota(\operatorname{Del}(X))$ is the graph
of some function $f:\operatorname{Del}(X)\to\mathbb{R}$. Let $\mathcal{U}$ and
$\mathcal{L}$ be the epigraph and hypograph of $f$ respectively, i.e., points
above and below the graph of $f$:

$\displaystyle\mathcal{U}$
$\displaystyle\mathrel{\coloneqq}\\{(x,y)\in\operatorname{Conv}(X)\times\mathbb{R}\mid
y\geq f(x)\\}\subset\mathbb{R}^{d+1},$ (25) $\displaystyle\mathcal{L}$
$\displaystyle\mathrel{\coloneqq}\\{(x,y)\in\operatorname{Conv}(X)\times\mathbb{R}\mid
y\leq f(x)\\}\subset\mathbb{R}^{d+1}.$ (26)

We say that $\sigma\in\operatorname{Del}^{\mu}(X)$ lies above (resp. below)
$\iota(\operatorname{Del}(X))$ in $\operatorname{Del}^{\mu}(X)$ if $\sigma$
intersects the interior of $\mathcal{U}$ (resp. $\mathcal{L}$). Since
$\iota(\operatorname{Del}(X))$ is $d$-dimensional, each $(d+1)$-simplex of
$\operatorname{Del}^{\mu}(X)$ intersects it in a face of dimension at most
$d$, from which it follows that every $(d+1)$-simplex of
$\operatorname{Del}^{\mu}(X)$ is either above or below
$\iota(\operatorname{Del}(X))$ but not both. We wish to have a notion of upper
and lower faces for each $(d+1)$-simplex of $\operatorname{Del}^{\mu}(X)$, for
which we need the following lemma.

######  Lemma 3.3.

The $(d+1)$th basis vector $e_{d+1}\in\mathbb{R}^{d+1}$ is transverse to
$\operatorname{Del}^{\mu}(X)$.

###### Proof.

Suppose $\tau$ is a simplex in $\operatorname{Del}^{\mu}(X)$ that is not
transverse to $e_{d+1}$. Without loss of generality we can assume that $\tau$
is $d$-dimensional. Let $\pi:\mathbb{R}^{d+1}\to\mathbb{R}^{d}$ be the
projection to the first $d$ coordinates. Then $\pi(\operatorname{Aff}(\tau))$
is a $(d-1)$-dimensional subspace of $\mathbb{R}^{d}$, which implies that the
vertices of $\tau$ are an affinely dependent subset of $X$. This contradicts
the fact that $X$ is in general position. ∎

By virtue of Lemma 3.3, for any $\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$
there is a well-defined notion of upper and lower faces of $\sigma$ with
respect to $e_{d+1}$ (see Section 2.7 for our definition of upper and lower
faces). Now we can define our generalized discrete Morse gradient. Recall that
$\sigma^{*}$ and $\sigma_{*}$ are the minimal upper and lower faces of
$\sigma$ respectively. We define $\Sigma^{\prime}$ and $\Sigma$ to be the
following collection of intervals:

$\displaystyle\Sigma^{\prime}$
$\displaystyle=\\{[\sigma^{*},\sigma]\mid\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X),\sigma\subset\mathcal{U}\\}\cup\\{[\sigma_{*},\sigma]\mid\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X),\sigma\subset\mathcal{L}\\},$
(27) $\displaystyle\Sigma$
$\displaystyle=\Sigma^{\prime}\cup\iota(\operatorname{Del}(X)).$ (28)

In other words, whenever $\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$ lies
above (resp. below) $\iota(\operatorname{Del}(X))$ then there is a
corresponding interval in $\Sigma$ comprising all the upper (resp. lower)
faces of $\sigma$.

######  Proposition 3.4.

$\Sigma$ is a generalized discrete Morse vector field on
$\operatorname{Del}^{\mu}(X)$ whose set of singleton intervals is
$\iota(\operatorname{Del}(X))$.

Before proving Proposition 3.4 we need a technical lemma.

######  Lemma 3.5.

If $\tau^{(k)}\in\operatorname{Del}^{\mu}(X)$ lies above (resp. below)
$\iota(\operatorname{Del}(X))$ with $k\leq d$ then there is a unique
$\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$ such that $\tau$ is an upper
(resp. lower) face for $\sigma$ with respect to $e_{d+1}$ and $\sigma$ lies
above (resp. below) $\iota(\operatorname{Del}(X))$.

###### Proof.

We only consider the case where $\tau$ lies above
$\iota(\operatorname{Del}(X))$; the proof for the other case is similar. Let
$\pi:\mathbb{R}^{d+1}\to\mathbb{R}^{d}$ be the projection to the first $d$
coordinates. Consider any point $x\in\tau\cap\operatorname{int}{\mathcal{U}}$,
and let $y=\iota(\pi(x))$. Note $x\neq y$. The line segment $[x,y]$ lies in
$\operatorname{Del}^{\mu}(X)$ by convexity of the latter. By Lemma 3.3 we know
that $e_{d+1}$ is transverse to $\operatorname{Del}^{\mu}(X)$, so no non-
degenerate subsegment of $[x,y]$ can lie in a $d$-simplex. In particular the
subsegment $[x,x-\lambda e_{d+1}]$ must lie in some $\sigma^{(d+1)}$ for
$\lambda>0$ small enough. Then by Lemma 2.11 $\tau$ is an upper face for
$\sigma$. Moreover, $\sigma$ lies above $\iota(\operatorname{Del}(X))$ because
it contains the point $x$ which is in $\operatorname{int}{\mathcal{U}}$. ∎

###### Proof of Proposition 3.4.

We check that (1) the intervals in $\Sigma^{\prime}$ are contained in
$\operatorname{Del}^{\mu}(X)\setminus\iota(\operatorname{Del}(X))$, (2) the
intervals are disjoint, and (3) their union is all of
$\operatorname{Del}^{\mu}(X)\setminus\iota(\operatorname{Del}(X))$.

  1. 1.

If $[\sigma^{*},\sigma]$ is an interval in $\Sigma^{\prime}$, then by
construction $\sigma$ lies above $\iota(\operatorname{Del}(X))$. Any simplex
$\tau$ in $[\sigma^{*},\sigma]$ is an upper face of $\sigma$, and by Lemma
2.11 the relative interior of any upper face of $\sigma$ lies strictly in the
interior of $\mathcal{U}$. Therefore, any $\tau\in[\sigma^{*},\sigma]$ is not
contained in $\iota(\operatorname{Del}(X))$. A similar argument holds for when
$\sigma$ lies below $\iota(\operatorname{Del}(X))$.

  2. 2.

Suppose $\sigma_{1}^{(d+1)}$ and $\sigma_{2}^{(d+1)}$ are distinct simplices
in $\operatorname{Del}^{\mu}(X)$. We must show that the corresponding
intervals in $\Sigma^{\prime}$ are disjoint. First suppose $\sigma_{1}$ and
$\sigma_{2}$ lie above and below $\iota(\operatorname{Del}(X))$ respectively,
so that $[\sigma_{1}^{*},\sigma_{1}]$ and $[(\sigma_{2})_{*},\sigma_{2}]$ are
the corresponding intervals in $\Sigma$. Then $\sigma_{1}\cap\sigma_{2}$ is
either empty, in which case the intervals are disjoint and there is nothing
left to show, or it must be a simplex in $\iota(\operatorname{Del}(X))$. In
the latter case, $\sigma_{1}\cap\sigma_{2}$ cannot belong to the intervals
corresponding to $\sigma_{1}$ and $\sigma_{2}$ due to part (1).

Otherwise, $\sigma_{1}$ and $\sigma_{2}$ both lie above
$\iota(\operatorname{Del}(X))$ (without loss of generality). If
$\tau\in[\sigma_{1}^{*},\sigma_{1}]\cap[\sigma_{2}^{*},\sigma_{2}]$ then
$\tau$ is an upper face for both $\sigma_{1}$ and $\sigma_{2}$. But this is
impossible due to Lemma 2.11 and the fact that $\sigma_{1}$ and $\sigma_{2}$
have disjoint interiors.

  3. 3.

Let $\tau$ be any simplex in
$\operatorname{Del}^{\mu}(X)\setminus\operatorname{Del}(X)$ and without loss
of generality assume that $\tau$ lies above $\iota(\operatorname{Del}(X))$. We
will show that $\tau$ is contained in some interval of $\Sigma^{\prime}$. If
$\dim(\tau)=d+1$ then $\tau\in[\tau^{*},\tau]\in\Sigma^{\prime}$ and we are
done. Therefore, suppose $\dim(\tau)\leq d$. Then Lemma 3.5 implies that there
exists some $\sigma^{(d+1)}$ that lies above $\iota(\operatorname{Del}(X))$
such that $\tau$ is an upper face for $\sigma$. Hence,
$\tau\in[\sigma^{*},\sigma]\in\Sigma^{\prime}$.∎

###  3.2 Proof that the Generalized Vector Field is a Generalized Gradient

The next step is to check that $\Sigma$ is a gradient. Using the notation from
Section 2.8 and the statement of the  (Generalised Gradient Acyclicity Lemma).
(2.12), it suffices to check that
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ is a directed acyclic graph,
where $\mathcal{H}(\operatorname{Del}^{\mu}(X))$ is the Hasse diagram of the
co-face poset of $\operatorname{Del}^{\mu}(X)$. We will do this by
constructing a strictly monotonic real-valued function on
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$. Indeed, such any such
function can be lifted to a generalized discrete Morse function on
$\operatorname{Del}^{\mu}(X)$ whose gradient is $\Sigma$. Intuitively, this
function will describe the “distance” of each simplex from
$\iota(\operatorname{Del}(X))$ in terms of a height function. For the rest of
this section, let $h:\mathbb{R}^{d+1}\to\mathbb{R}$ denote the height function
along the $(d+1)$st coordinate.

A vertex in $\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ can either
correspond to a simplex $\tau$ in $\iota(\operatorname{Del}(X))$, or to an
interval of the form $[\sigma^{*},\sigma]$ or $[\sigma_{*},\sigma]$ in
$\Sigma^{\prime}$. We represent the latter kind of vertex by $[\sigma]$, where
$\sigma$ is the $(d+1)$-dimensional representative of the interval. We will
also write $C(\sigma)$ for the unique circumcentre of $\sigma$. Define
$f:\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma\to\mathbb{R}$ as follows

$f(x)=\begin{cases}\dim(\tau)&x=\tau\in\iota(\operatorname{Del}(X)),\\\
\left(h(C(\sigma))-\frac{1}{2}\right)^{2}+d&x=[\sigma].\end{cases}$ (29)

In the rest of this section we will prove that $f$ is strictly monotonic. We
first make some observations about
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$. There are no edges in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ that point from vertices of
$\mathcal{H}(\operatorname{Del}(X))$ into vertices of the form $[\sigma]$ for
$\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$. This is because
$\operatorname{Del}(X)$ is a subcomplex of $\operatorname{Del}^{\mu}(X)$.
There are also no edges of the form $[\sigma]\to[\sigma^{\prime}]$, if
$\sigma$ and $\sigma^{\prime}$ lie above and below
$\iota(\operatorname{Del}(X))$ respectively (or vice-versa). This is because
such an edge would imply the existence of a shared face $\tau$ that is an
upper face of $\sigma$ and a lower face of $\sigma^{\prime}$. By construction
of $\mathcal{U}$ and $\mathcal{L}$ this would imply that
$\sigma\subset\mathcal{L}$ and $\sigma^{\prime}\subset\mathcal{U}$, a
contradiction. Therefore, we have the following possibilities for the types of
edges in $\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$:

  1. 1.

$\eta\to\tau$ where $\eta,\tau\in\iota(\operatorname{Del}(X))$ and
$\eta>\tau$.

  2. 2.

$[\sigma]\to\tau$ where $\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$ and
$\tau\in\iota(\operatorname{Del}(X))$, with $\sigma>\tau$.

  3. 3.

$[\sigma]\to[\sigma^{\prime}]$ where $\sigma,\sigma^{\prime}$ are
$(d+1)$-simplices in $\operatorname{Del}^{\mu}(X)$ and both lie above or below
$\iota(\operatorname{Del}(X))$.

######  Remark 3.6.

Clearly $f(\eta)>f(\tau)$ whenever $\eta\to\tau$ is an edge of type (1) in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$.

Next we consider edges of type (2) in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))$. If $[\sigma]\to\tau$ is such an
edge, then $f([\sigma])>f(\tau)$ holds automatically if $\dim(\tau)<d$.

######  Lemma 3.7.

Let $\tau\in\operatorname{Del}^{\mu}(X)$. Then
$\tau\in\iota(\operatorname{Del}(X))$ if and only if there is an empty
circumsphere for $\tau$ in $\mathbb{R}^{d+1}$ whose centre $C$ satisfies
$h(C)=\frac{1}{2}$.

###### Proof.

Let $V(\tau)\subset X$ be the set of points whose chromatic lift is the vertex
set of $\tau$, i.e., $V(\tau)^{\mu}=\tau$. By Equation 12 there exists an
empty $[2]$-stack $S$ passing through $V(\tau)$ in $\mathbb{R}^{d}$. By the
correspondence between stacks and spheres, any $[2]$-stack $S$ passing through
$V(\tau)$ lifts to an empty $d$-sphere $S^{\mu}$ passing through $\tau$ in
$\mathbb{R}^{d+1}$. Let $r_{0}(S)$ and $r_{1}(S)$ be the radii of the
$(d-1)$-spheres in $S$ and let $C$ be the centre of $S^{\mu}$. Applying
Pythagoras’ theorem, we get $r_{1}(S)^{2}-r_{0}(S)^{2}=2h(C)-1$ (see Figure
8). Equation 8 implies that $\tau\in\iota(\operatorname{Del}(X))$ if and only
if there is an empty stack $S$ passing through $V(\tau)$ with
$r_{0}(S)=r_{1}(S)$, and by the previous remark this is equivalent to
$h(C)=1/2$. ∎

$r_{1}$$r_{0}$$h$$|1-h|$$R$$R$$C$ Figure 8:  Visual proof of Lemma 3.7. If
$r_{0}=r_{1}$ then $h^{2}=|1-h|^{2}\implies h=\frac{1}{2}$.

######  Lemma 3.8.

Suppose $\sigma^{(d+1)}\subset\mathbb{R}^{d+1}$ is a geometric simplex,
$z\in\mathbb{R}^{d+1}$ is transverse to $\sigma$, and $\tau^{(d)}<\sigma$. Let
$C$ be the circumcentre of $\sigma$, let $C^{\prime}$ be the centre of any
circumsphere of $\tau$ that is empty of $\sigma$, and let
$h_{z}:\mathbb{R}^{d+1}\to\mathbb{R}$ denote the height function along $z$. If
$\tau$ is a lower (resp. upper) face of $\sigma$ with respect to $z$ then
$h_{z}(C)>h_{z}(C^{\prime})$ (resp. $h_{z}(C)<h_{z}(C^{\prime})$).

###### Proof.

$C^{\prime}$ must lie on the set $\ell$ of points equidistant from the
vertices of $\tau$, and since $\tau$ is a $d$-simplex $\ell$ is a line
orthogonal to $\operatorname{Aff}(\tau)$. The circumsphere of $\sigma$ is an
empty circumsphere for $\tau$, so $C$ lies on $\ell$. Let $w$ be the unit
outward normal to $\tau$ with respect to $\sigma$, so that $w$ is parallel to
$\ell$. Then we can write $C^{\prime}=C+tw$ for some $t\in\mathbb{R}$.

First we claim that $t>0$. Let $v_{0}$ be the vertex of $\sigma$ opposite to
$\tau$, and let $v_{1}$ be any vertex of $\tau$. We have

$\displaystyle|C^{\prime}-v_{0}|^{2}-|C^{\prime}-v_{1}|^{2}$
$\displaystyle=\langle 2C^{\prime}-v_{0}-v_{1},v_{1}-v_{0}\rangle$
$\displaystyle=\langle 2C+2tw-v_{0}-v_{1},v_{1}-v_{0}\rangle$
$\displaystyle=|C-v_{0}|^{2}-|C-v_{1}|^{2}+2t\langle w,v_{1}-v_{0}\rangle$
$\displaystyle=2t\langle w,v_{1}-v_{0}\rangle,$

where the fourth equality is because $C$ is a circumsphere for $\sigma$. By
the definition of outward normal, there exists $x\in\operatorname{Aff}(\tau)$
and $\lambda>0$ such that $v_{0}=x-\lambda w$. Then

$\langle w,v_{1}-v_{0}\rangle=\langle w,v_{1}-x+\lambda w\rangle=\lambda$

since $v_{1}-x\in\operatorname{Lin}(\tau)$ and
$w\perp\operatorname{Lin}(\tau)$. Thus,
$|C^{\prime}-v_{0}|^{2}-|C^{\prime}-v_{1}|^{2}=2t\lambda$. This shows that if
$t<0$ then the circumsphere through $\tau$ centred at $C^{\prime}$ contains
$v_{0}$ and cannot be empty.

Now we have

$h_{z}(C)-h_{z}(C^{\prime})=\langle z,C-(C+tw)\rangle=-t\langle z,w\rangle.$

Without loss of generality assume that $\tau$ is a lower face of $\sigma$.
Then by definition $\langle z,w\rangle<0$, and the quantity above is non-
negative with equality if and only if $t=0$. ∎

######  Lemma 3.9.

Let $Y\subset\mathbb{R}^{d+1}$ be in general position, let $z$ be transverse
to $\operatorname{Del}(Y)$, and let
$\sigma_{1}^{(d+1)},\sigma_{2}^{(d+1)}\in\operatorname{Del}(Y)$ intersect in
an upper $d$-dimensional face of $\sigma_{2}$ with respect to $z$. Let $C_{i}$
be the circumcentre of $\sigma_{i}$, and let
$h_{z}:\mathbb{R}^{d+1}\to\mathbb{R}$ denote the height function along the $z$
direction. Then $h_{z}(C_{1})>h_{z}(C_{2})$.

###### Proof.

Since $z$ is transverse to $\sigma_{1}$, the face
$\tau=\sigma_{1}\cap\sigma_{2}$ must be either a lower or upper face of
$\sigma_{1}$. But we are given that $\tau$ is an upper face of $\sigma_{2}$,
and thus by Lemma 2.11 it cannot be an upper face of $\sigma_{1}$. Thus,
$\tau$ is a lower face of $\sigma_{1}$. The circumcentre $C_{2}$ is the centre
of a circumsphere for $\tau$ that is empty of $\sigma_{1}$ because of the
Delaunay condition. Moreover, since $Y$ is in general position, we must have
$C_{2}\neq C_{1}$. Then applying Lemma 3.8 to $\sigma_{1}$ and $\tau$ gives
$h(C_{1})>h(C_{2})$ as desired. ∎

$O$$P$$z$$a$$b$$c$$d$ Figure 9:  Illustration of Lemma 3.9. Here $O$ and $P$
are the circumcentres of $abc$ and $bcd$ respectively, and $bc$ is an upper
face for $abc$.

######  Lemma 3.10.

Suppose $\sigma^{(d+1)}\in\operatorname{Del}^{\mu}(X)$ and $C$ is its
circumcentre. Then $\sigma$ lies above (resp. below)
$\iota(\operatorname{Del}(X))$ if and only if $h(C)>\frac{1}{2}$ (resp.
$h(C)<\frac{1}{2}$).

###### Proof.

It suffices to show that if $\sigma$ lies above $\iota(\operatorname{Del}(X))$
then $h(C)>\frac{1}{2}$ and if $\sigma$ lies below
$\iota(\operatorname{Del}(X))$ then $h(C)<\frac{1}{2}$. The argument for both
cases is similar, so we prove only the former case. Hence, suppose $\sigma$
lies above $\iota(\operatorname{Del}(X))$.

First suppose $\sigma$ has a face $\tau^{(d)}$ that lies in
$\iota(\operatorname{Del}(X))$. Since $\tau$ is in
$\iota(\operatorname{Del}(X))$, Lemma 3.7 shows that there is an empty
circumsphere for $\tau$ with centre $C^{\prime}$ such that
$h(C^{\prime})=\frac{1}{2}$. The proof of Proposition 3.4 shows that any upper
face of $\sigma$ lies in
$\operatorname{Del}^{\mu}(X)\setminus\iota(\operatorname{Del}(X))$, so $\tau$
is necessarily a lower face of $\sigma$. Then $h(C)>h(C^{\prime})=\frac{1}{2}$
by Lemma 3.8.

Now for general $\sigma$: we construct a finite sequence of
$(d+1)$-dimensional simplices $\sigma=\sigma_{0},\sigma_{1},\ldots,\sigma_{k}$
such that $\sigma_{i}\cap\sigma_{i+1}$ is a $d$-dimensional upper face of
$\sigma_{i+1}$ for each $i<k$, and $\sigma_{k}$ has a lower $d$-dimensional
face in $\iota(\operatorname{Del}(X))$. Suppose $\sigma_{i}$ has been chosen.
If $\sigma_{i}$ has a lower $d$-dimensional face on
$\iota(\operatorname{Del}(X))$ set $k=i$. Otherwise, let $\tau_{i}$ be any
lower $d$-dimensional face of $\sigma_{i}$, so $\tau_{i}$ must lie above
$\iota(\operatorname{Del}(X))$. By Lemma 3.5 there exists a unique
$\sigma_{i+1}$ that lies above $\iota(\operatorname{Del}(X))$ for which $\tau$
is an upper face. This sequence is non-repeating because by Lemma 3.9 the
sequence of heights of the circumcentres $h(C(\sigma_{i}))$ is strictly
decreasing in $i$. The sequence terminates because it is non-repeating and
because there are a finite number of simplices in
$\operatorname{Del}^{\mu}(X)$. Having constructed our sequence, we note that
$h(C(\sigma_{k}))>\frac{1}{2}$ by our previous argument, and the result
follows using the monotonicity of $h(C(\sigma_{i}))$. ∎

From Lemma 3.10 and the definition of the function $f$ in Equation 29 we
immediately get the following.

######  Lemma 3.11.

If $f$ is the function defined in Equation 29 then $f([\sigma])>f(\tau)$
whenever $[\sigma]\to\tau$ is an edge of type (2) in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$.

Finally, we consider edges of type (3) in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))$.

######  Lemma 3.12.

Suppose $\sigma,\sigma^{\prime}$ are $(d+1)$-simplices in
$\operatorname{Del}^{\mu}(X)$ that lie above (resp. below)
$\iota(\operatorname{Del}(X))$.

  1. 1.

If there is an edge $[\sigma]\to[\sigma^{\prime}]$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$, then
$\sigma\cap\sigma^{\prime}$ is an upper (resp. lower) face of
$\sigma^{\prime}$.

  2. 2.

If $\sigma\cap\sigma^{\prime}$ is an upper (resp. lower) $d$-dimensional face
of $\sigma^{\prime}$ then there is an edge $[\sigma]\to[\sigma^{\prime}]$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$.

###### Proof.

We consider the case where $\sigma$ and $\sigma^{\prime}$ lie above
$\iota(\operatorname{Del}(X))$; the proof for the other case is similar.

  1. 1.

Suppose there is an edge $[\sigma]\to[\sigma^{\prime}]$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$. Then there are upper faces
$\tau\in[\sigma^{*},\sigma]$ and
$\tau^{\prime}\in[(\sigma^{\prime})^{*},\sigma^{\prime}]$ such that there is
an edge $\tau\to\tau^{\prime}$ in $\mathcal{H}(\operatorname{Del}^{\mu}(X))$,
i.e., $\tau\geq\tau^{\prime}$. Then $\tau^{\prime}$ must be a face of
$\sigma\cap\sigma^{\prime}$, and the latter must therefore also belong to the
interval $[(\sigma^{\prime})^{*},\sigma^{\prime}]$.

  2. 2.

Suppose $\sigma\cap\sigma^{\prime}$ is an upper $d$-dimensional face of
$\sigma^{\prime}$. Then the edge $\sigma\to\sigma\cap\sigma^{\prime}$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))$ descends to an edge
$[\sigma]\to[\sigma^{\prime}]$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$.∎

######  Lemma 3.13.

Suppose $\sigma,\sigma^{\prime}$ are $(d+1)$-simplices in
$\operatorname{Del}^{\mu}(X)$ such that $\sigma$ and $\sigma^{\prime}$ both
lie above (resp. below) $\iota(\operatorname{Del}(X))$ and
$\sigma\cap\sigma^{\prime}$ is an upper (resp. lower) face of
$\sigma^{\prime}$. Then there is a path of $(d+1)$-simplices
$[\sigma]=[\sigma_{1}]\to[\sigma_{2}]\to\ldots\to[\sigma_{k}]=[\sigma^{\prime}]$
in $\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ such that
$\sigma_{i}\cap\sigma_{i+1}$ is $d$-dimensional for each $1\leq i<k-1$.

###### Proof.

We consider the case when $\sigma,\sigma^{\prime}$ lie above
$\iota(\operatorname{Del}(X))$. Consider the star
$V\mathrel{\coloneqq}\operatorname{st}(\sigma\cap\sigma^{\prime})$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$. We claim:

$\text{$\sigma^{\prime}$ is the unique $(d+1)$-simplex in $V$ that has no
lower face in $V$}.$ (30)

Let $\mu$ be any $(d+1)$-simplex in $V$ with no lower face in $V$. This is
equivalent to the property that every $d$-dimensional face of $\mu$ that
contains $\sigma\cap\sigma^{\prime}$ is an upper face of $\mu$, which is
equivalent to the property that $\sigma\cap\sigma^{\prime}$ is an upper face
of $\mu$. This is equivalent to $\mu=\sigma^{\prime}$ because Lemma 2.11
implies that there is a unique $\mu$ for which $\sigma\cap\sigma^{\prime}$ is
an upper face.

We now construct the required path inductively. Begin by setting
$\sigma_{1}=\sigma$ and assume by induction that $\sigma_{i}\in V$. If
$\sigma_{i}=\sigma^{\prime}$ then we are done; otherwise by our previous
remarks we can choose a lower $d$-dimensional face $\tau$ of $\sigma_{i}$ that
is in $V$. Note that $\tau$ cannot be in $\iota(\operatorname{Del}(X))$. This
is because $\tau>\sigma\cap\sigma^{\prime}$, and $\sigma\cap\sigma^{\prime}$
cannot be in $\iota(\operatorname{Del}(X))$ due to Proposition 3.4 and the
fact that $\sigma\cap\sigma^{\prime}$ is an upper face of $\sigma^{\prime}$
which lies above $\iota(\operatorname{Del}(X))$. By Lemma 3.5 there exists a
unique $(d+1)$-dimensional simplex $\sigma_{i+1}$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ for which $\tau$ is an upper
face. Moreover, $\sigma_{i+1}\in V$ because
$\sigma_{i+1}>\tau>\sigma\cap\sigma^{\prime}$. Since $\tau$ is an upper face
of $\sigma_{i+1}$ and $\tau=\sigma_{i}\cap\sigma_{i+1}$, there is an edge
$[\sigma_{i}]\to[\sigma_{i+1}]$ in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ by Lemma 3.12. The sequence
$(\sigma_{i})_{i\geq 1}$ is non-repeating because the sequences of heights of
the circumcentres $h(C(\sigma_{i}))$ is strictly decreasing by Lemma 3.9. The
sequence must terminate in a finite number of steps since it is non-repeating
and $V$ is finite. Furthermore, it must terminate at $\sigma^{\prime}$ by
(30). ∎

######  Lemma 3.14.

The function $f$ defined in Equation 29 satisfies
$f([\sigma])>f([\sigma^{\prime}])$ whenever $[\sigma]\to[\sigma^{\prime}]$ is
an edge of type (3) in $\mathcal{H}(\operatorname{Del}^{\mu}(X))$.

###### Proof.

Let $[\sigma]\to[\sigma^{\prime}]$ be an edge of type (3) in
$\mathcal{H}(\operatorname{Del}^{\mu}(X))$ and without loss of generality
assume $\sigma$ and $\sigma^{\prime}$ lie above
$\iota(\operatorname{Del}(X))$. By Lemma 3.13 there is a path
$[\sigma]=[\sigma_{0}]\to[\sigma_{1}]\to\ldots\to[\sigma_{k}]=[\sigma^{\prime}]$
where each $\sigma_{i}\cap\sigma_{i+1}$ is a $d$-dimensional upper face for
$\sigma_{i+1}$. By Lemma 3.9 the sequence $h(C(\sigma_{i}))$ is strictly
decreasing, and hence $(h(C(\sigma_{i}))-\frac{1}{2})^{2}+d$ is also strictly
decreasing. It follows that $f([\sigma])>f([\sigma^{\prime}])$. ∎

######  Proposition 3.15.

The function $f$ defined in Equation 29 lifts to a generalized discrete Morse
function on $\operatorname{Del}^{\mu}(X)$, whose generalized discrete Morse
gradient is $\Sigma$ as defined in Equation 28.

###### Proof.

Remarks 3.6, 3.11 and 3.14 imply that the function $f$ defined in Equation 29
is strictly monotonic on $\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$.
This means that $\mathcal{H}(\operatorname{Del}^{\mu}(X))/\Sigma$ is a
directed acyclic graph, and Lemma 2.12 implies that $\Sigma$ is a generalized
discrete Morse gradient. Then it is clear that the lift of $f$ to
$\mathcal{H}(\operatorname{Del}^{\mu})$ is still monotonic and its level sets
are exactly $\Sigma$, which shows that the lift is a generalized discrete
Morse function whose gradient is $\Sigma$. ∎

Now since $\operatorname{Crit}(\Sigma)=\operatorname{Del}(X)$ (Proposition
3.4), Theorem 3.2 follows by applying the  (Generalised Gradient Collapsing
Theorem). (2.13) to the Morse gradient $\Sigma$. Finally, Theorem 3.1 follows
from the remarks at the beginning of Section 3.1.

##  4 Morse Theoretic Structure of the Chromatic Alpha Filtration Function

The main goal of this section is to study the Čech and the chromatic alpha
filtration functions. In Section 4.1 we show that these functions are
generalized discrete Morse functions. This fact was already proved in [ALS13]
for the Čech filtration and in [Mon+24] for the chromatic alpha filtration, as
noted in the introduction. However, we will need to study the relationship
between the generalized gradients of these filtration functions (Section 4.2),
for which it is useful to specifically formulate a proof by adapting the
methods in [BE16], from the case of spheres to the case of stacks. In that
paper, the authors define a family of “selective Delaunay filtrations” that
interpolate between the alpha and Čech filtrations, and prove that their
filtration functions all share similar properties. We will generalize their
construction to interpolate between the chromatic alpha and Čech filtrations.
While in [BE16] the intermediate filtrations are interesting objects in their
own right, in our case the intermediate filtrations are largely a notational
convenience for the proofs of this section. Throughout the section
$X\subset\mathbb{R}^{d}$ will denote a fixed point cloud in general position
and $\mu:X\to[s+1]$ will denote a fixed colouring of $X$.

###  4.1 Showing that the Filtration Function is Morse

Recall that for $\gamma\subset[s+1]$ an empty $\gamma$-stack in
$\mathbb{R}^{d}$ comprises a set of concentric $(d-1)$-spheres
$S=(S_{m})_{m\in\gamma}$ such that $S_{m}$ is empty of $X_{m}$. We now
consider a relaxation of the emptiness condition. For a $\gamma$-stack $S$
(not necessarily empty) we define:

$\displaystyle\operatorname{Incl}(S)$
$\displaystyle\mathrel{\coloneqq}\bigcup_{j\in\gamma}\\{x\in
X_{j}\mid\text{$x$ lies on or inside $S_{j}$}\\},$ (31)
$\displaystyle\operatorname{Excl}(S)$
$\displaystyle\mathrel{\coloneqq}\bigcup_{j\in\gamma}\\{x\in
X_{j}\mid\text{$x$ lies on or outside $S_{j}$}\\},$ (32)
$\displaystyle\operatorname{On}(S)$
$\displaystyle\mathrel{\coloneqq}\bigcup_{j\in\gamma}\\{x\in
X_{j}\mid\text{$x$ lies on
$S_{j}$}\\}=\operatorname{Incl}(S)\cap\operatorname{Excl}(S).$ (33)

For $\sigma,E\subset X$, we say $S$ excludes $E$ if
$E\cap\mu^{-1}(\gamma)\subset\operatorname{Excl}(S)$, and we say that $S$
includes $\sigma$ if $\sigma\subset\operatorname{Incl}(S)$. Denoting
$\gamma=\mu(\sigma)$, we will let $S^{\mu}(\sigma,E)$ denote the
$\gamma$-stack of minimum radius that includes $\sigma$ and excludes $E$, if
such a stack exists. Note that if $S^{\mu}(\sigma,E)$ exists, then it is
unique because it is the minimizer of a strictly convex function (see the
proof of Proposition 4.2). With this notation, the empty stack of minimum
radius passing through $\sigma$ is $S^{\mu}(\sigma,X)$.

By Equation 12, a simplex $\sigma$ belongs to the chromatic alpha complex
$\operatorname{\mathcal{A}}_{r}^{\mu}(X)$ if and only if $S^{\mu}(\sigma,X)$
exists and $\operatorname{Rad}(S^{\mu}(\sigma,X))\leq r$. By analogy, for each
$E\subset X$ we can define a filtration on the vertex set $X$ as follows:

$\operatorname{\mathcal{A}}^{\mu}_{r}(X,E)\mathrel{\coloneqq}\\{\sigma\subset
X\mid S^{\mu}(\sigma,E)\text{ exists and
}\operatorname{Rad}(S^{\mu}(\sigma,E))\leq r\\}.$ (34)

From Equations 3 and 8 it is straightforward that
$\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X,\emptyset)=\operatorname{\check{C}}_{\bullet}(X)$
and
$\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X,X)=\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X)$.

######  Remark 4.1.

In the monochromatic case, $\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X,E)$
is the so-called “selective Delaunay filtration” defined in [BE16].

Next we use the  (KKT Conditions). (2.16) to characterize the stacks
$S^{\mu}(\sigma,E)$. For $\gamma\subset[s+1]$ and a stack
$S=(S_{m})_{m\in\gamma}$, we let $\operatorname{Out}(S)$ be the set of “outer”
colours of $S$, i.e.,

$\operatorname{Out}(S)\mathrel{\coloneqq}\\{m\in\gamma\mid\operatorname{Rad}(S_{m})=\operatorname{Rad}(S)\\}.$
(35)

######  Proposition 4.2 (KKT Conditions for Stacks).

Let $E,\sigma\subset X$ with $\mu(\sigma)=\gamma\subset[s+1]$, and let
$S=(S_{m})_{m\in\gamma}$ be a stack that includes $\sigma$ and excludes $E$.
Suppose $S$ is centred on $y\in\mathbb{R}^{d}$ and its spheres have radii
$(r_{m})_{m\in\gamma}$. Let $\gamma^{\prime}=\operatorname{Out}(S)$. Then
$S=S^{\mu}(\sigma,E)$ if and only if there exists a set of real numbers
$\\{\lambda_{v}\\}_{v\in\operatorname{On}(S)}$ such that

  1. 1.

$\sum_{v\in\operatorname{On}(S)}\lambda_{v}v=y$.

  2. 2.

$\\{v\in\operatorname{On}(S)\mid\lambda_{v}>0\\}\subset\sigma$.

  3. 3.

$\\{v\in\operatorname{On}(S)\mid\lambda_{v}<0\\}\subset E$.

  4. 4.

$\sum_{v\in\operatorname{On}(S_{m})}\lambda_{v}=0$ for all
$m\notin\gamma^{\prime}$.

  5. 5.

$\sum_{v\in\operatorname{On}(S_{m})}\lambda_{v}\geq 0$ for all
$m\in\gamma^{\prime}$.

  6. 6.

$\sum_{m\in\gamma^{\prime}}\sum_{v\in\operatorname{On}(S_{m})}\lambda_{v}=1$.

In this case, the coefficients $\lambda_{v}$ are unique.

###### Proof.

To simplify notation assume that $\gamma=[\ell+1]=\\{0,\ldots,\ell\\}$, where
$\ell\leq s$. First we will prove the forward direction, so suppose
$S=S^{\mu}(\sigma,E)$. For $v\in\mu^{-1}(\gamma)$ define

$\displaystyle g_{v}:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}$
$\displaystyle\to\mathbb{R},$ $\displaystyle
f:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}$ $\displaystyle\to\mathbb{R},$
$\displaystyle(z,w_{0},\ldots,w_{\ell})$
$\displaystyle\mapsto\|v-z\|^{2}-w_{\mu(v)}^{2},$
$\displaystyle(z,w_{0},\ldots,w_{\ell})$ $\displaystyle\mapsto\max_{0\leq
i\leq\ell}w_{i}^{2}.$

Then $S$, which is defined by its centre $y$ and radii $(r_{m})_{m\in\gamma}$,
is given by the solution to the following optimization problem:

$\begin{array}[]{rrcll}\textnormal{minimise}&f(z,w_{0},\ldots,w_{\ell})\\\
\textnormal{subject to}&g_{v}(z,w_{0},\ldots,w_{\ell})&\geq&0&\textnormal{for
all }v\in E\cap\mu^{-1}(\gamma),\\\
&g_{v}(z,w_{0},\ldots,w_{\ell})&\leq&0&\textnormal{for all }v\in\sigma.\\\
\end{array}$ (36)

We can reformulate this optimization problem using affine constraints in order
to apply the KKT conditions. Notice that

$\|v-z\|^{2}-w_{\mu(v)}^{2}=\|v\|^{2}+\|z\|^{2}-2\langle z,v\rangle-
w_{\mu(v)}^{2}.$

Define the change of variables
$T:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}\to\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}$
by

$T(z,w_{0},\ldots,w_{\ell})=(z,\|z\|^{2}-w_{0}^{2},\ldots,\|z\|^{2}-w_{\ell}^{2}).$

Under this change of variable, we have $f=\tilde{f}T$ where
$\tilde{f}:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}\to\mathbb{R}$ is defined by

$\tilde{f}(z,u_{0},\ldots,u_{\ell})=\max_{0\leq i\leq\ell}\|z\|^{2}-u_{i}.$

We also have $g_{v}=\tilde{g}_{v}T$ where
$\tilde{g}_{v}:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}\to\mathbb{R}$ is
defined by

$\tilde{g}_{v}(z,u_{0},\ldots,u_{\ell})=\|v\|^{2}+u_{\mu(v)}-2\langle
z,v\rangle.$

Now let $E_{\gamma}\mathrel{\coloneqq}E\cap\mu^{-1}(\gamma)$ and consider the
following optimization problem

$\begin{array}[]{rrcl}\textnormal{minimise}&\tilde{f}(z,u_{0},\ldots,u_{\ell})\\\
\textnormal{subject to}&\tilde{g}_{v}(z,u_{0},\ldots,u_{\ell})&\geq
0&\textnormal{for all }v\in E_{\gamma}\setminus\sigma,\\\
&\tilde{g}_{v}(z,u_{0},\ldots,u_{\ell})&=0&\textnormal{for all }v\in\sigma\cap
E_{\gamma},\\\ &\tilde{g}_{v}(z,u_{0},\ldots,u_{\ell})&\leq 0&\textnormal{for
all }v\in\sigma\setminus E_{\gamma}.\\\ \end{array}$ (37)

Every solution $(z,w_{0},\ldots,w_{\ell})$ to (36) yields a solution
$T(z,w_{0},\ldots,w_{\ell})=(z,u_{0},\ldots,u_{\ell})$ to (37). Conversely,
every solution $(z,u_{0},\ldots,u_{\ell})$ to (37) yields a set of solutions
$T^{-1}(z,u_{0},\ldots,u_{\ell})$ to (36), of which there is a unique solution
that satisfies $w_{i}\geq 0$ for all $0\leq i\leq\ell$. By assumption
$S=S^{\mu}(\sigma,E)$ so $(y,r_{0},\ldots,r_{\ell})$ is a solution to (36).
Therefore,
$T(y,r_{0},\ldots,r_{\ell})\mathrel{\eqqcolon}(y,t_{0},\ldots,t_{\ell})$ is a
solution to (37). Applying the  (KKT Conditions). (2.16), there must exist
coefficients $\lambda_{v}$ for $v\in E_{\gamma}\cup\sigma$ such that

  1. 1.

(Primal feasibility) The constraints in (37) hold.

  2. 2.

(Stationarity) $0\in\sum_{v\in
E_{\gamma}\cup\sigma}\lambda_{v}\nabla\tilde{g}_{v}(y,t_{0},\ldots,t_{\ell})+\partial\tilde{f}(y,t_{0},\ldots,t_{\ell})$,
where $\partial\tilde{f}$ is the sub-differential of $\tilde{f}$.

  3. 3.

(Dual feasibility) $\lambda_{v}\leq 0$ for all $v\in
E_{\gamma}\setminus\sigma$ and $\lambda_{v}\geq 0$ for all
$v\in\sigma\setminus E_{\gamma}$.

  4. 4.

(Complementary slackness) $\lambda_{v}\tilde{g}_{v}(y,t_{0},\dots,t_{l})=0$
for all $v\in E_{\gamma}\cup\sigma$.

The complementary slackness condition states that $\lambda_{v}=0$ if the
constraint for $v$ is not satisfied strictly; that is,
$v\notin\operatorname{On}(S)$. Therefore, we may as well index the
coefficients $\lambda_{v}$ by the index set $\operatorname{On}(S)$, setting
$\lambda_{v}=0$ for $v\in(E_{\gamma}\cup\sigma)\setminus\operatorname{On}(S)$.
Furthermore, note that $E\cap\operatorname{On}(S)\subset E_{\gamma}$, since by
definition $S$ contains spheres indexed by colours in $\gamma$. Therefore, the
dual feasibility condition above implies conditions (2) and (3) of the
proposition.

Next we come to the stationarity condition. We have

$\partial\tilde{g}_{v}(y,t_{0},\ldots,t_{\ell})=(-2v,0,\ldots,0,1,0,\ldots,0)^{T}\in\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}$

where $1$ is in the $(d+\mu(v)+1)$th position. For ease of notation, we
identify $\mathbb{R}^{d}$ with the first $d$ coordinates of
$\mathbb{R}^{d+\ell+1}$, so we can write

$\displaystyle\partial\tilde{g}_{v}(y,t_{0},\ldots,t_{\ell})=-2v+e_{d+\mu(v)+1},$

where $e_{j}$ is the $j$th standard basis vector. On the other hand, to
compute the sub-differential of $\tilde{f}$ we use Lemma 2.17 to get

$\partial\tilde{f}(y,t_{0},\ldots,t_{\ell})=\operatorname{Conv}\\{(2y-e_{d+i+1})^{T}\mid
i\in\gamma^{\prime}\\}.$

The stationarity condition can then be restated as follows: there exist
coefficients $\mu_{i}\geq 0$ for $i\in\gamma^{\prime}$ such that
$\sum_{i\in\gamma^{\prime}}\mu_{i}=1$ and

$\sum_{v\in\operatorname{On}(S)}\lambda_{v}(2v-e_{d+\mu(v)+1})=\sum_{i\in\gamma^{\prime}}\mu_{i}(2y-e_{d+i+1}).$
(38)

By considering the first $d$ coordinates in the above equation, we get
condition (1) of the proposition. By considering the $(d+i+1)$th coordinate
entries for each $i\notin\gamma^{\prime}$, we see that
$\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}=0$, which is condition (4) of
the proposition. By considering the $(d+i+1)$th coordinate entries for each
$i\in\gamma^{\prime}$ we see that
$\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}=\mu_{i}\geq 0$, which is
condition (5) of the proposition. Finally, we see
$\sum_{i\in\gamma^{\prime}}\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}=\sum_{i\in\gamma^{\prime}}\mu_{i}=1$,
which proves condition (6) of the proposition.

Next we consider the backwards direction of the proposition. Therefore,
suppose we are given coefficients
$\\{\lambda_{v}\\}_{v\in\operatorname{On}(S)}$ that satisfy conditions (1)–(6)
of the proposition. Set $\lambda_{v}=0$ for
$v\in(E_{\gamma}\cup\sigma)\setminus\operatorname{On}(S)$. We will check that
the set of coefficients thus obtained satisfies the KKT conditions stated
above for the optimization problem in (37). First note that by assumption
$\sigma\subset\operatorname{Incl}(S)$ and $E\subset\operatorname{Excl}(S)$, so
the primary feasibility condition is satisfied. By setting $\lambda_{v}=0$ for
$v\in(E_{\gamma}\cup\sigma)\setminus\operatorname{On}(S)$ we force the
complementary slackness condition to hold. Conditions (2) and (3) of the
proposition imply that the dual feasibility condition holds. For
$i\in\gamma^{\prime}$ let
$\mu_{i}=\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}$. Then conditions (5)
and (6) of the proposition imply that each $\mu_{i}$ is non-negative and
$\sum_{i\in\gamma^{\prime}}\mu_{i}=1$. In conjunction with conditions (1) and
(4) of the proposition, we see that the following equation holds:

$\sum_{v\in\operatorname{On}(S)}\lambda_{v}(v+e_{d+\mu(v)+1})=y+\sum_{i\in\gamma^{\prime}}\mu_{i}e_{d+i+1}=\sum_{i\in\gamma^{\prime}}\mu_{i}(y+e_{d+i+1}).$
(39)

After applying an appropriate invertible linear transformation to both sides
of this equation, we are left with Equation 38 which shows that the
stationarity condition holds. The upshot is that $S$ defines a solution to the
optimization problem in (37), and by our previous arguments it also defines a
solution to the original problem in (36).

It remains to show uniqueness of the coefficients $\lambda_{v}$ that satisfy
the conditions of our proposition. Without loss of generality assume that
$\gamma^{\prime}=\\{k,\ldots,\ell\\}$ for some $k\geq 0$. Consider the linear
map
$L:\mathbb{R}^{d}\times\mathbb{R}^{\ell+1}\to\mathbb{R}^{d}\times\mathbb{R}^{k+1}$
defined on basis vectors by

$\displaystyle L(e_{j})=\begin{cases}e_{j}&j\leq d+k+1,\\\
e_{d+k+1}&\text{else}.\end{cases}$

This linear map is identity on the first $d+k$ coordinates and sums up the
remaining coordinates into the $(d+k+1)$th coordinate. Applying $L$ to
Equation 39, we get

$\sum_{i=0}^{k-1}\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}(v+e_{d+\mu(v)+1})+\sum_{i=k}^{\ell}\sum_{v\in\operatorname{On}(S_{i})}\lambda_{v}(v+e_{d+k+1})=y+e_{d+k+1}.$
(40)

Consider the colouring $\nu$ of $\sigma$ obtained from $\mu$ by merging the
colours $\\{k,\ldots,\ell\\}$. The vectors appearing on the LHS of Equation 40
are the points in the chromatic lift of $\operatorname{On}(S)$ with respect to
$\nu$, up to rescaling and translation. Since any subset of $X$ is also in
general position (Remark 2.7), $\operatorname{On}(S)$ is in general position.
Then by (GP2) we must have that $|\operatorname{On}(S)|\leq d+k+1$, and by
Lemma 2.5 $\operatorname{On}(S)$ is affinely independent. Since the sum of all
coefficients appearing on the LHS of Equation 40 is one, we see that the RHS
is in the affine span of an affine independent set, and therefore the
corresponding affine coefficients must be unique. ∎

Although the conditions of Proposition 4.2 are technical, they have a
straightforward combinatorial formulation. Suppose $\sigma,E\subset X$ are
such that $S=S^{\mu}(\sigma,E)$ exists. Then, denoting the coefficients from
Proposition 4.2 by $\\{\lambda_{v}\\}_{v\in\operatorname{On}(S)}$,
define222Our terminology is borrowed from [BE16].

$\displaystyle\operatorname{Front}(S)$
$\displaystyle\mathrel{\coloneqq}\\{v\in\operatorname{On}(S)\mid\lambda_{v}>0\\},$
(41) $\displaystyle\operatorname{Back}(S)$
$\displaystyle\mathrel{\coloneqq}\\{v\in\operatorname{On}(S)\mid\lambda_{v}<0\\}.$
(42)

######  Proposition 4.3 (Combinatorial KKT Conditions for Stacks).

Let $E,\sigma\subset X$ and let $S=(S_{m})_{m\in\gamma}$ be a stack in
$\mathbb{R}^{d}$ such that $\sigma\subset\operatorname{Incl}(S)$ and
$E\subset\operatorname{Excl}(S)$. Then $S=S^{\mu}(\sigma,E)$ if and only if
$\mu(\sigma)=\gamma$ and the following are true:

  1. 1.

$S$ is the stack (not necessarily empty) of minimum radius passing through
$\operatorname{On}(S)$.

  2. 2.

$\operatorname{Front}(S)\subset\sigma$.

  3. 3.

$\operatorname{Back}(S)\subset E$.

###### Proof.

The stack of minimum radius passing through $\operatorname{On}(S)$ is nothing
but $S^{\mu}(\operatorname{On}(S),\operatorname{On}(S))$. If
$S=S^{\mu}(\operatorname{On}(S),\operatorname{On}(S))$ or
$S=S^{\mu}(\sigma,E)$, then $\operatorname{Front}(S)$ and
$\operatorname{Back}(S)$ are well-defined, and the coefficients thereby
obtained from Proposition 4.2 satisfy conditions (1) and (4)–(6) of that
proposition, which do not depend on $E$ and $\sigma$. Then conditions (2) and
(3) of Proposition 4.2 are equivalent to
$\operatorname{Front}(S)\subset\sigma$ and $\operatorname{Back}(S)\subset E$.
∎

We can now show that the filtration function $\operatorname{Rad}_{E}^{\mu}$ of
the filtration $\operatorname{Del}^{\mu}_{\bullet}(X,E)$ is a generalized
discrete Morse function. Recall from Section 2.8 that it suffices to prove
that the level sets of $\operatorname{Rad}^{\mu}_{E}$ are intervals in the
face poset of $\operatorname{Del}^{\mu}_{\infty}(X,E)$. We proceed to describe
the level sets. Suppose $E\subset X$, $\gamma,\zeta\subset[s+1]$ and
$S=(S_{m})_{m\in\gamma}$ and $T=(T_{n})_{n\in\zeta}$ are stacks that are empty
of $E$. We say that $T$ extends $S$ and write $S\preceq T$ if
$\gamma\subset\zeta$, $\operatorname{Rad}(T)=\operatorname{Rad}(S)$, and
$S_{m}=T_{m}$ for each $m\in\gamma$. In other words, $S\preceq T$ if and only
if $T$ is obtained from $S$ by adding spheres, indexed by colours other than
those of $S$, without changing the outer radius of the stack. This defines a
partial ordering on stacks that are empty of $E$, and we define the $S^{*}$ to
be the maximal stack with respect to this partial ordering that extends $S$
and is empty of $E$. We claim that the level sets of
$\operatorname{Rad}_{E}^{\mu}$ have the form
$[\operatorname{Front}(S),\operatorname{Incl}(S^{*})]$ as $S$ ranges over the
stacks $S^{\mu}(\sigma,E)$ for
$\sigma\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,E)$.

######  Lemma 4.4.

Let $S=S^{\mu}(\sigma,E)$ for some $\sigma,E\subset X$. If
$\tau\in[\operatorname{Front}(S),\operatorname{Incl}(S^{*})]$ then

  1. 1.

$\operatorname{Rad}^{\mu}_{E}(\tau)=\operatorname{Rad}^{\mu}_{E}(\sigma)$.

  2. 2.

$S^{\mu}(\tau,E)\preceq S^{*}$.

  3. 3.

$\operatorname{Front}(S^{\mu}(\tau,E))=\operatorname{Front}(S)$ and
$\operatorname{Incl}(S^{\mu}(\tau,E)^{*})=\operatorname{Incl}(S^{*})$.

###### Proof.

Let $\gamma=\mu(\sigma)$, let $S=(S_{m})_{m\in\gamma}$, and define
$J\mathrel{\coloneqq}\\{j\in\gamma\mid\operatorname{Front}(S)\cap\operatorname{On}(S_{j})\neq\emptyset\\}$.
Let $S_{J}$ be the stack whose set of spheres is $\\{S_{j}\mid j\in J\\}$.
Then $S_{J}$ passes through $\operatorname{Front}(S)$ and excludes $E$. Note
that $J$ contains at least one of the colours in $\operatorname{Out}(S)$
because of conditions (5) and (6) of Proposition 4.2, so
$\operatorname{Rad}(S_{J})=\operatorname{Rad}(S)$ and $S_{J}\preceq S$. Let
$S^{\prime}$ be the stack obtained by restricting $S^{*}$ to the spheres that
include vertices of $\tau$, so $S^{\prime}\preceq S^{*}$. Since
$\tau\in[\operatorname{Front}(S),\operatorname{Incl}(S^{*})]$, by definition
of $J$ we must have $S_{J}\preceq S^{\prime}\preceq S^{*}$. In particular
$\operatorname{Rad}(S_{J})=\operatorname{Rad}(S^{\prime})=\operatorname{Rad}(S^{*})$.
We will show that $S^{\prime}=S^{\mu}(\tau,E)$,
$\operatorname{Front}(S^{\prime})=\operatorname{Front}(S)$, and
$\operatorname{Back}(S^{\prime})=\operatorname{Back}(S)$.

Let $\\{\lambda_{v}\mid v\in\operatorname{On}(S)\\}$ be the set of
coefficients obtained from Proposition 4.2 for $\sigma$ and $S$. We claim that
$\lambda_{v}=0$ for each
$v\in\operatorname{On}(S)\setminus\operatorname{On}(S_{J})$. To see this, let
$j\in\gamma$ and let $S_{j}$ pass through some point in
$\operatorname{Back}(S)$. Then conditions (4) and (5) of Proposition 4.2 imply
that $S_{j}$ must also pass through some point of $\operatorname{Front}(S)$.
Now define coefficients $\\{\lambda^{\prime}_{v}\mid
v\in\operatorname{On}(S^{\prime})\\}$ by setting
$\lambda^{\prime}_{v}=\lambda_{v}$ if $v\in\operatorname{On}(S_{J})$, and $0$
otherwise. The fact that $\lambda_{v}=0$ for
$v\not\in\operatorname{On}(S_{J})$ implies that the coefficients
$\\{\lambda_{v}^{\prime}\\}_{v\in\operatorname{On}(S^{\prime})}$ satisfy the
(KKT Conditions for Stacks). (4.2) for $S^{\prime}$ and
$\operatorname{On}(S^{\prime})$, which shows that $S^{\prime}$ is the stack of
minimum radius passing through $\operatorname{On}(S^{\prime})$. By
construction of $\\{\lambda_{v}^{\prime}\mid
v\in\operatorname{On}(S^{\prime})\\}$, we have
$\operatorname{Front}(S^{\prime})=\operatorname{Front}(S)$ and
$\operatorname{Back}(S^{\prime})=\operatorname{Back}(S)$. Then
$S^{\prime}=S^{\mu}(\tau,E)$ by the  (Combinatorial KKT Conditions for
Stacks). (4.3). ∎

######  Lemma 4.5.

Let $\tau\leq\sigma$ be simplices in
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,E)$. If
$\operatorname{Rad}_{E}^{\mu}(\tau)=\operatorname{Rad}^{\mu}_{E}(\sigma)$ then
$\tau$ contains $\operatorname{Front}(S^{\mu}(\sigma,E))$.

###### Proof.

Let $T$ be the stack obtained from $S^{\mu}(\sigma,E)$ by restricting to the
spheres that include vertices of $\tau$. Then
$\operatorname{Rad}(T)\leq\operatorname{Rad}_{E}^{\mu}(\sigma)=\operatorname{Rad}_{E}^{\mu}(\tau)\leq\operatorname{Rad}(T)$,
so $\operatorname{Rad}(T)=\operatorname{Rad}^{\mu}_{E}(\tau)$. Then
$T=S^{\mu}(\tau,E)$ by uniqueness of the latter.

Let $\\{\lambda_{v}\\}_{v\in\operatorname{On}(S^{\prime})}$ and
$\\{\lambda^{\prime}_{v}\\}_{v\in\operatorname{On}(S^{\prime})}$ be the
coefficients that appear in Proposition 4.2 for the minimizing stacks
$S=S^{\mu}(\sigma,E)$ and $S^{\prime}=S^{\mu}(\tau,E)$ respectively. Setting
$\lambda^{\prime}_{v}=0$ for all
$v\in\operatorname{On}(S)\setminus\operatorname{On}(S^{\prime})$, we see that
the set of coefficients
$\\{\lambda^{\prime}_{v}\\}_{v\in\operatorname{On}(S)}$ satisfies the
requirements of Proposition 4.2 for $\sigma$ and $S$, so
$\lambda_{v}=\lambda^{\prime}_{v}$ for all $v\in\operatorname{On}(S)$ by the
uniqueness assertion in that proposition. Then condition (2) in the
(Combinatorial KKT Conditions for Stacks). (4.3) implies that
$\operatorname{Front}(S)\subset\tau$. ∎

We arrive at the main result for this section, which is a generalization of
Theorem 4.6 in [Mon+24].

######  Theorem 4.6 (Selective Chromatic Delaunay Radius is Morse).

Suppose $X\subset\mathbb{R}^{d}$ is in general position, $\mu$ is a colouring
of $X$, and $E\subset X$. Then the filtration function
$\operatorname{Rad}_{E}^{\mu}:\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,E)\to[0,\infty)$
is a generalized discrete Morse function, with gradient given by

$\Sigma=\\{[\operatorname{Front}(S),\operatorname{Incl}(S^{*})]\mid\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,E),S=S^{\mu}(\sigma,E)\\}.$
(43)

Moreover, $\sigma\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,E)$ is a
critical simplex of $\operatorname{Rad}_{E}^{\mu}$ if and only if
$\sigma\in\operatorname{Del}(X)$ and the centre of the empty circumsphere of
minimum radius for $\sigma$ in $\mathbb{R}^{d}$ is contained in the relative
interior of $|\sigma|$ in $\mathbb{R}^{d}$.

###### Proof.

The first part of the theorem is a direct corollary of Lemmas 4.4 and 4.5. For
the second part, let $\sigma$ be a critical simplex of
$\operatorname{Rad}^{\mu}_{E}$ and let $S=S^{\mu}(\sigma,E)$. Then by the
definition of a critical simplex we have

$\operatorname{Front}(S)=\operatorname{Incl}(S^{*})=\sigma,\
\operatorname{Back}(S)=\emptyset$

From this we infer that
$\operatorname{Incl}(S^{*})\setminus\operatorname{On}(S)$ is empty, i.e.,
$S=S^{*}$ is an empty stack. We also conclude that
$\sum_{v\in\operatorname{On}(S_{m})}\lambda_{v}>0$ for all $m\in\mu(\sigma)$.
Using condition (4) of the  (KKT Conditions for Stacks). (4.2), this implies
$\mu(\operatorname{On}(S))=\operatorname{Out}(S)$, i.e., all spheres of $S$
have the same radius. This means that $S$ is an empty sphere passing through
the points of $\sigma$, i.e., $\sigma\in\operatorname{Del}(X)$. Moreover, the
conditions (1), (5), and (6) of the  (KKT Conditions for Stacks). (4.2) along
with the fact that $\operatorname{Front}(S)=\sigma$ together imply that the
centre of $S$ lies in the relative interior of the convex hull of the vertices
of $\sigma$. It only remains to check that $S$ is the minimum empty
circumsphere passing through $\sigma$, and this follows from the fact that
every empty circumsphere for $\sigma$ is also a stack that includes $\sigma$
and excludes $E$. ∎

From the above theorem we recover the fact the filtration function of the Čech
and chromatic alpha filtrations are generalized discrete Morse functions.

######  Corollary 4.7.

Suppose $X\subset\mathbb{R}^{d}$ is in general position and $\mu$ is a
colouring of $X$. Then the filtration functions of
$\operatorname{\check{C}}_{\bullet}(X)$ and
$\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X)$ are generalized discrete Morse
functions.

###### Proof.

For $\operatorname{\check{C}}_{\bullet}(X)$ and
$\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X)$ this follows from Theorem 4.6
and the fact that
$\operatorname{\check{C}}_{\bullet}(X)=\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X,\emptyset)$
and
$\operatorname{\mathcal{A}}^{\mu}_{\bullet}(X)=\operatorname{\mathcal{A}}_{\bullet}^{\mu}(X,X)$.
∎

###  4.2 Pairing Lemmas

The goal of this subsection is to prove three key technical lemmas, which are
needed for the proofs of Theorems A and B, that relate the Morse gradients of
the chromatic alpha and Čech filtrations. These lemmas are direct
generalizations of Lemmas 5.4, 5.5, and 5.7 in [BE16], and the proofs are very
similar. As in that paper, we will write $\sigma+x$ for $\sigma\cup\\{x\\}$
and $\sigma-x$ for $\sigma\setminus\\{x\\}$, and we note that at least one of
$\sigma\pm x$ is equal to $\sigma$. We continue to let
$X\subset\mathbb{R}^{d}$ be a fixed point cloud in general position and $\mu$
be a fixed colouring of $X$.

######  Lemma 4.8 (Same Stacks Lemma).

Let $E\subset X$, $\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,E)$,
and $S=S^{\mu}(\sigma,E)$. For any $x\in X$ we have:

  1. 1.

$S^{\mu}(\sigma-x,E)\preceq S\preceq S^{\mu}(\sigma+x,E)$ if and only if
$x\in\operatorname{Incl}(S^{*})\setminus\operatorname{Front}(S)$.
Additionally, $S=S^{\mu}(\sigma+x,E)$ if and only if
$\mu(\sigma+x)=\mu(\sigma)$ and $S=S^{\mu}(\sigma-x,E)$ if and only if
$\mu(\sigma-x)=\mu(\sigma)$.

  2. 2.

$S=S^{\mu}(\sigma,E\pm x)$ if and only if
$x\in\operatorname{Excl}(S)\setminus\operatorname{Back}(S)$.

###### Proof.

  1. 1.

The  (Combinatorial KKT Conditions for Stacks). (4.3) show that
$\operatorname{Front}(S)\subset\sigma\subset\operatorname{Incl}(S)$. Then
$x\in\operatorname{Incl}(S^{*})\setminus\operatorname{Front}(S)$ is equivalent
to $\sigma\pm x\in[\operatorname{Front}(S),\operatorname{Incl}(S^{*})]$, and
in this case Lemma 4.4 implies that $S^{\mu}(\sigma\pm x,E)\preceq S^{*}$. The
first part of the result then follows by noting that $S,S^{\mu}(\sigma-x,E)$,
and $S^{\mu}(\sigma+x,E)$ must all be comparable with respect to the partial
ordering $\preceq$. If in addition $\mu(\sigma-x)=\mu(\sigma+x)$ then the
second part of the claim follows directly from the  (Combinatorial KKT
Conditions for Stacks). (4.3).

  2. 2.

The claim follows directly from the  (Combinatorial KKT Conditions for
Stacks). (4.3).∎

######  Lemma 4.9 (First Simplex Pairing Lemma).

Let $E\subset F\subset X$ and
$\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,F)$ such that
$\operatorname{Rad}^{\mu}_{F}(\sigma)>\operatorname{Rad}^{\mu}_{E}(\sigma)$.
Then there exists a point $x\in F\setminus E$ such that

  1. 1.

$S^{\mu}(\sigma-x,E)\preceq S^{\mu}(\sigma,E)=S^{\mu}(\sigma+x,E)$.

  2. 2.

$S^{\mu}(\sigma-x,F)\preceq S^{\mu}(\sigma,F)=S^{\mu}(\sigma+x,F)$.

###### Proof.

Let $S=S^{\mu}(\sigma,E)$, $T=S^{\mu}(\sigma,F)$, and $\gamma=\mu(\sigma)$. By
the  (Combinatorial KKT Conditions for Stacks). (4.3), we have
$T=S^{\mu}(\sigma,\operatorname{Back}(T))$. By assumption
$\operatorname{Rad}(S)<\operatorname{Rad}(T)$, and since $T$ is the stack of
minimum radius that includes $\sigma$ and excludes $\operatorname{Back}(T)$,
$S$ cannot exclude all of $\operatorname{Back}(T)$. Therefore, there exists
some point $x\in\operatorname{Back}(T)\setminus\operatorname{Excl}(S)$. Now
$\operatorname{Excl}(S)=E\cap\mu^{-1}(\gamma)$ and
$\operatorname{Back}(T)\subset F\cap\mu^{-1}(\gamma)$, from which it follows
that $x\in F\setminus E$.

Now $x\notin\operatorname{Excl}(S)$ and $\mu(x)\in\gamma$ together imply that
$x\in\operatorname{Incl}(S)\setminus\operatorname{On}(S)\subset\operatorname{Incl}(S)\setminus\operatorname{Front}(S)$.
Then applying the  (Same Stacks Lemma). (4.8), we get that
$S^{\mu}(\sigma-x,E)\preceq S=S^{\mu}(\sigma+x,E)$ (in particular these stacks
exist). Next, $x\in\operatorname{Back}(T)$ means that
$x\in\operatorname{Incl}(T)\setminus\operatorname{Front}(T)$, so the  (Same
Stacks Lemma). (4.8) implies that $S^{\mu}(\sigma-x,F)\preceq
S^{\mu}(\sigma,F)=S^{\mu}(\sigma+x,F)$ as desired. ∎

######  Lemma 4.10 (Second Simplex Pairing Lemma).

Let $E\subset F\subset X$ and let
$\sigma\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,E)\setminus\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)$.
Then there exists a point $x\in F\setminus E$ such that

  1. 1.

$S^{\mu}(\sigma-x,E)\preceq S^{\mu}(\sigma,E)=S^{\mu}(\sigma+x,E)$.

  2. 2.

Both $\sigma+x$ and $\sigma-x$ are not in
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)$.

###### Proof.

Write $S=S^{\mu}(\sigma,E)$, and $F_{\sigma}=F\cap\operatorname{Excl}(S)$;
then the  (Combinatorial KKT Conditions for Stacks). (4.3) imply that
$S=S^{\mu}(\sigma,F_{\sigma})$ and hence
$\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,F_{\sigma})$. Let
$A\subset X$ and $x\in X$ satisfy $F_{\sigma}\subset A\subset A+x\subset F$
such that
$\sigma\in\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,A)\setminus\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,A+x)$.
Writing $\gamma=\mu(\sigma)$, if $\mu(x)\notin\gamma$ then $S^{\mu}(\sigma,A)$
automatically excludes $A+x$ and
$\sigma\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,A+x)$, so it must be
that $\mu(x)\in\gamma$. Together with the fact that $x\in
F\setminus\operatorname{Excl}(S)$, this means that $x\in F\setminus E$. It
also means that
$x\in\operatorname{Incl}(S)\setminus\operatorname{On}(S)\subset\operatorname{Incl}(S)\setminus\operatorname{Front}(S)$.
Applying the  (Same Stacks Lemma). (4.8) yields part (1) of the claim. In
fact, the same argument also gives that
$x\notin\operatorname{Excl}(S^{\mu}(\sigma,A))$ and
$S^{\mu}(\sigma-x,A)\preceq S^{\mu}(\sigma,A)=S^{\mu}(\sigma+x,A)$.

Now $\sigma\notin\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,A+x)$, so
certainly $\sigma+x\notin\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,A+x)$,
and since
$\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)\subset\operatorname{\mathcal{A}}^{\mu}_{\infty}(X,A+x)$
we see that $\sigma+x\notin\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)$ as
claimed in (2). It remains to show that
$\sigma-x\notin\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)$, so suppose for
contradiction that
$\sigma-x\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,F)$. Then
$\sigma-x\in\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,A+x)$. Write
$T=S^{\mu}(\sigma-x,A+x)$. Since
$\sigma+x\notin\operatorname{\mathcal{A}}_{\infty}^{\mu}(X,A+x)$, we must have
that $x\notin\operatorname{Incl}(T^{*})$. Together with the fact that
$\mu(x)\in\gamma$, this implies that
$x\in\operatorname{Excl}(T)\setminus\operatorname{On}(T)\subset\operatorname{Excl}(T)\setminus\operatorname{Back}(T)$,
so applying part (2) of the  (Same Stacks Lemma). (4.8) gives
$T=S^{\mu}(\sigma-x,A)$. We have already shown that
$S^{\mu}(\sigma-x,A)\preceq S^{\mu}(\sigma,A)$. The upshot is that
$x\notin\operatorname{Incl}(T^{*})=\operatorname{Incl}(S^{\mu}(\sigma-x,A)^{*})\supset\operatorname{Incl}(S^{\mu}(\sigma,A))$.
This, along with the fact that $\mu(x)\in\gamma$, contradicts the fact above
that $x\notin\operatorname{Excl}(S^{\mu}(\sigma,A))$. ∎

##  5 Proof of Main Results

Throughout this section we fix a point cloud $X\subset\mathbb{R}^{d}$ in
general position and the parameter $r\in[0,\infty]$.

###  5.1 Proof of Theorem A

We recall the statement of Theorem A for convenience.

######  Theorem A.

Let $X\subset\mathbb{R}^{d}$ be a finite set of points in general position,
and let $\mu,\nu$ be colourings of $X$ such that $\nu$ refines $\mu$. For any
$r\geq 0$ there are simplicial collapses
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\nu}(X)\searrow\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\mu}(X)$.

Suppose $\mu:X\to[s+1],\nu:X\to[s^{\prime}+1]$ are colourings of $X$ such that
$\mu\preceq\nu$. We wish to show that there is a simplicial collapse
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\nu}(X)\searrow\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\mu}(X)$.
Since $X$ is in general position, we can identify
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}_{r}^{\nu}(X)$ with
its realization as a subcomplex of the chromatic Delaunay triangulation
$\operatorname{Del}^{\nu}(X)$, and we also identify subsets of $X$ with the
simplices they span in $\operatorname{Del}^{\nu}(X)$. Using the same arguments
as in the beginning of Section 3.1, we may assume that $\nu$ is obtained from
$\mu$ by splitting up the last class, i.e., $s^{\prime}=s+1$ and
$\mu^{-1}(s)=\nu^{-1}(\\{s,s+1\\})$. Then by Remark 2.9 there is a colouring
$\zeta:X^{\mu}\to[2]$ such that $X^{\nu}=(X^{\mu})^{\zeta}$, and there is an
embedding of chromatic Delaunay triangulations
$\iota:\operatorname{Del}^{\mu}(X)\to\operatorname{Del}^{\nu}(X)$ such that
$\iota(\operatorname{Del}^{\mu}(X))$ is the graph of some function
$g:\operatorname{Del}^{\mu}(X)\subset\mathbb{R}^{d+s}\to\mathbb{R}$. For the
purposes of this section, we identify
$\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\mu}_{r}(X)$ with
its realization as a subcomplex of $\iota(\operatorname{Del}^{\mu}(X))$, and
we will say that $\sigma\in\operatorname{Del}^{\nu}(X)$ lies above (resp.
below) $\iota(\operatorname{Del}^{\mu}(X))$ if intersects the interior of the
epigraph (resp. hypograph) of $g$ (see Section 3.1 for the precise
definition).

Recall from Section 3.2 that there is a generalized discrete Morse function

$f:\operatorname{Del}^{\nu}(X)\cong\operatorname{\operatorname{Del}\operatorname{\check{C}}}^{\nu}_{\infty}(X)\to[0,\infty)$

defined in Equation 29, whose critical set is