Given a finite set $A\subset\mathbb{R}^d$, let $\cov{r}{k}$ denote the set of all points within distance $r$ to at least $k$ points of $A$.  Allowing $r$ and $k$ to vary, we obtain a 2-parameter family of spaces that grow larger when $r$ increases or $k$ decreases, called the multicover bifiltration.  Motivated by the problem of computing the homology of this  bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy <cit.>.  Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang <cit.>, and can be efficiently computed using a variant of an algorithm given by these authors in <cit.>.  Using an implementation for dimension 2 and 3, we provide experimental results.  Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

§ INTRODUCTION

Let $A$ be a finite subset of $\R^d$, whose points we call sites. For $r\in [0,\infty)$ and an integer $k\geq 0$, we define

\[
\cov{r}{k}:=\left\{  b\in\mathbb{R}^d \mid \textnormal{ } ||b-a||\leq r \textnormal{ for at least $k$ sites } a\in A  \right\}.
\]

Thus, $\cov{r}{k}$ is the union of all $k$-wise intersections of closed balls
of radius $r$ centered at the sites; see Figure <ref>.
Define a bifiltration to be
a collection of sets
\[C:=(C_{r,k})_{(r,k)\in [0,\infty)\times\N}\]
such that
$C_{r,k}\subseteq C_{r',k'}$ whenever $r\leq r'$ and $k\geq k'$.
Clearly, the sets
\[\covonly:=(\cov{r}{k})_{(r,k)\in [0,\infty)\times\N}\]
form a bifiltration.  This is known as the multicover bifiltration.  It arises naturally in topological data analysis (TDA), and specifically, in the topological analysis of data with outliers or non-uniform density <cit.>.

We wish to study the topological structure of the bifiltration $\covonly$ algorithmically in practical applications, via 2-parameter persistent homology <cit.>.  For this, the natural first step is to compute a combinatorial model of $\covonly$, that is, a purely combinatorial bifiltration $C$ which is topologically equivalent to $\covonly$.  This step is the focus of the present paper.  For computational efficiency, $C$ should not be too large.

In fact, we propose two closely related combinatorial models $C$, one polyhedral and one simplicial.  The polyhedral model is a bifiltration of the rhomboid tiling, a polyhedral cell complex in $\R^{d+1}$ recently introduced by Edelsbrunner and Osang to study the multicover bifiltration <cit.>.  Edelsbrunner and Osang have given an efficient algorithm for computing the rhomboid tiling <cit.>, and this adapts readily to compute our bifiltration.  We use the simplicial model to prove that the polyhedral model is topologically equivalent to $\covonly$.

point=[circle,thick,draw=black,fill=black,inner sep=0pt,minimum width=4pt,minimum height=4pt]
(-2.2, 2) rectangle (2, -1.6);

( 0.5, .3) circle (.8);
( -1, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( -1, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( 0.5, .3) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1.2, .6) circle (.8);
( -1, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( -1.2, .6) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1, 0) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1.2, .6) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( 0.5, .3) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1.2, .6) circle (.8);
(-0.5, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( -.7, -.6) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1, 0) circle (.8);
( -.7, -.6) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( .97, -.50) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( 0.5, .3) circle (.8);
( .97, -.50) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
(a)[point] at (-.5,0) ;
( 0.5, .3) circle (.8);
(b)[point] at (.5,.3) ;
( -1, 0) circle (.8);
(c)[point] at (-1,0) ;
( -1.2, .6) circle (.8);
(c)[point] at ( -1.2, .6) ;
( 0, 1.1) circle (.8);
(c)[point] at (  0, 1.1) ;
( -.7, -.6) circle (.8);
(c)[point] at (-.7, -.6) ;
( .97, -.50) circle (.8);
(c)[point] at ( .97, -.5) ;

point=[circle,thick,draw=black,fill=black,inner sep=0pt,minimum width=4pt,minimum height=4pt]
(-2.2, 2) rectangle (2, -1.6);

(-0.5, 0) circle (.8);
( 0.5, .3) circle (.8);
( -1, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( -1.2, .6) circle (.8);
( -1, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( -1, 0) circle (.8);
( -1.2, .6) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( 0.5, .3) circle (.8);
( 0, 1.1) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( 0, 1.1) circle (.8);
( -1, 0) circle (.8);
(-0.5, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

( 0, 1.1) circle (.8);
( -1.2, .6) circle (.8);
(-0.5, 0) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( -1, 0) circle (.8);
( -.7, -.6) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
( 0.5, .3) circle (.8);
( .97, -.50) circle (.8);
[color=niceyellow] (-2,2)rectangle (2,-2);

(-0.5, 0) circle (.8);
(a)[point] at (-.5,0) ;
( 0.5, .3) circle (.8);
(b)[point] at (.5,.3) ;
( -1, 0) circle (.8);
(c)[point] at (-1,0) ;
( -1.2, .6) circle (.8);
(c)[point] at ( -1.2, .6) ;
( 0, 1.1) circle (.8);
(c)[point] at (  0, 1.1) ;
( -.7, -.6) circle (.8);
(c)[point] at (-.7, -.6) ;
( .97, -.50) circle (.8);
(c)[point] at ( .97, -.5) ;

The 2- and 3-fold cover of a few points with respect to a certain radius. The first homology of the 2-fold cover is trivial, while the first homology of the 3-fold cover is non-trivial.

Motivation and prior work.

For $k=1$ fixed, $(\cov{r}{1})_{r\in[0,\infty)}$ is the well-known offset filtration (also known as the union of balls filtration),
a standard construction for analyzing the topology of a finite point sample across scales <cit.>.  It is a central object in the field of persistent homology.
While the persistent homology of this filtration is stable to small geometric perturbations of the
sites <cit.>, it is not robust with respect to outliers, and it can be insensitive to topological structure in high density regions of the data.

Within the framework of 1-parameter persistent homology, there have been many proposals for alternative constructions which address these issues.  These approaches include the removal of low density outliers <cit.>, filtering by a density function <cit.>, distance to measure constructions <cit.>, kernel density functions <cit.>, and subsampling <cit.>.  A detailed overview of these approaches can be found in <cit.>.

Several of these constructions have good stability properties or good asymptotic behavior.
However, as explained in <cit.>, all of the known 1-parameter persistence strategies for handling outliers or variations in density share certain disadvantages: First, they all depend on a choice of a parameter.  Typically, this parameter specifies a fixed spatial scale or a density threshold at which the construction is carried out.  In the absence of a priori knowledge about the structure of the data, it may be unclear how to select such a parameter.  And if the data exhibits topological features at multiple spatial or density scales, it may be that no single parameter choice allows us to capture all the structure present in the data.  Second, constructions that fix a scale parameter are unable to distinguish between small spatial features and large ones, and constructions that fix a density or measure parameter are unable to distinguish features in densely sampled regions of the data from features involving sparse regions.

A natural way to circumvent these limitations is to consider a 2-parameter approach, where one constructs a  bifiltration from the data, rather than a 1-parameter filtration <cit.>.  The multicover bifiltration is one natural option for this.  Alternatives include the density bifiltrations of Carlsson and Zomorodian <cit.>, and the degree bifiltrations of Lesnick and Wright  <cit.>; again, we refer the reader to <cit.> for a more detailed discussion.
Among these three options, the multicover bifiltration has two attractive features which together distinguish it from the others.  First, its construction does not depend on any additional parameters. Second, the multicover bifiltration satisfies a strong stability property, which in particular guarantees robustness to outliers <cit.>.

There is a substantial and growing literature on the use of bifiltrations in data analysis.  Most approaches begin by applying homology with coefficients to the bifiltration, to obtain an algebraic object called  bipersistence module.  In contrast to the 1-parameter case, where the algebraic structure of a persistence module is completely described by a barcode <cit.>, it is well-known that defining the barcode of bipersistence modules is problematic <cit.>.  Nevertheless, one can compute invariants of a bipersistence module which serve as useful surrogates for a barcode, and a number of ideas for this have been proposed  <cit.>.

Regardless of which invariants of the multicover bifiltration we wish to consider, to work with this bifiltration computationally, the natural first step is to find a reasonably sized combinatorial  (i.e., simplicial or polyhedral) model for the bifiltration.  With such a model, recently developed algorithms such as those described in <cit.> and <cit.> can efficiently compute minimal presentations and standard invariants of the homology modules of the bifiltration.

In the 1-parameter setting, there are two well-known simplicial models of the offset filtration. The Čech filtration, is given at each scale by the nerve of the balls; the equivalence of the offset and Čech filtrations follows from the Persistent Nerve Theorem.  For large point sets, the full Čech filtration is too large to be used in practical computations.  However, the alpha filtration (also known as the Delaunay filtration) <cit.> is a much smaller subfiltration of the Čech filtration which is also simplicial model for the offset filtration.  It is given at each scale by intersecting each ball with the Voronoi cell <cit.> of its center, and then taking the nerve of the resulting regions.  For $d$ small (say $d\leq 3$), the Delaunay filtration is readily computed in practice for many thousands of points.

It is implicit in the work of Sheehy <cit.> that the multicover bifiltration has an elegant simplicial model, the subdivision-Čech bifiltration, obtained via a natural filtration on the barycentric subdivision of each Čech complex; see also <cit.> and <cit.>.  However, the subdivision-Čech bifiltration has exponentially many vertices in the size of the data, making it even more unsuitable for computations than the ordinary Čech filtration.

Edelsbrunner and Osang <cit.> therefore seek to develop the computational theory of the multicover bifiltration using higher-order Delaunay complexes <cit.>,  taking the alpha filtration as inspiration.  Assuming the sites are in general position, they define a polyhedral cell complex in $\R^{d+1}$ called the rhomboid tiling, which contains all higher-order Delaunay complexes as planar sections.
Using the rhomboid tiling, they present a polynomial time algorithm to compute the barcodes of a horizontal or vertical slice of the multicover bifiltration (i.e., of a one-parameter filtration obtained by fixing either one of the two parameters $r,k$).
The case of fixed $r$ and varying $k$ is more challenging because the order-$k$ Delaunay complexes do not form a filtration.  The authors construct a zigzag filtration for this case.
The problem of efficiently computing 2-parameter persistent homology of the multicover bifiltration is not addressed by <cit.>.

We note that the subdivision-Čech bifiltration is more general than the Rhomboid tiling:  the rhomboid tiling is defined only for Euclidean data, whereas the topological equivalence of the subdivision-Čech and multicover bifiltrations extends to data in any metric space where finite intersections of balls are contractible.

We introduce the first efficiently computable combinatorial models of the
multicover bifiltration $\covonly$.  First, we introduce a simplicial model, whose
construction is based on two main ideas: In order to connect
the higher-order alpha complex constructions for $(r,k)$ and $(r,k+1)$, we simply overlay
their underlying covers to a “double-cover”, whose nerve is
a simplicial complex that contains both alpha complexes. This yields a zigzag of simplicial filtrations.  The second main idea is that this zigzag can be “straightened out” to a (non-zigzaging) bifiltration,
simply by taking unions of prefixes in the zigzag sequence.  This straightening technique has previously been used by Sheehy to construct sparse approximations of
Vietoris-Rips complexes <cit.>.  Together, these two ideas give rise to a bifiltration $\tcovonly:=(\tcov{r}{k})_{(r,k)\in [0,\infty)\times\N}$
of simplicial complexes.

The bifiltration $\tcovonly$ can also be obtained directly as the persistent nerve of a “thickening" of $\covonly$ constructed via mapping telescopes.  This observation leads to a simple
proof of topological equivalence (i.e., weak equivalence; see Section <ref>) of $\covonly$ and $\tcovonly$ via the Nerve Theorem.  It follows that the persistent homology modules of $\covonly$ and $\tcovonly$ are isomorphic.

Our second contribution is to show that the rhomboid tiling
as defined in <cit.> also gives rise to a (non-zigzaging) bifiltration
of polyhedral complexes that is topologically equivalent to the multicover.
We proceed in two steps:
First, we slice every rhomboid at each integer value $k$
(slightly increasing the number of cells) and adapt the straightening trick used to construct $\tcovonly$.
We prove the topological equivalence of this construction
with the multicover bifiltration by relating the slice rhomboid filtration with $\tcovonly$.
The main observation is a one-to-one correspondence of maximal-dimensional cells
in both constructions, which leads to a proof via the Nerve Theorem.
Second, we relate the sliced and unsliced rhomboid tilings at every scale via a deformation retraction.

We give size bounds for both of the bifiltrations we introduce. For $n$ points in $\R^d$, we show that their size is $O(n^{d+1})$.  This is a decisive improvement over Sheehy's Čech-based construction, which has exponential dependence on $n$.

An efficient algorithm for computing rhomboid tilings has recently been presented in <cit.>;
hence, using the accompanying implementation rhomboidtiling of this algorithm,
our second contribution gives us an efficient software to compute
a bifiltration of cell complexes equivalent to $\covonly$, currently for points in $\R^2$ and $\R^3$.
We combine this implementation with the libraries mpfree
and rivet to demonstrate that minimal presentations of multicover persistent homology modules can now be efficiently computed, often within seconds, as can invariants such as the Hilbert function.

§ BACKGROUND

For $P$ a poset, define a ($P$-indexed) filtration to be a collection of topological spaces $X=(X_p)_{p\in P}$ indexed by $P$, such that $X_p\subseteq X_q$ whenever $p\leq q\in P$.  For example, an $\N$-indexed filtration $X$ is a diagram of spaces and inclusions of the following form:

\[
\begin{tikzcd}
X_{1}  \arrow[hookrightarrow]{r} & X_{2} \arrow[hookrightarrow]{r} & X_{3}  \arrow[hookrightarrow]{r}&   X_{4} \arrow[hookrightarrow]{r}&  \cdots.
\end{tikzcd}
\]

A morphism $\varphi:X\to Y$ of $P$-indexed filtrations is a collection of continuous maps $(\varphi_p:X_p\to Y_p)_{p\in P}$ which commute with the inclusions in $X$ and $Y$.  In the language of category theory, a $P$-indexed filtration is a functor $P\to \mathbf{Top}$ whose internal maps are inclusions, and a morphism is a natural transformation.

Recall that the product poset $P\times Q$ of posets $P$ and $Q$ is defined by taking $(p,q)\leq (p',q')$ if and only if $p\leq p'$ and $q\leq q'$.
When $P$ is the product of two totally ordered sets, we call a $P$-indexed filtration a bifiltration.

In the classical homotopy theory of diagrams of spaces, there is a standard analogue of the notion of homotopy equivalence for diagrams of spaces, called weak equivalence.  We now define a version of this for $P$-indexed filtrations: A morphism of filtrations $\varphi:X\to Y$ is called an objectwise homotopy equivalence if each $\varphi_p:X_p\to Y_p$ is a homotopy equivalence. If there exists a finite zigzag diagram of objectwise homotopy equivalences

\[X\rightarrow Z_1 \leftarrow Z_2 \rightarrow \cdots \leftarrow Z_{n-1}\rightarrow Z_n \leftarrow Y\]

connecting $X$ and $Y$,  then we say that $X$ and $Y$ are weakly equivalent.  The terminology originates from the theory of model categories <cit.>.  See <cit.> for discussions of weak equivalence of diagrams in the context of TDA.

To motivate the consideration of zigzags in the definition above, we note that for $X$ and $Y$ a pair of weakly equivalent $P$-indexed filtrations, there is not necessarily an objectwise homotopy equivalence $f:X\to Y$.  For example, let $P=\R$, $X$ be the offset filtration on $\{0,1\}\subset \R$, and $Y$ be the nerve filtration of $X$.  It is easy to check that there is no objectwise homotopy equivalence $f:X\to Y$.  On the other hand, it follows from the Persistent Nerve Theorem (<Ref> below) that $X$ and $Y$ are weakly equivalent.  Moreover, one can construct a similar example of weakly equivalent filtrations for which there is no objectwise homotopy equivalence in either direction.

An objectwise weak equivalence $\varphi:X\to Y$ induces isomorphisms on the persistent homology modules of $X$ and $Y$.  Hence, weakly equivalent filtrations have isomorphic persistent homology modules.

We say a $P$-indexed filtration $X$ is Euclidean if $X_p\subset \R^n$ for some $n$ and all $p\in P$.

point=[circle,thick,draw=black!10!niceyellow,fill=black!10!niceyellow,inner sep=0pt,minimum width=4pt,minimum height=4pt]

basefont/.style = font = ,
timing/.style = basefont, sloped,above,
label/.style = basefont, align = left,
screen/.style = basefont, black, align = center,
minimum size = 6cm, fill = black!6, draw = black;

in 1,2,3
in 1,2,3

at (*-+0.45,*-+0.3) (,);

[draw,thick] (*-,*-) rectangle (*,*);

(,++) ellipse (0.55cm and 0.1cm)
(,++) circle (0.5cm)
(,++) ellipse (.05cm and .05cm)

[niceyellow] ;
[niceyellow] ;

node(1)[below] ;
node (2) [above] ;

(+,++) ellipse (.65cm and .15cm)
(+,++) circle (.5cm)
(+,++) ellipse (.4cm and .7cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(++,++) ellipse (.8cm and .2cm)
(++,++) circle (.5cm)
(++,++) ellipse (.9cm and 1.5cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(,+) ellipse (1.5cm and .8cm)
(,+) circle (1.2cm)
(,+) ellipse (.15cm and .3cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(+,+) ellipse (1.5cm and .8cm)
(+,+) circle (1.2cm)
(+,+) ellipse (.6cm and .8cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(2*+,+) ellipse (1.6cm and .9cm)
(2*+,+) circle (1.3cm)
(2*+,+) ellipse (1cm and 1.6cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(,) ellipse (1.5cm and .8cm)
(,) circle (1.2cm)
(,) ellipse (.6cm and .8cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(+,) ellipse (1.6cm and .9cm)
(+,) circle (1.2cm)
(+,) ellipse (.65cm and 1.3cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

(2*+,) ellipse (1.7cm and 1cm)
(2*+,) circle (1.3cm)
(2*+,) ellipse (1.1cm and 1.9cm)

[niceyellow] ;
[niceyellow] ;
[niceyellow] ;

node[below] ;
node [above] ;
node [below] ;

point=[circle,thick,draw=black!10!niceyellow,fill=black!10!niceyellow,inner sep=0pt,minimum width=8pt,minimum height=8pt]

basefont/.style = font = ,
timing/.style = basefont, sloped,above,
label/.style = basefont, align = left,
screen/.style = basefont, black, align = center,
minimum size = 6cm, fill = black!6, draw = black;

in 1,2,3
in 1,2,3

at (*-+0.45,*-+0.3) (,);

[draw,thick] (*-,*-) rectangle (*,*);

(1) at (,++) [point] ;
(2) at (,++) [point] ;

(1) at (+,++) [point] ;
(2) at (+,++) [point] ;
(3) at (+,++) [point] ;

(1) at (++,++) [point] ;
(2) at (++,++) [point] ;
(3) at (++,++) [point] ;

[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) –  (3.center) – cycle;

(1) at (++,++) [point] ;
(2) at (++,++) [point] ;
(3) at (++,++) [point] ;

(1) at (,+) [point] ;
(2) at (,+) [point] ;
(3) at (,+) [point] ;

[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;

(1) at (,+) [point] ;
(2) at (,+) [point] ;
(3) at (,+) [point] ;

(1) at (+,+) [point] ;
(2) at (+,+) [point] ;
(3) at (+,+) [point] ;

[pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (1.center) – cycle;

(1) at (+,+) [point] ;
(2) at (+,+) [point] ;
(3) at (+,+) [point] ;

(1) at (++,+) [point] ;
(2) at (++,+) [point] ;
(3) at (++,+) [point] ;

[black!10!niceyellow,opacity=.5] (1.center) – (2.center) – (3.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (1.center) – cycle;

(1) at (++,+) [point] ;
(2) at (++,+) [point] ;
(3) at (++,+) [point] ;

(1) at (,) [point] ;
(2) at (,) [point] ;
(3) at (,) [point] ;

[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (1.center) – cycle;

(1) at (,) [point] ;
(2) at (,) [point] ;
(3) at (,) [point] ;

(1) at (+,) [point] ;
(2) at (+,) [point] ;
(3) at (+,) [point] ;

[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (1.center) – cycle;

(1) at (+,) [point] ;
(2) at (+,) [point] ;
(3) at (+,) [point] ;

(1) at (++,) [point] ;
(2) at (++,) [point] ;
(3) at (++,) [point] ;

[black!10!niceyellow,opacity=.5] (1.center) – (2.center) – (3.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (1.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (2.center) – cycle;
[pattern=north east lines, pattern color=black!10!niceyellow, draw=black!10!niceyellow,line width=.05cm,opacity=.7] (3.center) – (1.center) – cycle;

(1) at (++,) [point] ;
(2) at (++,) [point] ;
(3) at (++,) [point] ;

Left: A bifiltration of good covers over $\{1<2<3\}\times\{3<2<1\}$. Right: A bifiltration consisting of the nerves of the covers. The Persistent Nerve Theorem ensures that not only the individual spaces at scales $(n,m)$ are homotopy equivalent, but also that the two bifiltrations are weakly equivalent.

*The Persistent Nerve Theorem.
A cover of $X\subset \R^n$ is a collection $\firstcovername=\{\firstcovername^i\}_{i\in I}$ of subsets of $X$ whose union is $X$.
The nerve of $\firstcovername$ is the abstract simplicial complex

\[
\nerve\left(\firstcovername\right):=\left\{\sigma\subset I\mid\bigcap_{i\in \sigma} \firstcovername^i \neq \emptyset \right\}.
\]

We say that the cover is good if it is finite and consists of closed, convex sets <cit.>.

One version of the Nerve Theorem  asserts that $X$ and
$\nerve\left(\firstcovername\right)$ are homotopy equivalent whenever $\firstcovername$ is a good cover of $X$ <cit.>.

It is TDA folklore that this version of the Nerve Theorem can be extended to a persistent version; a proof appears in <cit.>; see also <cit.> for formulation of the Persistent Nerve Theorem in terms of open covers.

In order to state the Persistent Nerve Theorem for closed, convex covers, we first extend the definition of a cover.

Let $P$ be a poset and $X$ a $P$-indexed Euclidean filtration.  A cover of $X$ is a collection
$\firstcovername=\{\firstcovername^i\}_{i\in I}$ of $P$-indexed filtrations  such that for each $p\in P$, $\{\firstcovername^i_p \mid i\in I\}$ is a cover of $\firstcovername_p$.  We say $\firstcovername$ is good if each $\firstcovername_p:=\{\firstcovername^i_p \mid i\in I\}$ is a good cover.

The definition of the nerve above extends immediately to yield a nerve filtration $\nerve\left(\firstcovername\right)$ associated to any cover of a filtration.

Let $P$ be a poset, $X$ a $P$-indexed Euclidean filtration, and $\firstcovername$ a good cover of $X$.  There exists a diagram of objectwise homotopy equivalences

\[
\begin{tikzcd}
X  &  \arrow[labels=above]{l}{\simeq} \arrow{r}{\simeq} \deltaspace{\firstcovername}{X}  & \nerve(\firstcovername).
\end{tikzcd}
\]

As shown in <cit.>, the intermediate filtration $\deltaspace{\firstcovername}{X}$ in the statement of the theorem can be taken to be a homotopy colimit of a diagram constructed from $\firstcovername$, just as in the proof of the Persistent Nerve Theorem for open covers <cit.>.  Note that if $P$ is a singleton set, the Persistent Nerve Theorem specializes to the classical version of the Nerve Theorem mentioned above.

Left: The 2-fold cover of some points with respect to a certain radius overlapped with its Voronoi diagram of order 2. $\vorcovonly$ is combinatorially simpler than
Right: The corresponding 3-fold cover overlapped with its Voronoi diagram of order 3.

As indicated in the introduction, the multicover bifiltration of a finite set $A\subset \R^d$ is the $\R\times \N^{\mathrm{op}}$-indexed bifiltration $\covonly$ given by

\[
\cov{r}{k}:=\left\{  b\in\mathbb{R}^d \mid \textnormal{ } ||b-a||\leq r \textnormal{ for at least $k$ points } a\in A  \right\}.
\]

A first step towards constructing a simplicial model for $\covonly$ is to identify a good cover for $\cov{r}{k}$, with $r$ and $k$ fixed.

For $\widetilde{A}\subset A$ we define

\[ \covreg{r}{\widetilde{A}}:=\left\{ b\in\mathbb{R}^d \mid\textnormal{ } ||b-\tilde{a}||\leq r \textnormal{ for all } \tilde{a}\in \widetilde{A} \right\}.
\]

Clearly, $\cov{r}{k}$ is the union of all $\covreg{r}{\widetilde{A}}$ such that $\widetilde{A}\subset A$ and $|\widetilde{A}|=k$, and each $\covreg{r}{\widetilde{A}}$ is closed and convex. Hence, denoting
\[\bigcov{r}{k}:=\left\{ \covreg{r}{\widetilde{A}} \mid  \widetilde{A}\subset A,  |\widetilde{A}|=k \right\}\]
and applying the Nerve Theorem, $\cov{r}{k}$ is homotopy equivalent to $\nerve(\bigcov{r}{k})$.  For fixed $k$ and $r\leq r'$, we have an inclusion $\nerve(\bigcov{r}{k})\hookrightarrow \nerve(\bigcov{r'}{k})$.

Note that these nerves can be quite large: for large enough $r$, $\nerve(\bigcov{r}{k})$ contains $\binom{|A|}{k}$ vertices.   To obtain a smaller simplicial model of $\cov{r}{k}$, we use the generalization of Delaunay triangulations to higher-order Delaunay complexes. For a subset $\tilde{A} \subset A$ with $|\tilde{A}|=k$, define its order-$k$ Voronoi region as

\[
\vorreg{\tilde{A}}:=\left\{ b\in \mathbb{R}^d \mid \textnormal{ } ||b-\tilde{a}||\leq ||b-a|| \textnormal{ for all } \tilde{a}\in \tilde{A}, a\in A \setminus \tilde{A} \right\}.
\]

The set of all order-$k$ Voronoi regions  yield a decomposition of $\R^d$ into closed convex subsets having the same $k$ closest points of $A$ in common.  This decomposition is called the order-$k$ Voronoi diagram <cit.>.  We denote it as $\vor{k}$.

For any $r\in \R$ and $k\in \N$, intersecting each order-$k$ Voronoi region with the corresponding multicovered region of fixed radius $r$ yields the following good cover of $\cov{r}{k}$.

\[
\vorcov{r}{k}:=\left\{ \covreg{r}{\widetilde{A}}\cap \vorreg{\tilde{A}}\mid\tilde{A}\subset A, |\tilde{A}|=k \right\}.
\]

For an illustration, see Figure <ref>.
The nerve of $\vorcov{r}{k}$, which we will denote $\del{r}{k}$, is called an order-$k$ Delaunay complex.
By the Nerve Theorem, $\del{r}{k}$ and $\cov{r}{k}$ are homotopy equivalent.
Note that $\del{r}{1}$  is the alpha complex of radius $r$ <cit.>.
A different but related  concept is the order-$k$ Delaunay mosaic, which is the geometric dual of the order-$k$ Voronoi diagram <cit.>; see <Ref>.

§ A SIMPLICIAL DELAUNAY BIFILTRATION

point=[circle,thick,draw=black!10!niceyellow,fill=black!10!niceyellow,inner sep=0pt,minimum width=4pt,minimum height=4pt]

basefont/.style = font = ,
timing/.style = basefont, sloped,above,,
label/.style = basefont, align = left,
screen/.style = basefont, black, align = center,
minimum size = 6cm, fill = black!6, draw = black,opacity=.5;

(1)[point,above right=9.5em and 3.5em of sheet1.south west] ;
(2)[point,above right=12.5em and 7em of sheet1.south west] ;
(3)[point,above right=15em and 9em of sheet1.south west] ;
(4)[point,above right=13em and 11em of sheet1.south west] ;
(5)[point,above right=14em and 13em of sheet1.south west] ;
(6)[point,above right=12em and 11.5em of sheet1.south west] ;
(7)[point,above right=9em and 12em of sheet1.south west] ;
(8)[point,above right=7.5em and 8em of sheet1.south west] ;
(9)[point,above right=8em and 15em of sheet1.south west] ;

[black!10!niceyellow,opacity=.4] (1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4] (6.center) – (7.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (6.center) – (7.center) – (8.center) – cycle;

(10)[point,above right=11em and 3em of sheet2.south west] ;
(11)[point,above right=14em and 6em of sheet2.south west] ;
(12)[point,above right=16em and 6.5em of sheet2.south west] ;
(13)[point,above right=13.5em and 8em of sheet2.south west] ;
(14)[point,above right=15em and 12.5em of sheet2.south west] ;
(15)[point,above right=9.5em and 11em of sheet2.south west] ;
(16)[point,above right=7em and 9em of sheet2.south west] ;
(17)[point,above right=10.5em and 7em of sheet2.south west] ;
(18)[point,above right=10em and 15.5em of sheet2.south west] ;
(19)[point,above right=6.5em and 5em of sheet2.south west] ;

[black!10!niceyellow,opacity=.4] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center)  – (18.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (18.center)  – cycle;

[label, above right=10.75em and -0.5em of sheet1.west] (f1-label) ${\del{r}{3}}$;
[label, above right=10.75em and -0.5em of sheet2.west] (f2-label) $\del{r}{2}$;

point=[circle,thick,draw=black!10!niceyellow,fill=black!10!niceyellow,inner sep=0pt,minimum width=4pt,minimum height=4pt]

basefont/.style = font = ,
timing/.style = basefont, sloped,above,,
label/.style = basefont, align = left,
screen/.style = basefont, black, align = center,
minimum size = 6cm, fill = black!6, draw = black,opacity=.7;

(1)[point,above right=9.5em and 3.5em of sheet1.south west] ;
(2)[point,above right=12.5em and 7em of sheet1.south west] ;
(3)[point,above right=15em and 9em of sheet1.south west] ;
(4)[point,above right=13em and 11em of sheet1.south west] ;
(5)[point,above right=14em and 13em of sheet1.south west] ;
(6)[point,above right=12em and 11.5em of sheet1.south west] ;
(7)[point,above right=9em and 12em of sheet1.south west] ;
(8)[point,above right=7.5em and 8em of sheet1.south west] ;
(9)[point,above right=8em and 15em of sheet1.south west] ;

[black!10!niceyellow,opacity=.4](1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4] (6.center) – (7.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (6.center) – (7.center) – (8.center) – cycle;

(10)[point,above right=11em and 3em of sheet2.south west] ;
(11)[point,above right=14em and 6em of sheet2.south west] ;
(12)[point,above right=16em and 6.5em of sheet2.south west] ;
(13)[point,above right=13.5em and 8em of sheet2.south west] ;
(14)[point,above right=15em and 12.5em of sheet2.south west] ;
(15)[point,above right=9.5em and 11em of sheet2.south west] ;
(16)[point,above right=7em and 9em of sheet2.south west] ;
(17)[point,above right=10.5em and 7em of sheet2.south west] ;
(18)[point,above right=10em and 15.2em of sheet2.south west] ;
(19)[point,above right=6.5em and 5em of sheet2.south west] ;

[black!10!niceyellow,opacity=.4] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center)  – (18.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (18.center)  – cycle;

[black!10!niceyellow,opacity=.15] (1.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (10.center) – cycle;

[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (11.center) – cycle;

[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (17.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (17.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (17.center) – (16.center) – cycle;

[black!10!niceyellow,opacity=.15] (9.center) – (15.center) – (18.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (9.center) – (15.center) – (18.center) – cycle;

[black!10!niceyellow,opacity=.15] (5.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15]  (5.center) – (14.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (14.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (8.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (16.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (16.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (17.center) – (19.center) – cycle;

(10)[point,above right=11em and 3em of sheet2.south west] ;
(11)[point,above right=14em and 6em of sheet2.south west] ;
(12)[point,above right=16em and 6.5em of sheet2.south west] ;
(13)[point,above right=13.5em and 8em of sheet2.south west] ;
(14)[point,above right=15em and 12.5em of sheet2.south west] ;
(15)[point,above right=9.5em and 11em of sheet2.south west] ;
(16)[point,above right=7em and 9em of sheet2.south west] ;
(17)[point,above right=10.5em and 7em of sheet2.south west] ;
(18)[point,above right=10em and 15.2em of sheet2.south west] ;
(19)[point,above right=6.5em and 5em of sheet2.south west] ;

[black!10!niceyellow,opacity=.4] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center)  – (18.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (18.center)  – cycle;

[label, above right=10.75em and -0.5em of sheet2.west] (f1-label) ${\del{r}{2}}$;
[label, above right=10.75em and -0.5em of sheet1.west] (f2-label) ${\del{r}{3}}$;

Left: The Delaunay complexes of order 2 and 3 of our running example. Right: The construction of the simplicial complex $\tdel{r}{2}$. $\tdel{r}{2}$ consists of the Delaunay complexes ${\del{r}{2}}$ and ${\del{r}{3}}$, and additional mixed simplices connecting these. This connection arises from intersections of the $2$-, and $3$-fold covers restricted to their Voronoi diagrams of order 2 and 3, respectively.

For fixed $r\geq 0$, we have inclusions

\[
\begin{tikzcd}
\cdots \arrow[hookrightarrow]{r} & \cov{r}{5} \arrow[hookrightarrow]{r} & \cov{r}{4} \arrow[hookrightarrow]{r} & \cov{r}{3} \arrow[hookrightarrow]{r} & \cov{r}{2} \arrow[hookrightarrow]{r} & \cov{r}{1},
\end{tikzcd}
\]

but there are no analogous inclusions  $\del{r}{k}\hookrightarrow \del{r}{k-1}$ between the higher-order Delaunay complexes.
Indeed, we do not even have inclusions of the vertex sets.  Consequently, $\vorcovonly$ is not a bifiltration of covers.

*Overlaying consecutive covers.
We replace the higher-order Delaunay complexes $\del{r}{k}$ by the nerve of the union of two consecutive $\vorcov{r}{k}$.
For an illustration of the outcome, see Figure <ref>. Formally, we define

\[
\tdel{r}{k}:=\nerve\left( \vorcov{r}{k} \cup \vorcov{r}{k+1} \right).
\]

Importantly, $\vorcov{r}{k} \cup \vorcov{r}{k+1}$ covers the same space as  $\vorcov{r}{k}$ for any $r\geq 0$ and $k\in\mathbb{N}$.
Furthermore, we get inclusions

\[
\begin{tikzcd}
\del{r}{k+1}  \arrow[hookrightarrow]{r} & \tdel{r}{k} \arrow[hookleftarrow]{r} &  \del{r}{k}.
\end{tikzcd}
\]

*Straightening out zigzags.

In order to define a simplicial bifiltration, let $n:=|A|$, $r\geq 0$, and define the filtration

\[
\begin{tikzcd}
\del{r}{n} \ar[hookrightarrow]{r} & \tdel{r}{n-1} \ar[hookrightarrow]{r} & \tdel{r}{n-2}\cup\tdel{r}{n-1} \ar[hookrightarrow]{r} & \cdots \ar[hookrightarrow]{r} & \bigcup_{i=1}^{n-1} \tdel{r}{i}.
\end{tikzcd}
\]

Since $\del{r}{k}=\emptyset$ for all $k>n$, we can denote the spaces in this filtration by

\[
\tcov{r}{k}:= \bigcup_{i\geq k} \tdel{r}{i}.
\]

For an illustration, see Figure <ref>. Letting both $r$ and $k$ vary, we obtain a $\R\times \N^{\mathrm{op}}$-indexed  bifiltration $\tcovonly$. Note that $\tcov{r}{k}$ is not equal to the nerve of the union of all $\vorcov{r}{i}$, $i\geq k$, which is a much larger object.

point=[circle,thick,draw=niceyellow,fill=niceyellow,inner sep=0pt,minimum width=4pt,minimum height=4pt]

basefont/.style = font = ,
timing/.style = basefont, sloped,above,,
label/.style = basefont, align = left,
screen/.style = basefont, black, align = center,
minimum size = 6cm, fill = black!6, draw = black,opacity=.7;

(20)[point,above right=11.5em and 3.5em of sheet3.south west] ;
(21)[point,above right=14em and 7em of sheet3.south west] ;
(22)[point,above right=8em and 8em of sheet3.south west] ;
(23)[point,above right=11em and 11em of sheet3.south west] ;

(1)[point,above right=9.5em and 3.5em of sheet1.south west] ;
(2)[point,above right=12.5em and 7em of sheet1.south west] ;
(3)[point,above right=15em and 9em of sheet1.south west] ;
(4)[point,above right=13em and 11em of sheet1.south west] ;
(5)[point,above right=14em and 13em of sheet1.south west] ;
(6)[point,above right=12em and 11.5em of sheet1.south west] ;
(7)[point,above right=9em and 12em of sheet1.south west] ;
(8)[point,above right=7.5em and 8em of sheet1.south west] ;
(9)[point,above right=8em and 15em of sheet1.south west] ;

[black!10!niceyellow,opacity=.4](1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4] (6.center) – (7.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (6.center) – (7.center) – (8.center) – cycle;

[black!10!niceyellow,opacity=.15] (21.center) – (2.center) – (3.center) – cycle;
[black!10!niceyellow,opacity=.15] (21.center) – (2.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.15] (21.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.15] (20.center) – (1.center) – (2.center) – cycle;
[black!10!niceyellow,opacity=.15] (20.center) – (1.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.15] (20.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.15] (22.center) – (8.center) – (7.center) – cycle;
[black!10!niceyellow,opacity=.15] (22.center) – (7.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.15] (22.center) – (8.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.15] (23.center) – (4.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.15] (23.center) – (4.center) – (5.center) – cycle;
[black!10!niceyellow,opacity=.15] (23.center) – (6.center) – (5.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (21.center) – (2.center) – (3.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (21.center) – (2.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (21.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (20.center) – (1.center) – (2.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (20.center) – (1.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (20.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (22.center) – (8.center) – (7.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (22.center) – (7.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (22.center) – (8.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (23.center) – (4.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (23.center) – (4.center) – (5.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (23.center) – (6.center) – (5.center) – cycle;

(1)[point,above right=9.5em and 3.5em of sheet1.south west] ;
(2)[point,above right=12.5em and 7em of sheet1.south west] ;
(3)[point,above right=15em and 9em of sheet1.south west] ;
(4)[point,above right=13em and 11em of sheet1.south west] ;
(5)[point,above right=14em and 13em of sheet1.south west] ;
(6)[point,above right=12em and 11.5em of sheet1.south west] ;
(7)[point,above right=9em and 12em of sheet1.south west] ;
(8)[point,above right=7.5em and 8em of sheet1.south west] ;
(9)[point,above right=8em and 15em of sheet1.south west] ;

[black!10!niceyellow,opacity=.4](1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.4] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.4] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.4] (6.center) – (7.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (1.center) – (2.center) – (8.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (2.center) – (3.center) – (4.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (4.center) – (5.center) – (6.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (6.center) – (7.center) – (8.center) – cycle;

(10)[point,above right=11em and 3em of sheet2.south west] ;
(11)[point,above right=14em and 6em of sheet2.south west] ;
(12)[point,above right=16em and 6.5em of sheet2.south west] ;
(13)[point,above right=13.5em and 8em of sheet2.south west] ;
(14)[point,above right=15em and 12.5em of sheet2.south west] ;
(15)[point,above right=9.5em and 11em of sheet2.south west] ;
(16)[point,above right=7em and 9em of sheet2.south west] ;
(17)[point,above right=10.5em and 7em of sheet2.south west] ;
(18)[point,above right=10em and 15.2em of sheet2.south west] ;
(19)[point,above right=6.5em and 5em of sheet2.south west] ;

[black!10!niceyellow,opacity=.4] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center)  – (18.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (18.center)  – cycle;

[black!10!niceyellow,opacity=.15] (1.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (2.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.15] (1.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (2.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (10.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (1.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (10.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (10.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (8.center) – (10.center) – cycle;

[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (12.center) – (11.center) – cycle;

[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (3.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (2.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (3.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (3.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (11.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (2.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (3.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (11.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (17.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (5.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (5.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (4.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (5.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (4.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (17.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (15.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (4.center) – (17.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (7.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (6.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (7.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (8.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (7.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (6.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (17.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (15.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (7.center) – (17.center) – (16.center) – cycle;

[black!10!niceyellow,opacity=.15] (9.center) – (15.center) – (18.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (9.center) – (15.center) – (18.center) – cycle;

[black!10!niceyellow,opacity=.15] (5.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.15]  (5.center) – (14.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (5.center) – (14.center) – (13.center) – cycle;

[black!10!niceyellow,opacity=.15] (8.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (16.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.15] (8.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (16.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4, line width=.2mm] (8.center) – (17.center) – (19.center) – cycle;

(10)[point,above right=11em and 3em of sheet2.south west] ;
(11)[point,above right=14em and 6em of sheet2.south west] ;
(12)[point,above right=16em and 6.5em of sheet2.south west] ;
(13)[point,above right=13.5em and 8em of sheet2.south west] ;
(14)[point,above right=15em and 12.5em of sheet2.south west] ;
(15)[point,above right=9.5em and 11em of sheet2.south west] ;
(16)[point,above right=7em and 9em of sheet2.south west] ;
(17)[point,above right=10.5em and 7em of sheet2.south west] ;
(18)[point,above right=10em and 15.2em of sheet2.south west] ;
(19)[point,above right=6.5em and 5em of sheet2.south west] ;

[black!10!niceyellow,opacity=.4] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.4] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.4] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.4] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.4] (15.center)  – (18.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (11.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (12.center) – (13.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (14.center) – (15.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (10.center) – (17.center) – (19.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (17.center) – (19.center) – (16.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (11.center) – (13.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (13.center) – (15.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (16.center) – (17.center) – cycle;
[black!10!niceyellow,opacity=.8, line width=.2mm] (15.center) – (18.center)  – cycle;
[xshift=750,yshift=300] (sheet6);

ı/ in

[label,  above right=10.75em and -0.5em of sheetı.west] (fı-label) ;

[dotted,->] (sheet5.south east) edge node[timing, below]  (sheet4.south east);
[ultra thick,->] (sheet1.south east) edge node[timing, below]  (sheet2.south east);
[ultra thick,->] (sheet4.south east) edge node[timing, below]  (sheet3.south east);
[ultra thick,->] (sheet3.south east) edge node[timing, below]  (sheet1.south east);

$\tcov{r}{2}$ is union of all $\tdel{r}{i}$, $i\geq 2$.   By <Ref>, it is homotopy equivalent to $\del{r}{2}$. $\tcovonly$ is bounded by $n$, the number of sites in $A$. Thus, in this case, $\del{r}{i}$ is empty for $i\geq 5$.

The  bifiltration $\tcovonly$ is our desired simplicial model of the multicover bifiltration:

The multicover bifiltration $\covonly$ is weakly equivalent to $\tcovonly$.

The proof of <Ref> will use the following variant of the usual mapping telescope construction  <cit.>: given any sequence of continuous maps

\[C = (C_1\hookrightarrow C_{2} \hookrightarrow \cdots  \hookrightarrow C_n),\]

let $M_C$ denote the quotient of the disjoint union
\[\sqcup_{i=1}^{n} C_i\times I\]

given by gluing each $C_{i}\times \{1\}$ to $C_{i+1}\times \{0\}$ along the inclusion $C_{i}\hookrightarrow C_{i+1}$.  It is easy to check that we have a deformation retraction $M_C\to C_n$.

Our proof strategy is similar to ones used for sparse filtrations <cit.>.
We will observe that $\tcovonly$ is isomorphic to the nerve of a good cover of a bifiltration $X$ which is weakly equivalent to $\covonly$.  The result then follows from the Persistent Nerve Theorem.

Let $X_{r,k}$ be the mapping telescope of the sequence of

\[\cov{r}{n}\hookrightarrow \cov{r}{n-1}\hookrightarrow \cdots \hookrightarrow \cov{r}{k}.\]
Letting $r$ and $k$ vary, the spaces $X_{r,k}$ assemble into an $\R\times \N^{\mathrm{op}}$-indexed bifiltration $X$, and the deformation retractions $X_{r,k}\to \cov{r}{k}$ assemble into an objectwise homotopy equivalence $X\to \covonly$.  Noting that the cover $\vorcov{r}{k}$ of each $\cov{r}{k}$ induces a cover $\vorcov{r}{k}\times I$ of $\cov{r}{k}\times I$ in the obvious way, we see that the covers $\{\vorcov{r}{i}\times I\}_{i=k}^n$ descend to a good cover of $X_{r,k}$, and these in turn assemble into a good cover of $X$.  It is easy to see that $\tcovonly$ is isomorphic to the persistent nerve of this cover.

*Truncations of S-Del.
When the point cloud is large, it may be computationally difficult to construct the full bifiltration $\tcovonly$.  We instead consider, for $\kmax\in\N$, the bifiltration $\tcovonly^{\leq\kmax}$ constructed in the same way, but  disregarding all order-$k$ Voronoi cells with $k>\kmax$,
\[\tcovonly^{\leq\kmax}_{r,k}:= \bigcup_{(\kmax-1) \geq i\geq k} \tdel{r}{i}.\]
Note that $\tcovonly^{\leq |A|}=\tcovonly$.
Viewing $\tcovonly^{\leq \kmax}$ as an $(\R\times \{1,\ldots,\kmax\})$-indexed bifiltration, the proof of <Ref> adapts immediately to show that $\tcovonly^{\leq \kmax}$ is weakly equivalent to the restriction of $\covonly$ to $\R\times \{1,\ldots,\kmax\}$.

*Size of S-Del.
By the size of a bifiltration $X$, we mean the number of simplices in the largest simplicial complex in $X$.
If the sites $A\subset \R^d$ are not in general position, the size of $\tcovonly^{\leq\kmax}$ can be huge; indeed, if all points of $A$ lie on a circle in $\R^2$ and $r$ is at least the radius of this circle, then $\del{r}{k}$ has $2^{|A|\choose k}$ simplices, so $\tcovonly^{\leq \kmax}$ is at least as large.  However, if $A$ is in general position, then the situation is far better:

Let $A\subset\R^d$ be a set of $n$ sites in general position, with a constant dimension $d$. Then $\tcovonly^{\leq \kmax}$ has size
$O(n^{ \floor*{\frac{d+1}{2}}} K^{\ceil*{\frac{d+1}{2}}})$.
In particular, $\tcovonly$ has size $O(n^{d+1})$.

In brief, the idea of the proof is to bound the
number of maximal simplices in $\tcovonly^{\leq \kmax}$
using a bound on the number of Voronoi vertices at levels $\leq k$ <cit.>.
The result then follows by observing that the dimension of the complex is a constant that only
depends on $d$. However, this dependence
on $d$ is doubly exponential, so the $O$-notation hides a large factor
if $d$ is large. See Appendix <ref> for details of the proof.

In contrast to <Ref>, the number of vertices in Sheehy's subdivision-Čech model <cit.>

grows exponentially with $|A|$, regardless of whether $A$ is in general position.

§ THE RHOMBOID BIFILTRATION

*The rhomboid tiling.

Let  $\Xp \subseteq \R^d$ be a finite set of sites in general position, and
$S$ an arbitrary $(d-1)$-sphere in $\R^d$.
Then $S$ yields a decomposition $\Xp=\Xin \sqcup \Xon \sqcup \Xout$
with $\Xin$ the sites in the interior of $S$, $\Xon$ the sites on the sphere,
and $\Xout$ the sites in the exterior of $S$. We define the combinatorial rhomboid of $S$ to be the collection of sets

\begin{equation}
\vx{S} := \left\{\Xin \cup \qv \mid \qv \subseteq \Xon\right\}.
\label{eqn:newvx}
\end{equation}

We call elements of $\vx{S}$ combinatorial vertices, and call

\begin{equation}
\rhomonly(\Xp) = \left\{\vx{S} \mid \text{$S$ is a sphere in $\R^d$}\right\}
\end{equation}

the (combinatorial) rhomboid tiling of $\Xp$.  Elements of $\rhomonly(\Xp)$ are called rhomboids.  Since $\Xp$ is fixed throughout,
we write $\rhomonly$ instead of $\rhomonly(\Xp)$.

As observed in <cit.>, the combinatorial rhomboid tiling can be geometrically
realized as a polyhedral cell complex <cit.>. For that, a combinatorial vertex $\{a_1,\ldots,a_k\}$
(where $a_1,\ldots,a_k$ are sites in $\R^d$) is embedded as $(\sum_{i=1}^k a_i,-k)$ in $\R^{d+1}$.
We call $k$ the depth of the vertex. Embedding a combinatorial rhomboid as the convex hull
of its embedded vertices yields an actual rhomboid in $\R^{d+1}$ whose dimension equals the cardinality of $\Xon$
in the corresponding partition of $\Xp$. The collection of these rhomboids is the (geometric) rhomboid tiling
for $\Xp$.
We illustrate the construction in Figure <ref>. In what follows, we identify
vertices and rhomboids with their combinatorial description. In particular, we will
use $\rhomonly$ both for the combinatorial and the geometric rhomboid tiling.

The rhomboid tiling of $5$ points on the real line.
The highlighted 2-rhomboid $\rho$ defined by $\xin{\rho} = \{c\}$ and $\xon{\rho} = \{b,d\}$
is the convex hull of the points $c$, $bc$, $cd$,
and $bcd$, simplifying the labels here and, e.g., writing $bcd$ instead of the cell complex associated to $\{b,c,d\}$.
The horizontal line at depth $k$ intersects the tiling in
the order-$k$ Delaunay mosaic.

The total number of cells (of all dimensions) in $\rhomonly$ is at most $\frac{2^{d+1}}{(d+1)!}|A+1|^{d+1}\leq 2|A+1|^{d+1}$.

For any rhomboid $\rho\in\rhomonly$, we let $r_\rho$ denote the infimal radius among all spheres $S$
for which $\vx{S}=\rho$. It is easily checked that if $\rho'$ is a subset of $\rho$, then $r_{\rho'}\leq r_{\rho}$,
and therefore, for any $r\geq 0$, the sublevel set
$\rhomonly_{r}=\{\rho\in\rhomonly\mid r_{\rho}\leq r\}$
is also a polyhedral complex.

Next, we slice the rhomboid tiling by cutting every rhomboid along the hyperplanes $\{x \in \R^{d+1} \mid -x_{d+1}=k\}$
with $k=0,\ldots,n$.
In this way, a rhomboid decomposes into its intersections with these hyperplanes and with slabs of the form $\{x \in \R^{d+1} \mid k\leq -x_{d+1}\leq k+1\}$.
Clearly, the resulting polyhedra again form a polyhedral complex
that we call the sliced rhomboid tiling $\trhomonly$.
We refer to its cells as sliced rhomboids.

For a sliced rhomboid $\rho$, we define $k_\rho$ as the minimum depth among its vertices. Moreover, there is a unique (unsliced) rhomboid $\rho'$ of smallest dimension
that contains $\rho$, and we define $r_\rho:=r_{\rho'}$. Define

\[
\trhom{r}{k}:=\{\rho\in\trhomonly\mid r_{\rho}\leq r, k_\rho\geq k\}
\]

and observe that for $r\leq r'$ and $k\geq k'$, we have $\trhom{r}{k}\subseteq\trhom{r'}{k'}$. Hence, $(\trhom{r}{k})_{(r,k)\in [0,\infty)\times\N}$
is a bifiltration of combinatorial cell complexes. Again, we will abuse notation and use the symbol $\trhomonly$ both for the sliced rhomboid tiling
and the bifiltration $(\trhom{r}{k})_{(r,k)\in [0,\infty)\times\N}$.   As shown in <cit.>, the restriction of   $\trhomonly$ to cells in the hyperplane $-x_{d+1}=k$ is the order-$k$ Delaunay mosaic, i.e., the geometric dual of the order-$k$ Voronoi diagram.

*Comparison of S-Rhomb and S-Del.

The following result establishes a close relationship between the bifiltrations $\trhomonly$ and $\tcovonly$:

For all $(r,k)\in [0,\infty)\times\N$,

* The vertex sets of $\trhom{r}{k}$ and $\tcov{r}{k}$ are equal.

* The vertices of each sliced rhomboid in $\trhom{r}{k}$ span a simplex in $\tcov{r}{k}$.

* The vertices of each simplex in $\tcov{r}{k}$ are contained in a sliced rhomboid of $\trhom{r}{k}$.

For the first part, note that a set $v=\{a_1,\ldots,a_k\}$ of sites is a vertex in $\trhomonly$ if and only if there is a sphere $S$ that decomposes the sites into $\Xp=\Xin \sqcup \Xon \sqcup \Xout$ such that $\Xin\subseteq v\subseteq\Xin\cup\Xon$.  Such a sphere exists if and only if its center has $v$ among its $k$ closest sites, which is equivalent to the condition that the order-$k$
Voronoi region $\vorreg{v}$ is not empty. A slightly more careful analysis shows that the vertices of $\trhom{r}{k}$ and $\tcov{r}{k}$ are also the same for any choice
of $r$ and $k$.

For the second part, let $v_1,\ldots,v_m$ denote the vertices of a sliced rhomboid in $\trhom{r}{k}$.
Let $\rho$ denote the smallest rhomboid of $\rhomonly$ containing this sliced rhomboid, and let $S$ denote a sphere of radius $\leq r$ that gives rise to $\rho$.
Let $x$ denote the center of $S$ and $\Xp=\Xin \sqcup \Xon \sqcup \Xout$ be the decomposition with respect to $S$.
Now, each $v_i$ is the union of $\Xin$ with a subset of $\Xon$, and hence, the point
$x$ belongs to the Voronoi region of $v_i$. Since $i$ is arbitrary, it follows that all Voronoi
regions intersect, and $x$ has distance $\leq r$ to each $v_i$, so $v_1,\ldots,v_m$ span a simplex in $\tcov{r}{k}$.

For the third part, consider vertices $v_1,\ldots,v_m$ that span a simplex in $\tcov{r}{k}$.
Assume that some $v_i$ has order $k'\geq k$ and that the remaining vertices are of order $k'$ or $k'-1$.
Since $v_1,\ldots,v_m$ span a simplex, the corresponding higher-order Voronoi regions, intersected with balls of radius $r$ around the involved sites, have non-empty intersection.  Choose such a point $x\in \R^d$.  Define $S$ as the smallest sphere centered at $x$ that includes $k'$ sites (either on the sphere or in its interior). $S$ induces a partition $\Xp=\Xin \sqcup \Xon \sqcup \Xout$ and a rhomboid $\rho$.
Each vertex $v_i$ of order $k'$ must contain all sites of $\Xin$, and some subset of the sites of $\Xon$, meaning that $v_i$ is in $\rho$.
Furthermore, at least one site lies on $S$; otherwise, there would be a smaller sphere.
This implies that each vertex $v_j$ of order $k'-1$ also has to contain all sites of $\Xin$ and some subset of $\Xon$.
Thus, all vertices lie in $\rho$, and in particular in its $(k'-1,k')$-slice.
Finally, observe that because one of the sites lies on $S$, the radius of $S$ is the distance
of that site to $x$, which is at most $r$.

Parts 1 and 2 of <Ref> establish that we have a vertex-preserving injection $\mathcal J$ from the cells of $\trhom{r}{k}$ to the simplices of $\tcov{r}{k}$.  Moreover, the third part of <Ref> implies that $\mathcal J$ restricts to a bijection from the maximal cells of $\trhom{r}{k}$ to the maximal simplices of $\tcov{r}{k}$.

We note that $\mathcal J$ does not preserve dimension:  For $\nu$ a cell of $\trhomonly$ spanned by vertices of cardinality $k$  (i.e., a cell in the order-$k$ Delaunay mosaic), we have $\dim(\nu)\leq d$.  But if $d\geq 3$, it can be that $\dim(\mathcal J(\nu))>d$, even when the sites are in general position. For a cell $\nu$ of $\trhom{r}{k}$ spanned by vertices of cardinality $k$ and $k+1$, we may have $\dim(\nu)\ne \dim(\mathcal J(\nu))$ even for $d=2$, see Figure <ref>.

An illustration of the difference between  $\tcovonly$ and $\trhomonly$ for three points in the plane.
The order-$1$ Voronoi regions of the points $\{x\}$, $\{y\}$, and $\{z\}$ intersect in $c$, as do the order-$2$ Voronoi regions of $\{x,y\}$, $\{y,z\}$, and $\{x,z\}$. Consequently, $\tcovonly$ contains a $5$-simplex, but the corresponding cell in $\trhomonly$ on the same vertex set is a $3$-dimensional triangular skew prism.

The bifiltrations $\trhomonly$ and $\tcovonly$ are weakly equivalent.

We define good covers

of both bifiltrations: First, for $\trhom{r}{k}$, we choose the cover that
consists of all its cells. This is a good cover because the cells are convex. The collection
of these covers over all choices of $r$ and $k$ yields a good cover $\mathcal{U}$ of the bifiltration $\trhomonly$, and the Persistent Nerve Theorem then gives objectwise homotopy equivalences

\[
\begin{tikzcd}
\trhomonly  &  \arrow[labels=above]{l}{\simeq} \arrow{r}{\simeq} \deltaspace{\mathcal{U}}{\trhomonly}  & \nerve(\mathcal{U}).
\end{tikzcd}
\]

for some intermediate bifiltration $\deltaspace{\mathcal{U}}{\trhomonly}$.

Moreover, we obtain a cover $\mathcal{V}_{r,k}$ of $\tcov{r}{k}$ whose elements are the simplices
spanned by the vertices of the sliced rhomboids in $\trhom{r}{k}$.
By the second part of Lemma <ref>,
these cover elements indeed exist. Moreover, in view of <Ref>, every maximal simplex of  $\tcov{r}{k}$ is an element of $\mathcal{V}_{r,k}$.  We thus obtain a good cover $\mathcal{V}$ of $\tcovonly$.  Applying the Persistent Nerve Theorem again, we obtain objectwise homotopy equivalences

\[
\begin{tikzcd}
\tcovonly  &  \arrow[labels=above]{l}{\simeq} \arrow{r}{\simeq} \deltaspace{\mathcal{V}}{\tcovonly}  & \nerve(\mathcal{V}).
\end{tikzcd}
\]

Finally, $\nerve(\mathcal{U})$ and $\nerve(\mathcal{V})$ are isomorphic: The elements of $\mathcal{U}$ and of $\mathcal{V}$ are in 1-to-1 correspondence (with corresponding cover elements having the same vertex set). In both cases, an intersection of cover elements is non-empty if and only if the elements share a vertex, which is determined
by their vertex sets. Hence, we have objectwise homotopy equivalences

\[
\begin{tikzcd}
\trhomonly  &  \arrow[labels=above]{l}{\simeq} \arrow{r}{\simeq} \deltaspace{\mathcal{U}}{\trhomonly}  & \nerve(\mathcal{U}) \arrow["\cong"]{r} & \nerve(\mathcal{V}) &  \arrow[labels=above]{l}{\simeq} \arrow{r}{\simeq} \deltaspace{\mathcal{V}}{\tcovonly}  & \tcovonly.
\end{tikzcd}\qedhere
\]

*Unslicing the rhomboid.

Next, we define a bifiltration on the (unsliced) rhomboid tiling. Recall that for a rhomboid $\rho$,
we already defined $r_\rho$ as the radius of the smallest sphere that gives rise to that rhomboid.
As in the sliced version, we define $k_\rho$ as the minimal depth among the vertices of $\rho$,
and $\Rhomboid{r}{k}:=\{\rho\mid r_\rho\leq r, k_\rho\geq k\}$.
This yields a bifiltration $(\Rhomboid{r}{k})_{(r,k)\in [0,\infty)\times\N}$,
which we denote by $\rhomonly$.

The bifiltrations $\rhomonly$ and $\trhomonly$ are weakly equivalent.

For a rhomboid $\rho$ in $\rhomonly$,
set $\altkmin$ as the minimal depth and $\altkmax$ as the maximal depth among the vertices in $\rho$;
note that $k_\rho=\altkmin$.
For $r$ and $k$ fixed, we call $\rho$ dangling
if $r_\rho\leq r$ and $\altkmin < k < \altkmax$.
Note that $\rho$ is not contained in $\Rhomboid{r}{k}$ in this case, but some of its slices
are contained in $\trhom{r}{k}$. Moreover, the only difference between
$\Rhomboid{r}{k}$ and $\trhom{r}{k}$ are slices of dangling rhomboids in $\trhom{r}{k}$.

Now, observe that for a dangling rhomboid of maximal dimension, there is a deformation retraction
that “pushes in” the slices of the dangling rhomboid, leaving the boundaries of the slices unchanged
and removing the entire interior part.
Applying this deformation retraction for all maximal-dimensional rhomboids in parallel,
and repeating the process for the next lower dimension yields a deformation retraction from $\trhom{r}{k}$
to $\Rhomboid{r}{k}$. This implies that for every choice of $r$ and $k$, the inclusion $\Rhomboid{r}{k}\hookrightarrow \trhom{r}{k}$ is a homotopy equivalence.
Moreover, these inclusions commute with the inclusion maps in $\rhomonly$ and $\trhomonly$, hence define an objectwise homotopy equivalence.

Combining the previous lemma with Theorem <ref> and Theorem <ref> yields the following result:

The bifiltrations $\rhomonly$ and $\covonly$ are weakly equivalent.

In view of <Ref>, $\rhomonly$ has at most $2|A+1|^{d+1}=O(|A|^{d+1})$ cells.

One can also bound the size of a truncated version of $\rhomonly$, defined analogously to the truncation of $\tcovonly$ considered in <Ref>.  Indeed, $\rhomonly$ is clearly smaller (in terms of number of cells) than $\trhomonly$, and by <Ref>, $\trhomonly$ is at least as small as $\tcovonly$.  Moreover, this extends to truncations of these bifiltrations.  Thus, the bound of <Ref> also holds for truncations of $\rhomonly$.

§ EXPERIMENTS

The algorithm from <cit.> computes the rhomboids of the rhomboid tiling
and their associated radius values. We extended its implementation rhomboidtiling[<https://github.com/geoo89/rhomboidtiling>] to compute the sliced and unsliced bifiltrations $\trhomonly$ and $\rhomonly$ and their free implicit representations (FIREP) <cit.>.  The implementation of  rhomboidtiling is in C++, using the Cgal library[CGAL, Computational Geometry Algorithms Library, <https://www.cgal.org>] for geometric primitives. The current version accepts only 2- and 3-dimensional inputs, but all steps readily generalize to higher dimensions; adding support for higher-dimensional inputs is a matter of software design rather than algorithm development.

We performed experiments on point sets in $\R^2$ and $\R^3$.  We provide a brief summary here; for detailed results, see Appendix <ref>.  We sampled points uniformly at random from $[0,1]^2$ and $[0,1]^3$, from a disk, from an annulus, and from an annulus with additional noise.  We computed the rhomboid bifiltrations  $\rhomonly^{\leq\kmax}$ and  $\trhomonly^{\leq\kmax}$.  We then used mpfree[<https://bitbucket.org/mkerber/mpfree>] to compute minimal presentations of 2-parameter persistent homology of our bifiltrations.

In one set of experiments, we found that $\rhomonly^{\leq\kmax}$  is up to 47% smaller than $\trhomonly^{\leq\kmax}$, and can be computed more than 20% faster.  The experiments suggest that the relative performance of $\rhomonly^{\leq\kmax}$ improves with increasing $\kmax$.

An illustration of the first Hilbert function of the multicover bifiltration, using grayscale shading.  The instances are samples of an annulus (top), a noisy annulus (middle), and a disk (bottom). The sample size is 100 in the left column, and 200 in the right column.  Darkness of the shading is proportional to the value of the Hilbert function, up to some maximum value, above which the shading is taken to be black; the lightest non-white shade of gray corresponds to a Hilbert function value of 1.

We investigated the size of $\rhomonly^{\leq\kmax}$,
varying the sample size and the density parameter.
For $d=2$, our experiments show a clear subquadratic growth of the size of $\rhomonly^{\leq\kmax}$ and its FIREP with respect to increasing $\kmax$. For $d=3$, the growth is clearly subcubic. These observations also extend to time complexity.

Letting the number of points increase, the size of $\rhomonly^{\leq\kmax}$ and its FIREP shows roughly linear growth for both space dimensions, with a slight superlinear tendency. Again, we observed the same behavior for the computation time.

We conclude this section with a data visualization enabled by the ideas of this paper: For $i\geq 0$, the $i$-th Hilbert function assigns to each parameter $(r,k)\in \R\times \N$ the rank of $i$-th homology module of $\cov{r}{k}$ (with coefficients in some fixed field). The Hilbert functions are well known to be unstable invariants.  Nevertheless, their visualization can give us a feel for how the Lipschitz stability property of the multicover bifiltration established in <cit.> manifests itself in random data.  Figure <ref> shows a few examples, plotted using rivet[<https://github.com/rivetTDA/>].

§ CONCLUSION

We have introduced a simplicial model for the multicover bifiltration, as well as a polyhedral model based on the rhomboid tiling <cit.>.  For a data set of size $n$ in $\R^d$ with $d$ constant, the size of both constructions is $O(n^{d+1})$.  The size can be further controlled by thresholding the parameter $k$ of the multicover bifiltration.  A recently introduced algorithm for computing the rhomboid tiling <cit.> extends readily to the computation of the polyhedral bifiltration, and we have implemented this extension.  In our experimental results, this approach scales well enough to suggest that practical applications could soon be within reach.  A natural next step is to begin exploring the use of the multicover bifiltration on real world data.

To obtain our combinatorial models of the multicover bifiltration, we begin with a zigzag of filtrations, and then straighten it out by taking unions of prefixes.  Notably, one could in principle compute the persistent homology modules of the multicover bifiltration without straightening out the zigzag, by inverting the isomorphisms on homology induced by the inclusions $\del{r}{k}\hookrightarrow \tdel{r}{k}$.   It seems plausible that this approach could be computationally useful.

We are curious to learn which indecomposables typically arise in the persistent homology modules of multicover bifiltration, and our approach could be used in conjunction with existing algorithms <cit.> to study this.  It would also be interesting to investigate whether there is an interplay between the geometry of a space and the multicover bifiltration of a noisy sample of this space; we wonder if invariants of the bifiltration encode additional information about geometric properties, such as the reach or differentiability.

Our experiments show a significant increase in the size of our models of multicover bifiltration for increasing $\kmax$.   This suggests the need for refinements to our algorithmic approach in order to handle large values of $\kmax$.
Aside from the truncations considered in this paper, there are a couple of promising ways forward: One could construct a coarsened bifiltration where some values of $k$ are skipped.  Alternatively, one could make use of the inductive nature of our constructions: for the step from $k$ to $k+1$, one does not need information about the bifiltrations at indices $j<k$. Therefore, one could provide the bifiltration as an output stream without storing it completely in memory. Subsequent algorithmic steps would then have to be implemented as streaming algorithms as well.

§ PROOF OF PROPOSITION 5

For $k\in \N$, and a bifiltration $X$, we let $X_{\infty,k}$ denote the largest simplicial complex of the form $X_{r,k}$, provided this exists.

If $A\subset\R^d$ is in general position, then for all $k\in \N$, we have

\[
\dim(\del{\infty}{k})%\leq {d+1 \choose k}-1
\leq {d+1 \choose \floor*{\frac{d+1}{2}}}.
\]

A simplex $\sigma\in \del{\infty}{k}$ is a set of order-$k$ Voronoi regions with a point of common intersection. Let $x$ be such a point.  Each order-$k$ Voronoi region $R\in \sigma$ is indexed by a subset of $A$, which we denote as $\mathrm{sites}(R)$.  Let

\begin{align*}
s&=\min\{r\geq 0\mid x\in \cov{r}{k}\},\\
A_{on}&=\{p\in A\mid \|p-x\|=s\}, \\
A_{in}&=\{p\in A\mid \|p-x\|<s\}.
\end{align*}

Clearly, $|A_{in}|<k$, and by the assumption of general position, we also have $|A_{on}|\leq d+1$.  Moreover, for all $R\in \sigma$, we have $A_{in}\subset \mathrm{sites}(R)$ and $\mathrm{sites}(R)\subset A_{in}\cup A_{on}$.
\[\dim(\sigma)={|A_{on}| \choose k-|A_{in}|}-1\leq  {d+1\choose k-|A_{in}|}\leq {d+1 \choose \floor*{\frac{d+1}{2}}}.\qedhere\]

If $A\subset\R^d$ is in general position, then for all $\kmax\in \N$, we have

\[\dim(\tcovonly^{\leq\kmax})\leq 2{d+1 \choose \floor*{\frac{d+1}{2}}}.\]

We first observe that

\[\dim(\tdel{\infty}{k})\leq \dim(\del{\infty}{k})+\dim(\del{\infty}{k+1})\leq 2 {d+1 \choose \floor*{\frac{d+1}{2}}},\]

by noting that the dimension on the left is upper bounded by the sum of the
maximal number of order-$k$ Voronoi regions and order-$(k+1)$ Voronoi regions
that meet at a fixed point in $\R^d$. Since these two summands equal
$\dim(\del{\infty}{k})-1$ and $\dim(\del{\infty}{k+1})-1$, we have the first
inequality, and the second one follows from the previous <Ref>.  Since each simplicial complex in $\tcovonly^{\leq\kmax}$ is a union of simplicial complexes $\tdel{r}{k}$, it follows that

\[\dim(\tcovonly^{\leq\kmax})\leq 2{d+1 \choose \floor*{\frac{d+1}{2}}},\]

as desired.

For any $k\in \N$, the number of maximal simplices in $\tdel{\infty}{k}$ is at most $V_k+V_{k+1}$, where $V_k$, $V_{k+1}$ denote
the number of Voronoi vertices at level $k$ or $k+1$, respectively.

Recall the definition

\[
\tdel{\infty}{k}:=\nerve\left( \vorcov{\infty}{k} \cup \vorcov{\infty}{k+1} \right),
\]

where both $\vorcov{\infty}{k}$ and $\vorcov{\infty}{k+1}$ are simply the
set of Voronoi regions of order-$k$ and order-$(k+1)$, respectively.
They are both polyhedral subdivisions of $\R^d$, and we consider the overlay of these subdivisions, which is the subdivision induced by the
non-empty full-dimensional intersections of an order-$k$ Voronoi region
with an order $(k+1)$ Voronoi region. For every simplex $\sigma$
of $\tdel{\infty}{k}$, we can find a cell in this overlay
such that all Voronoi regions in $\sigma$ intersect at the points of this cell.
Moreover, every cell in the overlay is bounded by a vertex
(because the same is true for the individual Voronoi diagrams, provided
that the number of sites is at least $d+1$). We conclude
that the maximal simplices of $\tdel{\infty}{k}$ are in one-to-one correspondence with the vertices of the overlay.

The main observation is that the vertices of the overlay
are precisely the union of the vertices of the order-$k$
and order-$(k+1)$ Voronoi diagram.
One way to see that is to observe that the overlay
can be constructed
out of the order-$k$ Voronoi diagram solely by subdividing full-dimensional
polytopes (i.e, the order-$k$ Voronoi regions) into subregions.
This subdivision is obtained by subdividing a Voronoi region for a
$k$-set $S$ of sites with respect to the order-$1$ Voronoi diagram
of the remaining sites $A\setminus S$. In particular, the overlay does
not subdivide any Voronoi cell of order $k$ that is not full-dimensional
which implies that no new vertex is created. The reason for that is
that a Voronoi cell of order $k$ that is neither a vertex nor full-dimensional
either involves exactly $k+1$ sites, in which case it lies in a
full-dimensional $(k+1)$-Voronoi region (and thus does not get subdivided), or it involves more than $k+1$ sites, in which case it also constitutes
a Voronoi cell of order $(k+1)$.

With this observation, we conclude that the number of maximal simplices
in $\tdel{\infty}{k}$ is at most $V_k+V_{k+1}$ as desired.

Since $\tcovonly^{\leq\kmax}$ is the union of $\tdel{\infty}{k}$
for $k=1,\ldots,\kmax-1$,
we have that the number of its maximal simplices is at most

\[(V_1+V_2)+(V_2+V_3)+\ldots + (V_{\kmax-1}+V_{\kmax})\leq 2 V_{\leq\kmax}\]

with Lemma <ref>, where $V_{\leq\kmax}$ is the number of Voronoi vertices at levels $\leq k$.
Since the number of simplices of a $d$-dimensional simplicial complex with $m$
maximal simplices is at most $2^{d+1}m$, we obtain an upper bound of

\[
(2{d+1 \choose \floor*{\frac{d+1}{2}}}+1) \cdot V_{\leq\kmax}
\]

for the size of $\tcovonly^{\leq \kmax}$ with Lemma <ref>.
Since the dimension bound only depends on the constant $d$, it is therefore
enough to bound $V_{\leq\kmax}$.

By a result of Clarkson and Shor <cit.>,
we have that $e_{\leq\kmax}$, the number of Voronoi regions (i.e., $d$-dimensional Voronoi cells) at levels $\leq\kmax$ is

\[e_{\leq\kmax}=O(|A|^{ \floor*{\frac{d+1}{2}}} \kmax^{\ceil*{\frac{d+1}{2}}}).\]

(This bound hides a constant that depends doubly exponentially on $d$.)
Moreover, by a combinatorial counting argument, as exposed in <cit.>, we have that the total size of the Voronoi diagram
at level $k$ is bounded by

\[
O(\mathrm{max}\{e_i\mid k-d+1\leq i\leq k+d-2\})
\]

with $e_i$ the number of Voronoi regions at level $k$.
The same bound applies to $V_{k}$ as well. A simple calculation shows
that $V_{\leq \kmax}$ is then bounded by $(2d-3)e_{\leq \kmax}=O(e_\leq\kmax)$.

The bound of <Ref> can also be proved via our correspondence with the rhomboid tiling in Section <ref>.
The Clarkson-Shor bound provides the same size bound for the number of $(d+1)$-dimensional rhomboids of level up to $\kmax-1$. Note that each maximal cell of $\trhomonly^{\leq\kmax}$ is the intersection of a $(d+1)$-dimensional rhomboid at depth $\leq \kmax-1$ with a slab $\{x \in \R^{d+1} \mid k\leq -x_{d+1}\leq k+1\}$ for some integer $k$. Slicing the rhomboids
as in Section <ref> yields a multiplicative factor of $d+1$
that is absorbed by $O$-notation. Finally, by <Ref>
we have that the sliced $(d+1)$-dimensional rhomboids are in one-to-one
correspondence with the maximal simplices of $\tcovonly^{\leq \kmax}$.
We omit further details.

§ DETAILS ON EXPERIMENTS

Let us mention an important technicality in our pipeline for computing minimal presentations: In order to limit the size of the minimal presentations, we “snap” the radius values of all generators and relations onto a set of 100 evenly spaced points in $\R$.  The values of the parameter $k$ are left unchanged.  This snapping is done only after the minimal presentation is computed.  The snapping process in fact can make a minimal presentation non-minimal, so after snapping, we re-minimize the presentation.  All reported results below are for minimal presentations computed using this pipeline.  The Hilbert functions shown in <Ref> were also computed from such “snapped" presentations.

*Experimental output.

We present the concrete outcome of some of our experiments.
All results are averaged
over $5$ runs with independently generated data sets.  The sizes reflect  the number of elements of the corresponding set, and the times were measured in seconds.

We give a brief overview of the experiments, referring to the tables for further details.  We were curious about the practical improvements from $\trhomonly$ to $\rhomonly$. We documented these for a few values of $n$ and $\kmax$ in the plane. The sizes of their truncated versions both grow linearly in the number of points. See Table <ref> for more refined results. In further experiments, we only used $\rhomonly$.

Table <ref> shows the behavior of fixed $\kmax$ and an increasing number of uniformly sampled points. Conversely, Table <ref> documents the behavior of $\rhomonly$ in an experiment with a fixed number of points and increasing $\kmax$. Both in dimension $2$ and $3$, we investigated the size of the bifiltration, the size of the FIREPs, and the size of minimal presentations thereof. We also kept track of the time needed for the computations.

Finally, we wondered how the measurements change when data sets are sampled from a particular shape. As an example, we sampled points from an annulus with random but bounded perturbations and added uniform background noise to it. Letting both the range of the perturbations and the portion of the background noise vary, we tracked the size of the minimal presentations in Table <ref>.

2|c|$d=2$     3cFIREP ($\trhomonly^{\leq\kmax}$)     3|c|FIREP ($\rhomonly^{\leq\kmax}$)      2c|

$n$     $\kmax$
size     time     $\frac{\textnormal{size}}{n\cdot\kmax^2}$

size       time     $\frac{\textnormal{size}}{n\cdot\kmax^2}$
$\frac{\textnormal{size (u)}}{\textnormal{size (s)}}$     $\frac{\textnormal{time (u)}}{\textnormal{time (s)}}$

10,000     4

1.916 M     25.67     12.0

1.197 M     19.49      7.48
62%      76%

20,000     4

3.836 M     50.79     12.0

2.397 M     40.11     7.49
62%     79%

40,000     4

7.676 M     107.44     12.0

4.797 M     84.21     7.49
62%     78%

80,000     4

15.355 M     228.29     12.0

8.597 M     179.45     6.71
56%     78%

10,000     8

8.249 M     106.90     12.9

4.344 M     77.30     6.79
53%     72%

20,000     8

16.528 M     231.75     12.9

8.702 M     166.55    6.80
53%     72%

40,000     8

17.709 M     475.51     6.95

15.265 M     346.67     5.97
86%     73 %

80,000     8

17.718 M     1,010.44     3.46

13.835 M     746.48    2.70
78%     74%

We compare the sizes of FIREPs of $\trhomonly^{\leq\kmax}$ and $\rhomonly^{\leq\kmax}$. We considered $n$ uniformly sampled points in the unit square. The FIREPs of the unsliced bifiltration show 63% of the size of FIREPs of the sliced version for $d=2$, and 54% for  $d=3$. That advantage seems to get smaller for a sufficiently large number of points.  Computing the unsliced version has revealed to be more than 20% faster for $K=4$ and to be more than 25% faster for $K=8$ in this experiment. A generalization of these findings would describe the computational value of $\rhomonly$ more accurately.

2|c|     2|c|$\rhomonly^{\leq\kmax}$     4c|FIREP     2c|snapped minpres

$d$     $n$     size      $\frac{\textnormal{size}}{n\cdot\kmax^3}$       size      $\frac{\textnormal{size}}{n\cdot\kmax^2}$       time     $\frac{10^4\cdot\textnormal{time}}{ n\cdot\kmax^3}$     size     time

2     1,250     0.192 M     9.60     0.148 M     7.40     1.95     3.90     0.0182 M     1.58

2     2,500     0.387 M     9.68     0.297 M     7.43     6.52     1.60     0.0373 M     4.56

2     5,000     0.777 M     9.71     0.598 M     7.48     9.30     1.16     0.0749 M     6.61

2     10,000     1.56 M     9.75     12.0 M     7.50     20.13     1.26     0.152 M     15.36

2     20,000     3.12 M     9.75     2.40 M     7.5     40.36     1.26     0.281 M     32.39

$d$     $n$     size      $\frac{\textnormal{size}}{n\cdot\kmax^3}$       size      $\frac{\textnormal{size}}{n\cdot\kmax^3}$       time     $\frac{10^4\cdot\textnormal{time}}{5\cdot n\cdot\kmax^3}$     size     time

3     1,250     2.28 M      28.50     1.42 M     17.75     45.39     1.13     0.0806 M     10.39

3     2,500     4.68 M      29.25     2.92 M     18.25     95.76     1.20     0.176 M     24.34

3     5,000     9.49 M      29.66     5.91 M     18.47     202.92     1.27     0.360 M     58.35

3     10,000     19.2 M     30.00     12.0 M     18.75     431.58     1.35     0.739 M     142.12

3     20,000     38.7 M     30.23     24.1 M     18.83     904.42     1.41     1.52 M     378.25

Results on $n$ uniformly sampled points in the unit square and unit cube, using $\kmax=4$ as maximal value for $k$. The size of the bifiltration and the FIREP grows slightly superlinear in the documented scale window. The computation time seems to be of the same complexity.

2|c|     2c|$\rhomonly^{\leq\kmax}$     4cFIREP     3|c|snapped minpres

$d$     $\kmax$     size     $\frac{\textnormal{size}}{n\cdot\kmax^2}$      size      $\frac{\textnormal{size}}{n\cdot\kmax^2}$      time     $\frac{10^5\cdot\textnormal{time}}{n\cdot\kmax^2}$     size     time     $\frac{\textnormal{size}}{\textnormal{FIREP size}}$

2     2     0.0216  M     10.8     0.0167 M     8.35     0.26      1.30      1.67 K     0.29     10.0%

2     4     0.0758 M      9.48     0.0583 M     7.29     0.76      0.95      7.08 K     0.74      12.1%

2     8      0.272 M     8.50     0.207 M     6.47     3.14      0.98      23.6 K     2.13      11.4%

2     16     0.997 M      7.79     0.755 M     5.90      12.53      0.98      74.7 K     7.47      9.89%

$d$     $\kmax$     size      $\frac{\textnormal{size}}{n\cdot\kmax^3}$       size      $\frac{\textnormal{size}}{n\cdot\kmax^3}$       time     $\frac{10^5\cdot\textnormal{time}}{5\cdot n\cdot\kmax^3}$     size     time     $\frac{\textnormal{size}}{\textnormal{FIREP size}}$

3     2      0.144 M      36.0      0.0860 M      21.5      2.30      1.15      5.70 K     0.86      6.63%

3     4      0.863 M      27.0     0.539 M    16.8     16.1     1.00     30.8 K     3.74     5.71%

3     8      5.33 M     20.8     3.36 M      13.1       122      0.95     146 K     23.7     4.34%

3     16      34.0 M     16.6     21.4 M     10.4      1,006      0.98     627 K     192     2.93%

Results on 500 uniformly sampled points in the unit square and unit cube. The sizes of the bifiltration and its FIREP grow clearly subquadratic for $d=2$, and clearly subcubic for $d=3$. The running times seem close to being quadratic and cubic in dimensions 2 and 3, respectively. We also measured the relation of the sizes of the snapped minimal presentations and FIREPs.

p     $err$     snapped minpres size     relative size

1     0.01      2,015
0.38 %

1     0.04      1,691
0.32 %

1     0.08      1,526
0.29 %

1     0.12       5,497
1.0 %

1     0.14        16,183
3.1 %

1     0.16      29,988
5.7 %

4     0.01      14,389
2.7 %

4     0.04       12,852
2.4 %

4     0.08      15,198
2.9 %

4     0.12      18,457
3.5 %

4     0.16      43,917
8.3 %

16     0.01      70,901
13 %

16     0.04       84,142
16 %

16     0.08      99,782

16     0.16      146,170

64     0.01       344,847
65 %

64     0.04      365,308
69 %

64     0.08      416,522
79 %

64     0.16       427,697
80 %

100     -      529,128
100 %

We sampled points of an annulus around a circle of radius $0.25$. In total, we have 10,000 points whereas $p\%$ of these points are uniform noise in the surrounding box $[0,1]^2$. The other points are sampled with a random perturbation per coordinate bounded by a number $err$. We considered $\kmax=8$ as maximal value for $k$. The size of the snapped minimal presentation increases when adding more uniform noise. It may increase more drastically within a certain range of $p$, i.e., for $p\in\{1,4\}$, starting at about at 0.12. We also observed a considerable variance of the individual results in such areas. In particular, the size of the snapped minimal presentations is neither a linear, nor a sub- or superlinear process. We regard this process mostly as a property of the snapping technique. Furthermore, when $p$ is not too big, the perturbations around each sampled point can be quite high, i.e., for $p\leq 4$ and $err=0.16$, the snapped minimal presentations are still of relative size $5.7\%$ and $8.3\%$, respectively. Note that the samples only stay inside the surrounding box  $[0,1]^2$ if $err\leq 0.25$.