---
abstract: |
    A filtration over a simplicial complex $K$ is an ordering of the simplices of $K$ such that all prefixes in the ordering are subcomplexes of $K$. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. In order to represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree \[Algorithmica ’14\]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest.\
    This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. \[SoCG ’15\] considered storing the simplices that are maximal for the inclusion and Attali et al. \[IJCGA ’12\] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the *filtration* of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex.\
    In this paper, we propose a new data structure called the Critical Simplex Diagram (CSD) which is a variant of the Simplex Array List (SAL) \[SoCG ’15\]. Our data structure allows to store in a compact way the filtration of a simplicial complex, and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Next, we show that the CSD representation admits the following construction algorithms.

    -   A new *edge-deletion* algorithm for the fast construction of Flag complexes, which only depends on the number of critical simplices and the number of vertices.

    -   A new *matrix-parsing* algorithm to quickly construct relaxed Delaunay complexes, depending only on the number of witnesses and the dimension of the complex.

author:
- |
    Jean-Daniel Boissonnat[^1]\
    INRIA Sophia Antipolis - Méditerranée, France.\
    `Jean-Daniel.Boissonnat@inria.fr`.
- |
    Karthik C. S.[^2]\
    Department of Computer Science and Applied Mathematics,\
    Weizmann Institute of Science, Israel.\
    `karthik.srikanta@weizmann.ac.il`.
bibliography:
- 'References.bib'
title: '**An Efficient Representation for Filtrations of Simplicial Complexes**'
---

Introduction
============

Persistent homology is a method for computing the topological features of a space at different spatial resolutions [@EH10]. More persistent features are detected over a wide range of length and are deemed more likely to represent true features of the underlying space, rather than artifacts of sampling, noise, or particular choice of parameters. To find the persistent homology of a space [@BDM15; @BM14], the space is represented as a sequence of simplicial complexes called a filtration. The most popular filtrations are nested sequences of increasing simplicial complexes but more advanced types of filtrations have been studied where consecutive complexes are mapped using more general simplicial maps [@DFW14]. Persistent homology found applications in many areas ranging from image analysis [@CIDZ08; @PC14], to cancer research [@ABDMPP12], virology [@CCR13], and sensor networks [@DG07].

Thus, a central question in Computational Topology and Topological Data Analysis is to represent simplicial complexes and filtrations efficiently. The most common representation of simplicial complexes uses the Hasse diagram of the complex that has one node per simplex and an edge between any pair of incident simplices whose dimensions differ by one. A more compact data structure, called Simplex Tree (ST), was proposed recently by Boissonnat and Maria [@SimplexTree]. The nodes of both the Hasse diagram and ST are in bijection with the simplices (of all dimensions) of the simplicial complex. In this way, they explicitly store all the simplices of the complex and it is easy to attach information to each simplex (such as a filtration value). In particular, they allow to store in a natural way the filtration of complexes which are at the core of Persistent Homology and Topological Data Analysis.

However, such data structures are redundant and typically very big, and they are not sensitive to the underlying structure of the complexes. This motivated the design of more compact data structures that represent only a sufficient subset of the simplices. A first idea is to store the 1-skeleton of the complex together with a set of blockers that prevent the expansion of the complex [@DataStructure3]. A dual idea is to store only the simplices that are maximal for the inclusion. Following this last idea, Boissonnat et al. [@BKT15] introduced a new data structure, called Simplex Array List, which was the first data structure whose size and query time were sensitive to the geometry of the simplicial complex. SAL was shown to outperform ST for a large class of simplicial complexes.

Although very efficient, SAL, as well as data structures that do not explicitly store all the simplices of a complex, makes the representation of filtrations problematic, and in the case of SAL, impossible. In this paper, we introduce a new data structure called Critical Simplex Diagram (CSD) which has some similarity with SAL. CSD only stores the critical simplices, i.e., those simplices all of whose cofaces have a higher filtration value, and in this paper, we overcome the problems arising due to the implicit representation of simplicial complexes, by showing that the basic operations on simplicial complexes can be performed efficiently using CSD. In short, CSD compromises on the membership query (which is slightly worse than that for ST) in order to save storage and to perform insertion and removal efficiently.

Our Contribution
----------------

At a high level, our main contribution through this paper is in developing a new perspective for the design of data structures representing simplicial complexes associated with a filtration. Previous data structures such as Hasse diagram and Simplex Tree interpreted a simplicial complex as a set of strings defined over the label set of its vertices and the filtration values as keys associated with each string. When a simplicial complex is perceived this way, a Trie is indeed a natural data structure to represent the complex. However, this way of representing simplicial complexes doesn’t make use of the fact that simplicial complexes are not arbitrary sets of strings but are constrained by a lot of combinatorial structure. In particular, simplicial complexes are closed under subsets and also (standard) filtrations are monotone functions. We exploit these constraints/structure by viewing a filtered simplicial complex with filtration range of size $t$ as a monotone function from $\{0,1\}^{|V|}$ to $\{0,1,\ldots,t\}$, where $V$ is the vertex set. We note that if a simplex is mapped to $t$ then, the simplex is understood to be not in the complex and if not, the mapping is taken to correspond to the filtration value of the simplex. In light of this viewpoint, we propose a data structure (CSD) which stores only the critical elements in the domain, i.e. those elements all of whose supersets (cofaces in the complex) are mapped to a strictly larger value. As a result, we are not only able to store data regarding a simplicial complex more efficiently but also explicitly utilize geometric regularity in the complex which would have been otherwise obscured. More concretely, we have the following result.

\[main\] Let $K$ be a $d$-dimensional simplicial complex. Let $\kappa$ be the number of critical simplices in the complex. The data structure CSD representing $K$ admits the following properties:

-   The size of CSD is at most $\kappa d$.

-   The cost of basic operations (such as membership, insertion, removal, elementary collapse, etc.) through the CSD representation is $\tilde{\mathcal{O}}((\kappa \cdot d)^2)$.

The proof of the above two items follows from the discussions in Section \[sizeofCSD\] and Section \[sec:operations\] respectively. We would like to point out here that while the cost of static operations such as membership is only $\tilde{\mathcal{O}}(d)$ for the Simplex Tree, to perform any dynamic operation such as insertion or removal, the Simplex Tree requires $\text{exp}(d)$ time. Moreover, as shown in Section \[sec:operations\], the cost of *most* basic operation using CSD is linear in $\kappa$.

As a direct consequence of representing a simplicial complex only through the critical simplices, we note that the construction of any simplicial complex with filtration, will be very efficient through CSD, simply because we have to build a smaller data structure as compared to the existing data structures. More specifically, we propose a new *edge-deletion* algorithm for the construction of flag complexes on $n$ vertices with $\kappa$ critical simplices in time $\mathcal{O}\left(\kappa n^{2.38}\right)$. Additionally, we provide a *matrix-parsing* algorithm for building $d$-dimensional relaxed Delaunay complexes over the witness set $W$ in $\mathcal{O}(|W| d^2 \log |W|)$ time. In each of these cases, we show that the construction is more efficient when using CSD rather than ST, primarily because CSD is a compact representation.

Organization of the paper
-------------------------

In Section \[Preliminaries\], we introduce definitions which will be used throughout the paper and we provide new lower bounds on the space of data structures needed to store simplicial complexes. In Section \[CSD\], we introduce the new data structure CSD to represent simplicial complexes and their filtration. Further, we describe how the data structure can perform basic operations on the complex and also discuss about its efficiency. In Section \[Flag\], we give a new algorithm for the construction of Flag complexes. In Section \[Delaunay\], we give a new algorithm for the construction of relaxed Delaunay complexes. Finally, in Section \[Conclusion\], we conclude by highlighting some open directions for future research.

Preliminaries {#Preliminaries}
=============

A simplicial complex $K$ is defined over a (finite) vertex set $V$ whose elements are called the vertices of $K$ and is a set of non-empty subsets of $V$ that is required to satisfy the following two conditions:

1.  $p\in V\Rightarrow \{p\}\in K$

2.  $\sigma\in K, \tau\subseteq\sigma\Rightarrow\tau\in K$

Each element $\sigma\in K$ is called a simplex or a face of $K$ and, if $\sigma\in K$ has precisely $s + 1$ elements $(s \ge -1)$, $\sigma$ is called an $s$-simplex and the dimension of $\sigma$, denoted by $d_\sigma$ is $s$. The dimension of the simplicial complex $K$ is the largest $d$ such that it contains a $d$-simplex.

A *face* of a simplex $\sigma = \{p_0 ,..., p_s \}$ is a simplex whose vertices form a subset of $\{p_0 ,..., p_s \}$. A proper face is a face different from $\sigma$ and the facets of $\sigma$ are its proper faces of maximal dimension. A simplex $\tau\in K$ admitting $\sigma$ as a face is called a *coface* of $\sigma$. A maximal simplex of a simplicial complex is a simplex which has no cofaces. A simplicial complex is pure, if all its maximal simplices are of the same dimension. Also, a free pair is defined as a pair of simplices $(\tau,\sigma)$ in $K$ where $\tau$ is the only coface of $\sigma$.

In this paper, the class of simplicial complexes of $n$ vertices in $d$ dimensions with $k$ maximal simplices out of the $m$ simplices in the complex is denoted by ${\cal K}(n,d,k,m)$, and $K$ denotes a simplicial complex in $ {\cal
  K} (n,d,k,m)$ .

In Figure \[fig:SimplicialComplexExample\] we see a three dimensional simplicial complex on the vertex set $\{1,2,3,4,5,6\}$. This complex has two maximal simplices: the tetrahedron $[1234]$ and the triangle $[356]$. We use this complex as an example through out the paper.

We adopt the following notation through out the paper: $[t]:=\{1,\ldots ,t\}$ and $\llbracket t\rrbracket=\{0,1,\ldots ,t\}$. A [*filtration*]{} over a simplicial complex $K$ is an ordering of the simplices of $K$ such that all prefixes in the ordering are subcomplexes of $K$. More concretely, a filtration of a complex is a function $f : K \to \mathbb{R}$ satisfying $f(\tau ) \le f(\sigma)$ whenever $\tau\subseteq\sigma$ [@EH10]. Moreover, we will assume that the filtration values range over $\llbracket t\rrbracket$. We say that a simplex $\sigma\in K$ is a **‘critical simplex’** if for all cofaces $\tau$ of $\sigma$ we have $f(\sigma)<f(\tau)$. For example, the critical simplices in the example described in Figure \[fig:SimplicialComplexExample\] are all the vertices, the edges $[56], [14], $ and $[24]$, the triangles $[356]$ and $[134]$, and the tetrahedron $[1234]$.

Lower Bounds {#Lower Bounds}
------------

Boissonnat et al. proved the following lower bound on the space needed to represent simplicial complexes [@BKT15].

\[Lowerbound\] [@BKT15] Consider the class of all $d$-dimensional simplicial complexes with $n$ vertices containing $k$ maximal simplices, where $d\ge2$ and $k\ge n+1$, and consider any data structure that can represent the simplicial complexes of this class. Such a data structure requires $\log{\binom{\binom{n/2}{d+1}}{k-n}}$ bits to be stored. For any constant $\varepsilon\in (0,1)$ and for $\frac{2}{\varepsilon}n\le k\le n^{(1-\varepsilon)d}$ and $d\le n^{\varepsilon/3}$, the bound becomes $\Omega(kd\log n)$.

We prove now a lower bound on the representation of filtrations of simplicial complexes.

\[FiltrationLowerbound\] Let $\beta=\left\lfloor\frac{t+1}{d+1}\right\rfloor$ be greater than 1. For any simplicial complex $K$ of dimension $d$ containing $m$ simplices, the number of distinct filtrations $f:K\to\llbracket t\rrbracket$ is at least $\beta^{m}$. If $\beta>(d+1)^{\delta}$ for some constant $\delta>0$ then, any data structure that can represent filtrations of the class of all $d$-dimensional simplicial complexes containing $m$ simplices requires $\Omega(m\log t)$ bits to be stored.

Let us fix a simplicial complex $K$ of dimension $d$ containing $m$ simplices. We will now build functions $f_i:K\to\llbracket t\rrbracket$. For every $i\in \left\llbracket{\beta}^m-1\right\rrbracket$, let $b(i)$ be the representation of $i$ as a $m$ digit number in base $\beta$ and let $b(i)_j$ be the $j^{\text{th}}$ digit of $b(i)$. Let $g$ be a bijection from $K$ to $[m]$. We define $f_i(\sigma)=d_{\sigma}\cdot\beta +b(i)_{g(\sigma)}+1$. We note that all the $f_i$s are distinct functions as for any two distinct numbers $i$ and $j$ in $\left\llbracket{\beta}^m-1\right\rrbracket$, we have that $b(i)\neq b(j)$. Finally, we note that each of the $f_i$s is a filtration of $K$. This is because, for any two simplices $\tau,\sigma\in K$, such that $\tau\subset\sigma$ (i.e., $d_\tau<d_\sigma$), and any $i\in \left\llbracket{\beta}^m-1\right\rrbracket$, we have that $f_i(\tau)\le (d_{\tau}+1)\cdot\beta < d_{\sigma}\cdot\beta+1\le f_i(\sigma)$.

It follows that there are at least $\beta^{m}$ distinct filtrations of $K$. By the pigeonhole principle, we have that any data structure that can represent filtrations of $K$ requires $\log\left(\beta^{m}\right)$ bits. It follows that if $\beta>(d+1)^{\delta}$ for some constant $\delta>0$ then $\beta>\frac{(t+1)^\delta}{(\beta-1)^\delta}$. Thus, any data structure that can represent filtrations of $K$ requires at least $\frac{\delta}{1+\delta}\cdot m\log (t+1)=\Omega(m\log t)$ bits to be stored.

Even if $\left\lfloor\frac{t}{d}\right\rfloor \le 1 $, we can show that any data structure that can represent $d$-dimensional simplicial complexes containing $m$ simplices with filtration ra nge $\llbracket t\rrbracket$ requires $\Omega(\frac{m\sqrt{t}}{d}\log t)$ bits. This can be shown by modifying the above proof as follows. Let $S_j$ be the set of all simplices of dimension $j-1$. We identify a subset $D$ of $[d]$ of size $\sqrt{t}$, such that $\sum_{j\in D}|S_{j}|$ is at least $\frac{m\sqrt{t}}{d}$. Therefore, for every set $S_j$, $j\in D$, we can associate $\sqrt{t}$ distinct filtration values, which leads to the lower bound.

The lower bounds in Lemma \[FiltrationLowerbound\] is not sensitive to the number of critical simplices, and intuitively, any lower bound on the size of data structures storing complexes with filtrations needs to capture the number of critical simplices as a parameter. We adapt the proof of Theorem \[Lowerbound\] and combine it with the ideas from the proof of Lemma \[FiltrationLowerbound\], to obtain the following lower bound.

\[CSDLowerBound\] Consider the class of all simplicial complexes on $n$ vertices of dimension $d$, associated with a filtration over the range of $\llbracket t\rrbracket$, such that the number of critical simplices is $\kappa$, where $d\ge2$ and $\kappa\ge n+1$, and consider any data structure that can represent the simplicial complexes of this class. Such a data structure requires $\log\left(\binom{\binom{n/2}{d+1}}{\kappa-n}t^{\kappa-n}\right)$ bits to be stored. For any constant $\varepsilon\in (0,1)$ and for $\frac{2}{\varepsilon}n\le \kappa\le n^{(1-\varepsilon)d}$ and $d\le n^{\varepsilon/3}$, the bound becomes $\Omega(\kappa (d\log n+\log t))$.

The proof of the first statement is by contradiction. Let us define $h=\kappa-n\ge 1$ and suppose that there exists a data structure that can be stored using only $s<\log \alpha \stackrel{{\rm def}}{=}\log\left(\binom{\binom{n/2}{d+1}}{\kappa-n}t^{h}\right)$ bits. We will construct $\alpha$ simplicial complexes (associated with a filtration), all with the same set $P$ of $n$ vertices, the same dimension $d$, with exactly $\kappa$ maximal simplices, and with a filtration over the range of $\llbracket t \rrbracket$. By the pigeon hole principle, two different simplicial complexes[^3], say $K$ and $K^\prime$, are encoded by the same word. So any algorithm will give the same answer for $K$ and $K^\prime$. But, by the construction of these complexes, there is either a simplex which is in $K$ and not in $K^\prime$ or there is a simplex whose filtration value in $K$ is different from the simplex’s filtration value in $K^\prime$. This leads to a contradiction.

The simplicial complexes and their associated filtration are constructed as follows. Let $P'\subset P$ be a subset of cardinality $n/2$, and consider the set of all possible simplicial complexes of dimension $d$ with vertices in $P'$ that contain $h$ critical simplices. We further assume that all critical simplices have dimension $d$ exactly. These complexes are $\beta=\binom{\binom{n/2}{d+1}}{h}$ in number, since the total number of maximal $d$ dimensional simplices is $\binom{n/2}{d+1}$ and we choose $h$ of them. Let us call them $\Gamma_1,\ldots,\Gamma_\beta$. We now extend each $\Gamma_i$ so as to obtain a simplicial complex whose vertex set is $P$ and has exactly $\kappa$ critical simplices. The critical simplices will consist of the $h$ maximal simplices of dimension $d$ already constructed (whose filtration value is set to one of the values in $[t]$) plus a number of maximal simplices of dimension 1 (whose filtration value is set to 0). The set of vertices of $\Gamma_i$, ${\rm vert}(\Gamma_i)$, may be a strict subset of $P'$. Let its cardinality be $\frac{n}{2}-r_i$ and observe that $0\leq r_i<\frac{n}{2}$. Consider now the complete graph on the $\frac{n}{2}+r_i$ vertices of $P\setminus {\rm vert}(\Gamma_i)$. Any spanning tree of this graph gives $\frac{n}{2}+r_i-1$ edges and we arbitrarily choose $\frac{n}{2}-r_i+1$ edges from the remaining edges of the graph to obtain $n$ distinct edges spanning over the vertices of $P\setminus {\rm vert}(\Gamma_i)$. We have thus constructed a 1–dimensional simplicial complex $K_i$ on the $\frac{n}{2}+r_i$ vertices of $P\setminus {\rm vert}(\Gamma_i)$ with exactly $n$ maximal simplices. Finally, we define the complex $\Lambda_i=\Gamma_i\cup K_i$ that has $P$ as its vertex set, dimension $d$, and $\kappa$ maximal simplices which are also the critical simplices. The filtration value of any simplex which is not maximal is defined to be the minimum of the filtration values of its cofaces in the complex. The set of $\Lambda_i$, $i=1, \cdots ,\beta$, where for each complex we associate $t^h$ different filtrations is the set of simplicial complexes (associated with a filtration) that we were looking for.

The second statement in the theorem is proved through the following computation:

$$\begin{aligned}
\log\left(\dbinom{\dbinom{n/2}{d+1}}{\kappa-n}t^{\kappa-n}\right)\ge &\ \log{\left(\frac{n^{(d+1)(\kappa-n)}}{2^{(d+1)(\kappa-n)}(d+1)^{(d+1)(\kappa-n)}(\kappa-n)^{(\kappa-n)}}\right)}+(\kappa-n)\log t \\
= &\ (d+1)(\kappa-n)\log n -(d+1)(\kappa-n)- (d+1)(\kappa-n)\log (d+1)\\
 &\ \phantom{{}(d+1)(\kappa-n)\log n -(d+1)} - (\kappa-n)\log (\kappa-n) +(\kappa-n)\log t\\
> &\ (d+1)(\kappa-n)\log n -3(d+1)(\kappa-n)-(d+1)(\kappa-n)\log d \\
 &\ \phantom{{}(d+1)(\kappa-n)\log n -(d+1)\log n } - (\kappa-n)\log \kappa +(\kappa-n)\log t\\
\ge &\ (d+1)(\kappa-n)(\log n -3-\log d) - (\kappa-n)(1-\varepsilon)d\log n \\
&\ \phantom{{}(d+1)(\kappa-n)(\log n -3-\log d) - (\kappa-n)(1-\varepsilon)d}  +(\kappa-n)\log t\\
\ge &\ d\varepsilon(\kappa-n)\log n + (\kappa-n)\log n -(d+1)(\kappa-n)\left(3+\frac{\varepsilon}{3}\log n\right)\\
&\ \phantom{{}(d+1)(\kappa-n)(\log n -3-\log d) - (\kappa-n)(1-\varepsilon)d}  +(\kappa-n)\log t\\
\ge &\ \frac{2\varepsilon}{3}\left(1-\frac{\varepsilon}{2}\right)\kappa d\log n  +\left(1-\frac{\varepsilon}{2}\right)\kappa\log t+\left(1-\frac{\varepsilon}{2}\right)\kappa\log n \\
&\ \phantom{{}(\kappa-n)\log n -(d+1)}-3d\left(1-\frac{\varepsilon}{2}\right)\kappa -\left(1-\frac{\varepsilon}{2}\right)\kappa\left(3+\frac{\varepsilon}{3}\log n\right) \\
= &\ \Omega(\kappa (d\log n+\log t))\end{aligned}$$

We note that in the above computation, the first inequality is obtained by applying the following bound on binomial coefficients: $\binom{n}{d}\ge\left(\frac{n}{d}\right)^d$.

Simplex Tree
------------

Let $K\in {\cal K}(n,d,k,m)$ be a simplicial complex whose vertices are labeled from 1 to $n$ and ordered accordingly. We can thus associate to each simplex of $K$ a word on the alphabet set $[n]$. Specifically, a $j$-simplex of $K$ is uniquely represented as the word of length $j + 1$ consisting of the ordered set of the labels of its $j + 1$ vertices. Formally, let $\sigma = \{v_{\ell_0} , \ldots , v_{\ell_j} \}$ be a simplex, where $v_{\ell_i}$ are vertices of $K$ and $\ell_i \in [n]$ and $\ell_0 <\cdot\cdot\cdot < \ell_j$ . $\sigma$ is represented by the word $[\sigma] = [ \ell_0 , \cdots , \ell_j ]$. The simplicial complex $K$ can be defined as a collection of words on an alphabet of size $n$. To compactly represent the set of simplices of $K$, the corresponding words are stored in a tree and this data structure is called the Simplex Tree of $K$ and denoted by ST$(K)$ or simply ST when there is no ambiguity. It may be seen as a trie on the words representing the simplices of the complex. The depth of the root is 0 and the depth of a node is equal to the dimension of the simplex it represents plus one.

We give a constructive definition of ST. Starting from an empty tree, insert the words representing the simplices of the complex in the following manner. When inserting the word $[\sigma] = [ \ell_0
,\cdot\cdot\cdot, \ell_j ]$ start from the root, and follow the path containing successively all labels $\ell_0 , \cdot\cdot\cdot ,
\ell_i$, where $[ \ell_0 ,\cdot\cdot\cdot, \ell_i ]$ denotes the longest prefix of $[\sigma]$ already stored in the ST. Next, append to the node representing $[ \ell_0 ,\cdot\cdot\cdot, \ell_i ]$ a path consisting of the nodes storing labels $\ell_{i+1}
,\cdot\cdot\cdot, \ell_j$. The filtration value of $\sigma$ denoted by $f(\sigma)$ is stored inside the node containing the label $\ell_j$, in the above path. In Figure 2, we give ST for the simplicial complex shown in Figure \[fig:SimplicialComplexExample\].

If $K$ consists of $m$ simplices (including the empty face) then, the associated ST contains exactly $m$ nodes. Thus, we need $\Theta(m(\log n+\log t))$ space/bits to represent the nodes in ST (since each node stores a vertex which needs $\Theta(\log n)$ bits to be represented and also stores the filtration value of the simplex that the node corresponds to, which needs $\Theta(\log t)$ bits to be represented). We remark here that we don’t consider the space needed to maintain the edges of ST, as it is part of the data structure implementation of ST. We can compare the upper bound obtained to the lower bound of Lemma \[FiltrationLowerbound\]. In particular, ST matches the lower bound, when $t$ is not small. Now, we will briefly recapitulate the cost of doing some basic operations through ST on a simplicial complex. To check if a simplex $\sigma$ is in the complex, is equivalent to checking the existence of the corresponding path starting from the root in ST. This can be done very efficiently in time $\mathcal{O}(d_\sigma \log n)$ and therefore all operations which primarily determine on the membership query can be efficiently performed using ST. One such example, is querying the filtration value of a simplex. However, due to its explicit representation, insertion is a costly operation on ST (exponential in the dimension of the simplex to be inserted). Similarly, removal is also a costly operation on ST, since there is no efficient way to locate and remove all cofaces of a simplex. Consequently, topology preserving operations such as elementary collapse and edge contraction are also expensive for ST. These operation costs are summarized later in Table \[tab:OperationsonMSD\]. In the next section, we will introduce a new data structure which does a better job of balancing between static queries (e.g. membership) and dynamic queries (e.g. insertion and removal).

Critical Simplex Diagram {#CSD}
========================

In this section, we introduce the [*Critical Simplex Diagram*]{}, ${\text{CSD}}(K)$, which is an evolved version of SAL [@BKT15]. CSD is a collection of $n$ arrays that correspond to the $n$ vertices of $K$. The elements of an array, referred to as [*nodes*]{} in the rest of the paper, correspond to copies of the vertex of $K$ associated to the array. Additionally, CSD has edges that join nodes of different arrays. Each connected component of edges in CSD represents a simplex of $K$. Not all simplices of $K$ are represented but only those simplices all of whose cofaces have a higher filtration value. We describe some notations used throughout the section below.

Notations {#sec:notations}
---------

Let $S_h$ be the set of simplices in the complex whose filtration value is $h$. Let $M_h$ be the maximal subset of $S_h$ containing all the critical simplices of $S_h$. For instance, in the complex of Figure \[fig:SimplicialComplexExample\], we have $M_0=\{1,2,3,4,5,6\}$, $M_1=\{[56]\}$, $M_2=\{[14],[356]\}$, $M_3=\{[134], [24]\}$, $M_4=\emptyset$, and $M_5=\{[1234]\}$. Moreover, we note that $M_0, M_1,...., M_t$ are all disjoint and denote by $M$ the union of all $M_h$.

We denote by $\Psi_{\max}(i)$ the subset of simplices of $M_h$ that contain vertex $i$ for all possible $h\in \llbracket t \rrbracket$. In other words,

Let $\Psi=\underset{i\in [n] }{\max}\ |\Psi_{\max}(i)|$.

We denote by $\Gamma_j$ the largest number of maximal simplices of $K$ that a given $j$-simplex of $K$ may be contained in. We note the following bounds: $$k\ge \Gamma_0\ge\Gamma_1\ge \cdots \ge \Gamma_d = 1,$$ $$\Gamma_0\le \Psi \le m.$$ Moreover, when $t=0$, we have $\Psi=\Gamma_0$. We describe the construction of CSD below.

Construction {#sec:construction}
------------

We initially have $n$ empty arrays $A_1,\ldots ,A_n$. The vertices of $K$ are associated to the arrays. Each array contains a set of nodes that are copies of the vertex associated to the array and are labelled by an ordered pair of integers (to be defined below). Nodes belonging to distinct arrays are joined by edges leading to a graph structure. The connected components of that graph represent the simplices in $M_0,M_1,\ldots,M_5$. All the nodes of such a simplex are labelled by a pair of integers. The first integer refers to the filtration value of the simplex and the second integer refers to a number used to index simplices that have the same filtration value. For instance, in Figure \[fig:CSDExample\] we have the CSD representation of the simplicial complex of Figure \[fig:SimplicialComplexExample\], and the triangle $[134]$ in $M_3$ is represented by 3 nodes, each with label $(3,1)$, that are connected by edges. Below we provide a more detailed treatment of the construction of CSD.

Given $M_h$ for every $h\in\llbracket t\rrbracket$, we build the CSD by inserting the simplices in $M_h$ in decreasing ordering of $h$. For *every* simplex $\sigma=v_{\ell_0} \cdot\cdot\cdot v_{\ell_j}$ in $M_h$, we associate a unique key generated using a hash function $\mathcal{H}$, ${\cal H}(\sigma) \in \left[|M_h|\right]$, and insert the nodes with label $(h,\mathcal{H}(\sigma))$ in to the arrays $A_{\ell_0},\ldots ,A_{\ell_j}$. For every $j^\prime\in [j]$, we introduce an edge between $(h,\mathcal{H}(\sigma))$ in $A_{\ell_{0}}$ and $(h,\mathcal{H}(\sigma))$ in $A_{\ell_{j^\prime}}$. In other words, $\sigma$, a critical simplex is being represented in CSD by a connected component in the graph thus defined. Each connected component is a star graph on $d_{\sigma}+1$ nodes where $v_{\ell_0}$ is the center of the star. Furthermore, each node in CSD corresponds to a vertex in exactly one simplex.

We denote by $A_i^\star$ the set of all nodes in $A_i$ of star graphs that correspond to maximal simplices in $K$ (the region with these nodes are shaded in Figure \[fig:CSDExample\]). Inside each $A_i$, we first sort nodes based on whether they are in $A_i^\star$ or not. Further, inside $A_i^\star$ and inside $A_i\setminus A_i^\star$, we sort the nodes according to the lexicographic order of their labels. We note that $A_i^\star$ is a contiguous subarray of $A_i$, i.e., all consecutive elements in $A_i^\star$ are also consecutive elements in $A_i$, as can be observed in Figure \[fig:CSDExample\].

We remark here that we use a hash function $\mathcal{H}$ to generate keys for simplices because it is an efficient way to reuse keys (in case of multiple insertions and removals).

Size of the Critical Simplex Diagram {#sizeofCSD}
------------------------------------

The number of nodes in each $A_i$ is at most $\Psi$, and the total number of nodes in CSD, we denote by $|{\rm CSD}|$, is at most $\Psi\cdot n$. Note that the number of edges in CSD is also at most $\Psi\cdot n$ since CSD is essentially a collection of star graphs.

Alternatively, we can bound the number of nodes by $|M|d$, where $M$ as defined in Section \[sec:notations\] is the union of all $M_h$. The actual relation between $\Psi$ and $|M|$ can be stated as follows: $$\sum_{i=1}^{n} |\Psi_{\max}(i)| = \sum_{\sigma\in M} (d_\sigma+1).$$

Further, in each node we store a filtration value (which requires $\log t$ bits) and a hashed value (which requires $\underset{h\in\llbracket t\rrbracket}{\max}\ \log |M_h|\le \log m$ bits). We can thus upper bound the space needed to store the nodes of CSD by $\Psi\cdot n(\log m+\log t)$ or by $|M|\cdot d(\log m+\log t)$. However, if we only store the filtration value and the hashed value at the center of the star graph then, we need only $|M|(d+\log m+\log t)$ space to store the nodes of CSD. In doing so, from any node of the star graph, we can still access/modify the filtration and hashed values in $\mathcal{O}(1)$ time. Thus, CSD matches the lower bound in Theorem \[CSDLowerBound\], up to constant factors (as $m=\mathcal{O}\left(n^d\right)$).

In the case of ${\text{CSD}}$, we are interested in the value of $\Gamma_0$ and $\Psi$ which we use to estimate the worst-case cost of basic operations in ${\text{CSD}}$, in the following subsection.

Operations on the Critical Simplex Diagram {#sec:operations}
------------------------------------------

Let us now analyze the cost of performing basic operations on ${\text{CSD}}$. First, we describe how to intersect arrays and update arrays in CSD as these are elementary operations on CSD which are required to perform basic operations on the simplicial complex that it represents. Next, we describe how to perform static queries such as the membership query. Following which we describe how to perform dynamic queries such as the insertion or removal of a simplex. Finally, we compare the efficiency of CSD with ST. We remark here that in order to perform the above operations efficiently, we will exploit the fact that the filtration value of a simplex that is not critical is equal to the minimum of the filtration values of its cofaces.

### Elementary Operations to maintain the Critical Simplex Diagram

Below, we first discuss the implementation of the arrays in CSD using red-black trees, and thus we would have described how to search within an array and update an array of CSD. Next, we describe how to compute the intersection of the arrays in CSD, an operation needed to answer static queries.

### Implementation of the arrays {#implementation-of-the-arrays .unnumbered}

We implement the arrays $A_i$ using a variant of the red-black trees, and this means we can search, insert, and remove an element inside $A_i$ in time $\mathcal{O}(\log |A_i|)$. Below we will discuss how to implement $A_i^\star$ and the same will hold for $A_i\setminus A_i^\star$ which we treat separately. Each subarray of $A_i^\star$ which have the same filtration value i.e., the same first coordinate, is implemented using a red-black tree. Now these subarrays described above partition $A_i^\star$ and we can label each partition with the common first coordinate value of its elements. We represent the set of these partitions using a red-black tree by storing the partitions label. Therefore, each $A_i$ is the union of two “doubly-composed” red-black trees. The way we search in $A_i$, is that we sequentially search in $A_i^\star$, followed by $A_i\setminus A_i^\star$.

### Intersecting arrays {#intersecting-arrays .unnumbered}

Let $\sigma$ be a simplex of dimension $d_{\sigma}$ and denote its vertices by $v_{\ell_0}, \ldots ,v_{\ell_{d_\sigma}}$. We will need to compute $A_\sigma$, defined as the intersection of $A_{\ell_0},\dots ,A_{\ell_{d_\sigma}}$, and $A_\sigma^\star$, defined as the intersection of $A_{\ell_0}^\star,\dots ,A_{\ell_{d_\sigma}}^{\star}$. To compute $A_\sigma$, we first find out the array with fewest elements amongst $A_{\ell_0},\dots ,A_{\ell_{d_\sigma}}$. Then, for each element $x$ in that array, we search for $x$ in the other $d_\sigma$ arrays, which can be done in time $\mathcal{O}\left(d_\sigma\log \left(\underset{i}{\max}\ |A_{\ell_i}|\right)\right)$. Hence $A_\sigma$ can be computed in time $\mathcal{O}\left(\left(\underset{i}{\min}\ |A_{\ell_i}|\right)d_\sigma\log \left(\underset{i}{\max}\ |A_{\ell_i}|\right)\right)$. As we have seen before, $|A_{\ell_i}| \leq \Psi \le m$.

We can compute $A_\sigma^\star$ in the same way as described above for $A_\sigma$ in time $\mathcal{O}\left(\left(\underset{i}{\min}\ |A_{\ell_i}^\star|\right)d_\sigma\log \left(\underset{i}{\max}\ |A_{\ell_i}^\star|\right)\right)$. As we have seen before, $|A_{\ell_i}^\star| \leq \Gamma_0 \le k$.

### Static Operations on the Critical Simplex Diagram {#staticoperations}

The tree structure of ST provides an efficient representation to perform static operations. However, we show below that we are able to answer these static queries using CSD by only paying a multiplicative factor of $\Psi$ (in the worst case) over the cost of performing the same operation in ST. In the case of the membership query, the multiplicative factor is reduced to $\Gamma_0$.

### Membership of a Simplex {#membership-of-a-simplex .unnumbered}

We first observe that $\sigma\in K$ if and only if $A_\sigma^\star\neq\emptyset$. This is because if $\sigma\in K$, then there exists a maximal simplex in $K$ which contains $\sigma$. The star graph associated to this maximal simplex has nodes in all the $A_{\ell_i}^\star$, and all those nodes have the same label. This implies that $A_\sigma^\star\neq\emptyset$, and the converse is also true. It follows that determining if $\sigma$ is in $K$ reduces to computing $A_\sigma^\star$ and checking whether it is non-empty. This procedure is very similar to the analogous procedure using SAL [@BKT15]. Therefore, membership of a simplex can be determined in time $\mathcal{O}(d_\sigma\Gamma_0\log k)$. Finally, we note that through the membership query, we are also able to decide if a simplex is maximal in the complex. We denote this new query by `is_maximal`, and will be used later for performing other operations.

### Access Filtration Value {#access-filtration-value .unnumbered}

Given a simplex $\sigma$ of $K$ we want to access its filtration value $f(\sigma)$. We observe that $f(\sigma)$ is the minimal filtration value of the nodes in $A_\sigma$ since the filtration function is monotone w.r.t. inclusion. Hence, accessing the filtration value of $\sigma$ reduces to computing $A_\sigma$. Therefore, the filtration of a simplex can be determined in time $\mathcal{O}(d_\sigma\Psi\log \Psi)$.

For example, consider the ${\text{CSD}}$ in Figure \[fig:CSDExample\]. We have to find the filtration value of $\sigma=[134]$ in the complex of Figure \[fig:SimplicialComplexExample\]. We see that $A_1\cap A_3 \cap A_4=\{(3,1),(5,1)\}$. This means that the filtration value of the triangle is $f([134])=\min\ (3,5)=3$. Finally, we note that through the filtration query, we are also able to decide if a simplex is critical in the complex. This new query, denoted by `is_critical`, will be used later for performing other operations.

### Computing Filtration Value of Facets {#computing-filtration-value-of-facets .unnumbered}

Given a simplex $\sigma= v_{l_0},...,v_{l_{d_{\sigma}}}$, we could procure the filtration value of its $d_\sigma+1$ facets by the access filtration value query, and thus requiring a total running time of $\mathcal{O}(d_\sigma^2 \Psi\log \Psi)$. However, we will modify the access filtration value query to obtain filtration value of the $d_\sigma+1$ facets of $\sigma$ in running time of $\mathcal{O}(d_\sigma \Psi\log \Psi)$. Let $A_{\ell_r}=\underset{i}{\text{argmin}}\ \lvert A_{\ell_i}\rvert$, for some $r\in\llbracket d_\sigma\rrbracket$. Let $B$ be a subset of $A_{\ell_r}$ such that every element of $A_{\ell_r}$ which appears in exactly $d_{\sigma}-1$ of the sets in $A_{\ell_0},\ldots ,A_{\ell_{r-1}},A_{\ell_{r+1}},\ldots ,A_{\ell_{d_\sigma}}$ is in $B$. We can identify $B$ in time $\mathcal{O}(|A_{\ell_r}|d_\sigma\log\Psi )$. To each entry $(s,x)$ in $B$ we associate the index of the set $A_{\ell_i}$ which does not contain $(s,x)$ by a mapping $g$. We sort $B$ based on $g$, and in case of ties based on the first coordinate. The filtration value of the facet $\sigma^\prime=v_{\ell_0} \cdots v_{\ell_{j-1}}\cdot v_{\ell_{j+1}}\cdots v_{\ell_{d_\sigma}}$, is the minimal filtration value of the nodes in $B$ which are mapped to $j$ under $g$. If there are no nodes in $B$ mapped to $j$ under $g$ then, the filtration value of $\sigma^\prime$ is $f(\sigma)$. This computation for all the $d_\sigma+1$ facets requires a total time of $\mathcal{O}(|B|\log |B|+d_\sigma\log |B|)=\mathcal{O}((\Psi+d_\sigma)\log \Psi)$. Therefore the total running time is $\mathcal{O}(d_\sigma \Psi\log \Psi)$.

### Computing Filtration Value of Cofaces of codimension 1 {#computing-filtration-value-of-cofaces-of-codimension-1 .unnumbered}

Given a simplex $\sigma$, we perform the access filtration value query to obtain all critical simplices that contain $\sigma$. We traverse the star graphs that contain the nodes in $A_\sigma$, to list these critical simplices in time $\mathcal{O}(d\Psi\log \Psi)$. From this list, we can compute the filtration value of all the cofaces of $\sigma$ of codimension 1 in $\mathcal{O}(d\Psi\log \Psi)$ time.

### Dynamic Operations on the Critical Simplex Diagram {#sec:dynamicoperations}

Now, we will see how to perform dynamic operations on CSD. We note here that CSD is more suited to perform dynamic queries over ST because of its non-explicit representation, and this means that the amount of information to be modified is always less than ST.

### Lazy Insertion {#lazy-insertion .unnumbered}

Lazy insertion is the operation of inserting $\sigma$ into the complex without checking if there are simplices in the complex which were previously critical but are now faces of $\sigma$ with the same filtration value as $f(\sigma)$. Additionally, in the case of lazy insertion, we assume that the information about $\sigma$ being a maximal simplex (or not) is known as part of the input. Lazy insertion will be extensively used in the later sections for preliminary construction of simplicial complexes. Lazy insertion in CSD requires $\mathcal{O}(d_\sigma\log\Psi)$ time (i.e., the cost of updating the arrays).

### Insertion {#insertion .unnumbered}

Suppose we want to insert a simplex $\sigma$ with filtration value $f(\sigma)$ such that any coface of $\sigma$ in $K$ has a filtration value larger than $f(\sigma)$. The insertion operation consists of first checking if $\sigma$ is a maximal simplex in $K$ by the `is_maximal` query. If $\sigma$ is maximal, then we have to insert the simplex and remove or reallocate (based on filtration value) all simplices which were maximal simplices in $K$ but are now faces of $\sigma$. If $\sigma$ is not maximal, then we just have to lazy insert $\sigma$ into the complex. We remark here that we do not need to remove the faces of $\sigma$ which were previously critical simplices and had filtration value at least $f(\sigma)$ as their presence will not hinder any operation on CSD. Alternatively, we can think of performing a clean-up operation in parallel where such nodes are removed from CSD without affecting any other operation (this discussion is elaborated in the paragraph called ‘Robustness in Modification’ in Section \[Performance\]).

Suppose $\sigma$ is a maximal simplex then, insert the star graph corresponding to $\sigma$ in $A_{\ell_0}^\star,\ldots ,A_{\ell_{d_\sigma}}^\star$. Updating the arrays $A_{\ell_i}$ takes time $\mathcal{O}(d_\sigma\log \Psi)$. Next, we have to check if there exist maximal simplices in $K$ which are now faces of $\sigma$, and either remove them if their filtration value is equal to $f(\sigma)$ or move them outside $A_{\ell_i}^\star$ if their filtration value is strictly less than that of $f(\sigma)$. We restrict our search for faces of $\sigma$ which were previously critical by looking for every vertex $v$ in $\sigma$, at the set of all maximal simplices which contain $v$, denoted by $Z_v$. We can compute $Z_v$ in time $\mathcal{O}( d_{\sigma}\Gamma_0 \log \Gamma_0)$. Then, we compute $\underset{v\in\sigma}{\cup}Z_v$ whose size is at most $(d_\sigma+1)\Gamma_0$ and check if any of these maximal simplices are faces in $\sigma$ (can be done in $\mathcal{O}(d_\sigma^2\Gamma_0)$ time). If such a face of $\sigma$ in $\underset{v\in\sigma}{\cup}Z_v$ has filtration value equal to $f(\sigma)$ then, we remove that connected component. To remove all such connected components takes time $\mathcal{O}(d_\sigma^2\Gamma_0\log \Gamma_0)$. On the other hand, if filtration value of the face is less than $f(\sigma)$ then, we will have to move the node outside $A_{\ell_i}^\star$ and place it appropriately to maintain the sorted structure of $A_{\ell_i}$. To reallocate all such connected components takes time $\mathcal{O}(d_\sigma^2\Gamma_0\log \Psi)$. Summarizing, to handle removal of face or reallocating the concerned faces of $\sigma$ which were previously maximal takes time at most $\mathcal{O}(d_\sigma^2\Gamma_0(\log \Gamma_0+\log \Psi))$.

If $\sigma$ is not a maximal simplex then, we insert the star graph corresponding to $\sigma$ in $A_{\ell_0},\ldots ,A_{\ell_{d_\sigma}}$. Updating the arrays $A_{\ell_i}$ takes time $\mathcal{O}(d_\sigma\log \Psi)$. Therefore, the total running time in this case is $\mathcal{O}(d_\sigma \log \Psi)$.

### Removal {#removal .unnumbered}

To remove a face $\sigma$, we first perform an access filtration value query of $\sigma$ (requires $\mathcal{O}(\Psi d_{\sigma}\log \Psi)$ time). We deal with the simplices in $ A_\sigma^\star$ and $ A_\sigma\setminus A_\sigma^\star$ separately. For every simplex $ \tau\in A_\sigma^\star$, i.e., for every coface $\tau$ of $\sigma$ in $K$ which is a maximal simplex, we remove its corresponding star graph from the CSD. Since there are at most $\Gamma_{d_{\sigma}}$ maximal simplices which contain $\sigma$, the above removal of star graphs can be done in $\mathcal{O}(\Gamma_{d_{\sigma}}d\log \Psi)$ time. Next, for each maximal simplex $\tau$ (containing $\sigma$) that we removed, and for every $i\in \llbracket d_\sigma\rrbracket $ we check if the facet of $\tau$ obtained by removing $v_{\ell_{i-1}}$ from $\tau$, is a maximal simplex. If yes, we lazy insert the facet as a maximal simplex with the same filtration value as $\tau$. If no, we lazy insert the facet as a non-maximal simplex with the same filtration value as $\tau$. Note that in order to check if the above mentioned $d_\sigma+1$ facets of $\tau$ are maximal, we do not have to make $d_{\sigma}+1$ `is_maximal` queries, but can do the same checking in $\mathcal{O}(\Gamma_{d_\sigma}d\log \Psi )$ time by using the same idea that is described in the ‘computing filtration value of facets’ paragraph in Section \[staticoperations\]. Additionally, we remark here that we can lazy insert the above selected facets of the the critical cofaces of $\sigma$, without checking if the facets themselves are critical because the argument made in the Insertion paragraph above for such cases apply here as well.

Next, for every simplex $ \tau\in A_\sigma\setminus A_\sigma^\star$ i.e., for every coface $\tau$ of $\sigma$ in $K$ which is a critical (not maximal) simplex, we replace its corresponding star graph by star graphs of its $d_{\sigma}+1$ facets with the same filtration value, where the $i^{\text{th}}$ facet is obtained by removing $v_{\ell_{i-1}}$ from $\tau$. Introducing a star graph and updating the arrays $A_{\ell_i}$ takes time $\mathcal{O}(d_\tau\log \Psi)$. Further, if $\sigma$ is a critical simplex (can be checked by `is_critical` query) then, we know that there is a connected component representing $\sigma$. We replace this star graph by the star graph for all its facets which have the same filtration value. Therefore, the total running time is $\mathcal{O}(dd_\sigma\Psi\log \Psi)$. We note here that as before, we lazy insert the above selected facets of the the critical cofaces of $\sigma$, without checking if the facets themselves are critical.

Therefore, the total time for insertion is $\mathcal{O}(\Psi dd_\sigma \log \Psi + \Gamma_{d_\sigma}d_\sigma d\log \Psi + \Gamma_{d_\sigma}^2d\log \Psi )=\mathcal{O}((\Psi d_\sigma  + \Gamma_{d_\sigma}^2)d\log \Psi)$.

### Elementary Collapse {#elementary-collapse .unnumbered}

A simplex $\tau$ is collapsible through one of its faces $\sigma$, if $\tau$ is the only coface of $\sigma$. Such a pair $(\sigma,\tau)$ is called a free pair, and removing both faces of a free pair is an elementary collapse. Given a pair of simplices $(\sigma,\tau)$, to check if it is a free pair is done by obtaining the list of all maximal simplices which contain $\sigma$, through the membership query (costs $\mathcal{O}(d_\sigma \Gamma_0\log\Gamma_0 )$ time) and then checking if $\tau$ is the only member in that list with codimension 1. If yes, then we remove $\tau$ from the CSD by just removing all the nodes in the corresponding arrays in time $\mathcal{O}(d_{\tau}\log \Psi)$. Next, for every facet $\sigma^\prime$ of $\tau$ other than $\sigma$, we check if $\sigma^\prime$ is a critical simplex (post removal of $\tau$) by asking the `is_critical` query. If yes, we lazy insert $\sigma^\prime$ in time $\mathcal{O}(d_\sigma\log \Psi)$. Finally, if $\sigma$ is a critical simplex then, we remove it in the same way we removed $\tau$ and for every facet of $\sigma$ we similarly check if it is a critical simplex (post removal of $\sigma$) by asking the `is_critical` query. If yes, we lazy insert that facet in time $\mathcal{O}(d_\sigma\log \Psi)$. Thus, the total running time is $\mathcal{O}(d_\sigma (d_\sigma\Psi\log \Psi+\Gamma_0\log\Gamma_0))=\mathcal{O}(d_\sigma^2 \Psi\log \Psi)$.

### Summary

We summarize in Table \[tab:OperationsonMSD\] the asymptotic cost of basic operations discussed above and compare it with ST, through which the efficiency of ${\text{CSD}}$ is established.

If the number of critical simplices is not large then $|{\text{CSD}}|$ is smaller than $|{\text{ST}}|$. The number of critical simplices is small unless we associate unique filtration values to a significant fraction of the simplices. For this subsection, we will assume that the number of critical simplices is small (this assumption will be justified in the next subsection). In this case, we have $\Psi$ to be small and thus the size of CSD is smaller than the size of ST.

We observe that while performing static queries, we pay a factor of $\Psi$ or $\Gamma_0$ in the case of CSD over the cost of the same operation in ST. In the case of dynamic operations we observe that the dependence on the dimension is exponentially smaller in CSD than in ST. Therefore, even if the number of critical simplices is polynomial in the dimension then, there is an exponential gap between CSD and ST in both the storage and the efficiency of performing dynamic operations. Furthermore, in the case of insertion, CSD depends on $\Gamma_0$ and not $\Psi$ (recall that $\Gamma_0\le \Psi$). Thus, the efficient insertion operation in CSD allows for fast construction of simplicial complexes, as we will see in future sections.

In short, CSD needs less storage than ST and performs dynamic operations more efficiently than ST while paying (mostly) a small multiplicative factor over ST in performing static queries. This is analogous to the trade-off between NFA (Non-deterministic Finite state Automaton) and DFA (Deterministic Finite state Automaton).

Performance of CSD {#Performance}
------------------

CSD has been designed to store filtrations of simplicial complexes but it can be used to store simplicial complexes without a filtration. In this case, $|M|=k$ and CSD requires $\mathcal{O}(kd\log k)$ memory space, which matches the lower bound in Theorem \[Lowerbound\], when $k=n^{\mathcal{O}(1)}$. In this case, CSD is very similar to SAL [@BKT15]. Marc Glisse and Sivaprasad S. [@MarcSivaprasad] have performed experiments on SAL and concluded that it is not only smaller in size but also faster than the Simplex Tree in performing insertion, removal, and edge contraction.

CSD is also a compact data structure to store filtrations, as its size matches (up to constant factors) the lower bound of $\Omega(|M|(d\log n+\log t))$ in Theorem \[CSDLowerBound\]. Moreover, if $\Psi$ is small, CSD is not only a compact data structure since $|{\text{CSD}}|$ is upper bounded by $\Psi n$, but, as shown in Table \[tab:OperationsonMSD\], CSD is also a very efficient data structure as all basic operations depend polynomially on $d$ (as opposed to ST for which some operations depend exponentially on $d$).

As our analysis shows, we can express the complexity of CSD in terms of a parameter $\Psi$ that reflects some “local complexity” of the simplicial complex. In the worst-case, $\Psi=\Omega(m)$ as it can be observed in the complete complex with each simplex having a unique filtration value. However we conjecture that, even if $m$ is not small, $\Psi$ remains small for a large class of simplicial complexes of practical interest. This conjecture is supported by the following experiment.

We considered a set of points obtained by sampling a Klein bottle in $\mathbb{R}^5$ and constructed its Rips filtration (see Section \[Flag\] for definition) using libraries provided by the GUDHI project [@GUDHI]. We computed $\Gamma_0$ and $\Psi$ for various values of $t$. The resulting simplicial complex on 10,000 vertices is 17 dimensional and has 10,508,486 simplices of which 27,286 are maximal. We record in Table \[tab:Rips\] below, the values of $|{\text{ST}}|$ and $|{\text{CSD}}|$ for the various filtration ranges of the Rips complex constructed above. In Figure \[fig:Rips\] is a graphical illustration of the data.

\[dataset1\]

We note from Table \[tab:Rips\] that $\Gamma_0$ is significantly smaller than $k(\approx 2.7 \times 10^4)$, and also that $\Gamma_0^{\text{avg}}$ is much smaller than $\Gamma_0$. Also, from Figure \[fig:Rips\], it is clear that there is an order of magnitude gap between $|{\text{CSD}}|$ and $|{\text{ST}}|$. Next, we note that $\Psi$ is remarkably smaller than $m$ (even notably smaller than $n$), and this implies efficient implementation of all operations. More importantly, we remark here that $\Psi^{\text{avg}}=|{\text{CSD}}|/n$ is at most $77.8$ in the above experiment. Finally, we observe that despite increasing $t$ at a rapid rate, $|{\text{CSD}}|$ grows very slowly after $t=100$. This is because the set of all possible filtration values of the Rips complex is small. Therefore, even for small values of $t$ the simplicial complex and its filtration is accurately captured by CSD.

### Local Sensitivity of the Critical Simplex Diagram {#local-sensitivity-of-the-critical-simplex-diagram .unnumbered}

It is worth noting that while the cost of basic operations are bounded using $\Gamma_0$ and $\Psi$, the actual cost is bounded by parameters such as $\underset{i}{\min}\left(|A_{\ell_i}^\star|\right)$, $\underset{i}{\min}\left(|A_{\ell_i}|\right)$, and $Z_v$ (introduced in the Insertion paragraph in Section \[sec:dynamicoperations\]) to get a better estimate on the cost of these operations. These parameters are indeed local. To begin with, $\underset{i}{\min}\left(|A_{\ell_i}^\star|\right)$ captures the local information about a simplex $\sigma$ sharing a vertex with other maximal simplices of the complex. More precisely, it is the minimum, over all the vertices of $\sigma$, of the largest number of maximal simplices that contain the vertex. If $\sigma$ has a vertex which is contained in a few maximal simplices then, $\underset{i}{\min}\left(|A_{\ell_i}^\star|\right)$ is small. Similarly, $\underset{i}{\min}\left(|A_{\ell_i}|\right)$ is the minimum, over all the vertices of $\sigma$, of the largest number of critical simplices that contain the vertex. This value depends not only on the structure of the filtration function but also on the filtration range. Finally, $Z_v$ captures another local property of a simplex $\sigma$ – the set of all maximal simplices that contain the vertex $v$. Therefore, CSD is sensitive to the local structure of the complex.

### Robustness in Modification {#robustness-in-modification .unnumbered}

We now demonstrate the robustness of CSD, i.e., its ability to perform queries *correctly* and *efficiently* even when it might have stored redundant data such as simplices which are not critical or multiple copies of the same simplex with different filtration values. Consider modifying the filtration value of some simplex $\sigma\in K$ from $f(\sigma)$ to $s_{\sigma}(<f(\sigma))$. In the case of ST, we will have to modify the filtration value inside the node containing $\sigma$ and additionally check (and modify if needed) its faces in decreasing order of dimension. This requires time $\Theta(2^{d_\sigma}d_\sigma(\log n+\log t))$. However, in the case of CSD, we can perform a lazy insertion of $\sigma$ into CSD in time $\mathcal{O}(d_\sigma\log \Psi)$, and the data structure is robust to such an insertion. This is because, all the operations can be performed correctly and with the same[^4] efficiency after the lazy insertion (even if some previously critical simplices need to be removed due to the lazy insertion of $\sigma$). For instance, consider the $\texttt{is\_critical}$ query on some simplex $\tau$. If $\tau$ was a face of $\sigma$ before modifying $f(\sigma)$ then, the *minimal* filtration value of the nodes in $A_{\tau}$ correctly gives the filtration value of $\tau$ as $s_\sigma$ will now be one of the entries in $A_\tau$. Otherwise, if $\tau$ was not a face of $\sigma$ then the filtration value of $\tau$ remains unchanged, as the lazy insertion of $\sigma$ has not introduced a new simplex, but only a new filtration value to an existing simplex. Therefore, we can think of using the data structure to manipulate simplicial complexes in very short time through a collection of lazy insertions and perform a clean-up operation at the end of the collection of lazy insertions, or even think of performing the clean-up operation in parallel to the lazy insertions. This idea has been applied in performing the insertion and removal operations as discussed in Section \[sec:dynamicoperations\]. We remark here that if we lazy insert $r$ simplices then in the worst case, $\Psi$ grows to $r+\Psi$. In other words, the presence of redundant simplices, implies that the efficiency dependence will now be on $r+\Psi$ instead of $\Psi$, but the redundancy will not affect the correctness of the operations.

[A Sequence of Representations for Simplicial Complexes and their Filtrations]{}
--------------------------------------------------------------------------------

Boissonnat et al. [@BKT15] in their paper on Simplex Array List described a sequence of data structures, each more powerful than the previous ones (but also bulkier). In that sequence of data structures $\langle \Lambda\rangle$, we had $\Lambda_{i}=i\mhyphen {\text{SAL}}$ (${\text{SAL}}$ referred to earlier in this paper is equal to $1\mhyphen{\text{SAL}}$). Further, they note that in the $i^{\textrm{th}}$ element of the sequence, every node which is not a leaf (sink) in the data structure corresponds to a unique $i$-simplex in the simplicial complex. Also for all $i\mhyphen{\text{SAL}}$, $i\in\mathbb{N}$, they state that it is a NFA recognizing all the simplices in the complex. As one moves along the sequence, the size of the data structure blows up by a factor of $d$ at each step. But in return, there is a gain in the efficiency of searching for simplices as the membership query depends on $\Gamma_i$ which decreases as $i$ increases.

We note here that ${\text{CSD}}$ described in this paper is exactly the same as $0\mhyphen{\text{SAL}}$, when $t=0$ (we ignore the structure of the connected component, which is a path in SAL but a star in CSD). Therefore, ${\text{CSD}}$ supersedes $0\mhyphen{\text{SAL}}$. There is no change in representation of a simplex between SAL and CSD; instead we only store more simplices (i.e, all critical simplices) in CSD. Therefore, in the same vein as $\langle\Lambda\rangle$, we can define a sequence of data structures, each more powerful than the previous ones (but also bulkier). More formally, consider the sequence of data structures $\langle \Pi\rangle$, where $\Pi_{0}={\text{CSD}}$ and $\Pi_i =
\underset{j=0}{\overset{t}{\bigcup}}i\mhyphen{\text{SAL}}(M_j)$, for all $i\in\mathbb{N}$. Further, for all $i\in\mathbb{N}$, we will refer to the data structure $\Pi_i$ by the name $i\mhyphen {\text{CSD}}$ (we will continue to refer to $0\mhyphen{\text{CSD}}$ as ${\text{CSD}}$). As we move along the sequence $\Pi$, the size of the data structure blows up by a factor of $d$ at each step. But in return, we gain efficiency in searching for simplices as the membership query depends on $\Gamma_i$ which decreases as $i$ increases. Additionally, we gain efficiency in accessing filtration value of a simplex as the complexity no longer depends on $\Psi=\Psi_0$ but on a smaller parameter, $\Psi_i$, which is the maximum number of critical cofaces that any $i$-simplex can have in the complex.

Marc Glisse and Sivaprasad S. implemented SAL [@MarcSivaprasad] for Data Set mentioned in Section 3.4, and then performed insertion and removal of random simplices, and contracted randomly chosen edges. They observed that 1-SAL outperformed 0-SAL in low dimensions. However, 0-SAL performed better than 1-SAL in higher dimensions. Therefore, in similar vein, it would be worth exploring for which class of simplicial complexes, $i\mhyphen$CSD is the best data structure in the CSD family (for every $i\in\mathbb{N}$).

Construction of Flag Complexes {#Flag}
==============================

The flag complex of an undirected graph $G$ is defined as an abstract simplicial complex, whose simplices are the sets of vertices in the cliques of $G$. Let $(P, \|\cdot\|)$ be a metric space where $P$ is a discrete point-set. Given a positive real number $r > 0$, the Rips complex is the abstract simplicial complex $\mathcal{R}^r(P)$ where a simplex $\sigma\in\mathcal{R}^r(P)$ if and only if $\|p-q\|\le 2r$ for every pair of vertices of $\sigma$. Note that the Rips complex is a special case of a flag complex. Rips filtrations are widely used in Topological Data Analysis since they are easy to compute and they allow to robustly reconstruct the homology of a sample shape via the computation of its persistence diagram [@CCSGGO09].

We will describe a specific filtration for Flag complexes which is of significant interest as it includes the Rips filtration. The filtration value of a vertex is $0$. The filtration value of every edge in the complex is given as part of the input. The filtration value of a simplex of higher dimension is equal to the maximum of the filtration values of all the edges in the simplex.

Edge-Deletion Algorithm for Construction of Flag Complexes
----------------------------------------------------------

Let $G$ be the (weighted) graph of the simplicial complex $K$. Let $\Delta$ denote the maximum degree of the vertices of $G$. To represent $K$ using ST, Boissonnat and Maria [@SimplexTree] propose computing and inserting the $\ell$-skeleton of $K$ into the ST and incrementally increasing $\ell$ from $1$ to $d$. Therefore, the time for construction of the ST representing the flag complex is $\mathcal{O}(mnd\log n)$.

To represent $K$ using CSD, we propose an *edge-deletion* algorithm, which is significantly faster than the construction algorithm for ST. We recall that in Section \[sec:construction\] we defined $S_h$ to denote the set of simplices in the complex with filtration value $h$.

#### Preprocessing Step.

We first compute all maximal cliques in $G$ in time $\mathcal{O}(k\cdot n^\omega)$ [@MU04], where $\omega<2.38$ [@L14] is the matrix multiplication exponent, i.e., $n^\omega$ is the time needed to multiply two $n\times n $ matrices. We store these maximal simplices in a Prefix Tree (like MxST of [@BKT15]). The filtration value given to the edges provides a natural ordering to the edges of the complex. We consider edges in descending order of their filtration value. Let $e_i$ be the edge with the $i^{\text{th}}$ highest filtration value. Recall that all simplices containing $e_i$ are of filtration value $f(e_i)$ and are in $S_{f(e_i)}$. Fix $i=1$.

#### Step 1.

In this step, we would like to compute $M_{f(e_i)}$ in order to build CSD. A natural way to do that is by first computing $S_{f(e_i)}$, and then identifying the subset $M_{f(e_i)}$. Computing $S_{f(e_i)}$ requires time $\mathcal{O}\left(\left|S_{f(e_i)}\right|d\log n\right)$ and then computing $M_{f(e_i)}$ will require time $\widetilde{\mathcal{O}}\left(\left|S_{f(e_i)}\right|\cdot d\cdot \left|M_{f(e_i)}\right|\right)$ using the best known algorithms in literature [@Y92; @YJ93; @P97; @BP11]. However, we will not compute $M_{f(e_i)}$ from $S_{f(e_i)}$, but instead skip computing $S_{f(e_i)}$ and directly compute $M_{f(e_i)}$ to list all the maximal simplices only containing the edge $e_i$ in time $\mathcal{O}\left(\left|M_{f(e_i)}\right|\Delta^\omega\right)$ using the algorithm presented by Makino and Uno [@MU04] on a subgraph of $G$ in the following way. We build an induced subgraph $H$ of $G$ which contains the vertices of the edge $e_i$ and all the vertices which are adjacent to *both* the vertices of $e_i$. We note that every maximal clique in $H$ is a maximal clique in $G$ containing the edge $e_i$, and vice versa. Therefore, if we run Makino and Uno’s algorithm on $H$ (which contains at most $\Delta+1$ vertices), we obtain all the maximal cliques in $G$ containing the edge $e_i$.

#### Step 2.

Next, we recognize the maximal simplices of $K$ in $M_{f(e_i)}$ in time $\mathcal{O}\left(\left|M_{f(e_i)}\right|d\log n\right)$ by checking each simplex $\sigma$ in $M_{f(e_i)}$ with the Prefix tree built in the preprocessing step in time $\mathcal{O}(d_\sigma \log n)$ (per simplex). We remark here that all simplices in $M_{f(e_1)}$ are maximal simplices in $K$, since $e_1$ has the largest filtration value.

#### Step 3.

We perform lazy insertion of simplices in $M_{f(e_i)}$ into the CSD and since we have identified the maximal simplices in $M_{f(e_i)}$, we know whether to insert them in $A_j^\star$ or not, within each $A_j$. This takes time $\mathcal{O}\left(\left|M_{f(e_i)}\right|d\log \Psi\right)$.

#### Step 4.

Finally, we remove $e_i$ from $G$, increment $i$ by 1, and repeat the procedure from step 1 until $G$ has no edges left.

This entire construction takes time $\mathcal{O}(|M|(\Delta^\omega+d\log(kd\Psi)))=\mathcal{O}\left(|M|n^{2.38}\right)$, which is significantly better than that of constructing a representation of $K$ by ST (which required time $\mathcal{O}(mnd\log n)$), as $|M|$ can be considerably (exponentially) smaller than $m$.

Performance of CSD for Flag Complexes
-------------------------------------

We would like to note here that the case when $k=\mathcal{O}(n)$, was argued to be of particular interest by Boissonnat et al. [@BKT15]. It can be observed in flag complexes, constructed from planar graphs and expanders [@ELS10], and in general, from nowhere dense graphs [@GKS13], and also from chordal graphs[@G80]. Generalizing, they noted that for all flag complexes constructed from graphs with degeneracy $\mathcal{O}(\log n)$ (degeneracy is the smallest integer $r$ such that every subgraph has a vertex of degree at most $r$), we have that $k=n^{\mathcal{O}(1)}$ [@ELS10]. We add to this list of observations by noting that the flag complexes of $K_{\ell}$-free graphs have at most $\max\{n,n\Delta^{\ell-2}/2^{\ell-2}\}$ maximal simplices [@P95], where $\Delta$ is the maximum degree of any vertex in the graph. Thus, when $\Delta$ and $\ell$ are constants, we have $k=\mathcal{O}(n)$. Finally, we note that the flag complexes of Helly circular-arc (respectively, circle) graphs [@G74; @D03], and boxicity-2 graphs [@S03] have $k=n^{\mathcal{O}(1)}$ from Corollary 4 of [@RS07]. This encompasses a large class of complexes encountered in practice and if the number of maximal simplices is small, ${\text{CSD}}$ is a very efficient data structure as $\Gamma_0\le k$.

Adaptation to Simplicial Maps
-----------------------------

A map $F:K\to K^\prime$ is simplicial if for every simplex $\sigma=\{v_0, v_1,\ldots , v_k\}$ in $K$, $F(\sigma)=\{F(v_0), F(v_1), \ldots , F(v_k)\}$ is a simplex in $K^\prime$. In this subsection, we discuss the adaptation of CSD to handle simplicial maps. For the purpose of demonstration, we consider Dey et al.’s [@DFW14] application of simplicial maps to topological data analysis over Rips complexes. They construct a sequence of Rips simplicial complexes, $\langle K_i^{\alpha_i}\rangle$ connected by simplicial maps, where $\alpha_i$ is the Rips parameter. The vertex set of $K_{i+1}^{\alpha_{i+1}}$ is obtained by extracting a subset (net) of the vertex set of $K_i^{\alpha_{i}}$. They define a map $\pi$ through which they map each vertex of $K_i^{\alpha_{i}}$ to its closest vertex in $K_{i+1}^{\alpha_{i+1}}$ . Next, they take $\alpha_{i+1}>\alpha_i$ so that the image of the edges of $K_i^{\alpha_{i}}$ are edges in $K_{i+1}^{\alpha_{i+1}}$. Since the complexes are Rips complexes, the image of all the simplices of $K_i^{\alpha_{i}}$ are in $K_{i+1}^{\alpha_{i+1}}$. To implement this procedure using CSD, we need to collapse the vertices of vert($K_i^{\alpha_{i}}$)$\setminus$vert($K_{i+1}^{\alpha_{i+1}}$) onto the vertices of $K_{i+1}^{\alpha_{i+1}}$ as given by $\pi$. First, we remark that this procedure is very expensive using ST, as vertex collapse is more expensive than the edge contraction operation, and Boissonnat and Maria [@SimplexTree] provide an essentially optimal algorithm running in $\mathcal{O}(md\log n)$ time for edge contraction.

In the case of CSD, we will assume that $\left(|\text{vert}(K_i^{\alpha_{i}})|-|(\text{vert}(K_{i+1}^{\alpha_{i+1}})|\right)$ is small, as otherwise, we could reconstruct $K_{i+1}^{\alpha_{i+1}}$ entirely from scratch using the fast edge-deletion algorithm. For every vertex $v$ in vert($K_i^{\alpha_{i}}$)$\setminus$vert($K_{i+1}^{\alpha_{i+1}}$), we first build a set $T_v$ from the set of maximal simplices containing $v$ as follows. If $\sigma$ is a maximal simplex containing $v$, then we include the simplex $\tau=\sigma\cap\text{vert}(K_{i+1}^{\alpha_{i+1}})$ in $T_v$. Let $T=\cup\ T_v$. Next, for every vertex $v$ in vert($K_i^{\alpha_{i}}$)$\setminus$vert($K_{i+1}^{\alpha_{i+1}}$), we remove all the nodes in $A_v$ and its neighbors in other arrays. For every simplex in $T$, we perform the `is_critical` query. If the simplex was not critical in $K_i^{\alpha_{i}}$ but is critical in $K_{i+1}^{\alpha_{i+1}}$, then we lazy insert the simplex. On the other hand, if the simplex was critical in $K_i^{\alpha_{i}}$, then we check if it is maximal in $K_{i+1}^{\alpha_{i+1}}$ and reallocate appropriately. The total cost of performing the above procedure is $\mathcal{O}(|T|d\Psi\log\Psi)$, where $|T|=\mathcal{O}(\Gamma_0(|\text{vert}(K_i^{\alpha_{i}})|-|(\text{vert}(K_{i+1}^{\alpha_{i+1}})|))$. This running time is significantly better than that of implementing the simplicial map using ST, as $\Psi$, and consequently $\Gamma_0$, may be considerably (exponentially) smaller than $m$. Adding to the above argument the benefit of the considerably (exponentially) smaller size of CSD, it is clear that CSD better supports the implementation of simplicial maps than ST.

Construction of Relaxed Delaunay Complexes {#Delaunay}
==========================================

Let $Q$ be a finite subset of a metric space $(P, \|\cdot\|)$ where $P$ is a discrete point-set. Given a relaxation parameter $\rho\ge 0$, we define the notion of being ‘witnessed’ as follows. A simplex $\sigma = \{q_0,\ldots , q_{d_\sigma}\}\subseteq Q$ belongs to the relaxed Delaunay complex[^5] $\text{Del}^\rho(Q, P)$ [@D08; @BDG15] if and only if there exists $x\in P$ such that for all $q_i\in \sigma$, and for all $q\in Q$ the following holds: $$\begin{aligned}
\|x-q_i\| \leq \|x-q\| + \rho\end{aligned}$$

The parameter $\rho$ defines a filtration on the relaxed Delaunay complexes, which has been used in topological data analysis. More explicitly, the filtration value of a simplex $\sigma$ in $\text{Del}^\rho(Q, P)$ is the smallest $\rho^\prime\le \rho$, such that $\sigma$ is in $\text{Del}^{\rho^\prime}(Q, P)$. For this entire section, we assume that the filtration range is $\llbracket t\rrbracket$.

We define a matrix $D$ of size $|P|\times |Q|$ as follows. For every $x\in P$ and $\ell\in [|Q|]$ let $D(x,\ell)$ denote the $\ell^{\text{th}}$ nearest neighbor of $x$ in $Q$ (ties are broken arbitrarily). For every $x\in P$, $i\in\llbracket t\rrbracket$, let $\ell_x^i$ be the largest integer such that $\left|\|x-D(x,1)\|-\|x-D(x,\ell_x^i)\|\right|\le \rho i/t$. Let $\sigma_x^i=\{D(x,1),D(x,2),\ldots ,D(x,\ell_x^i)\}$ and let $W=\left\{\sigma_x^i\bigl\vert x\in P, i\in \llbracket t \rrbracket\right\}$. We note below that $M$ (recall notation from Section \[sec:notations\]), the set of critical simplices in the complex is contained in $W$.

\[DelaunayStrong\] $M\subseteq W.$

Let $\tau=\{v_0,\ldots v_{d_\tau}\}$ be a critical simplex in $M$ with filtration value $f(\tau)$. By definition of $\text{Del}^\rho(Q, P)$, we have that there exists a point $x\in P$ which $\left(f(\tau)\rho/t\right)$-strongly witnesses $\tau$. Since $\tau$ is critical, we have that for every $q\in Q\setminus \tau$, the following holds. $$\forall i\in\llbracket d_\tau\rrbracket,\  \left|\|x-v_i\|-\|x-q\|\right|> \rho f(\tau)/t.$$ Therefore, we have that for every $i\in [d_\tau+1]$, $A(x,\ell_x^i)\in \tau$, or more precisely, $\sigma_x^{d_\tau+1}=\tau$.

The above lemma provides a characterization of $\text{Del}^\rho(Q, P)$: it can have at most $|P|(d+1)$ critical simplices. We note here that typically $P$ is a relatively small set. For example, in the experiments performed by Boissonnat and Maria (Table 1 of [@SimplexTree]), we note that the cardinality of the witness set is about a few ten thousands while the number of simplices in the complex is over a hundred million. Therefore, this provides practical evidence of the compact representation of $\text{Del}^\rho(Q, P)$ through CSD.

Under the assumption that for any $x,\ell$, $D(x,\ell)$ could be computed in $\mathcal{O}(1)$ time (i.e., $D$ is computed as part of the preprocessing), Boissonnat and Maria [@SimplexTree] described an algorithm to construct the ST representation of the relaxed witness complex. Their algorithm can be easily adapted to construct $\text{Del}_w^\rho(Q, P)$ in time $\mathcal{O}(tmd\log n)$.

In the case of CSD, we propose a new *matrix-parsing* algorithm which builds $\text{Del}^\rho(Q, P)$ in time $\mathcal{O}(|P|d^2\log \Psi)$ (assuming an oracle to access $D$). It is easy to see that all the simplices in $W$ can be constructed in $\mathcal{O}(|W|d\log n)=\mathcal{O}(|P|d^2\log n)$ time by sequentially computing the simplices $\sigma_x^i$ for all the $x\in P$, i.e., by parsing the matrix $D$ one row at a time. From the discussions about the robustness of CSD discussed in Section \[Performance\], we know that we could lazy insert all the simplices in $W$ to the CSD and it would behave exactly like in the scenario wherein only the simplices in $M$ (which is a subset of $W$) are inserted. This lazy insertion of all the simplices in $W$ can be done in time $\mathcal{O}(|P|d^2\log \Psi)$. After the construction, we may perform a clean-up operation to remove the redundant simplices that were inserted.

Conclusion {#Conclusion}
==========

In this paper, we introduce a new data structure called the Critical Simplex Diagram (CSD) to represent filtrations of simplicial complexes. In this data structure, we store only those simplices which are critical with respect to the filtration value, i.e., we store a simplex if and only if all its cofaces are of a (strictly) higher filtration value than the filtration value of the simplex itself. We then show how to efficiently perform basic operations on simplicial complexes by only storing these (critical) simplices. This is summarized in Table \[tab:OperationsonMSD\]. Finally, we showed how to (quickly) construct the CSD representation of flag complexes and relaxed Delaunay complexes.

As a future direction of research, we would like to obtain better bounds on $\Psi$ and $\Gamma_i$ for specific complexes such as the Rips complex or the relaxed Delaunay complex by assuming some notion of geometric regularity. Also, it would be interesting to obtain lower bounds on the various query times (such as membership, insertion/removal), by assuming an optimal storage of $\mathcal{O}(\kappa d\log n)$ ($\kappa=|M|$ is the number of critical simplices). From the standpoint of practice, we would like to find fast construction algorithms under the CSD representation for other simplicial complexes of interest such as the alpha complex and the relaxed witness complex. Finally, we would like to implement this data structure and check its performance versus the Simplex Tree in practice.

Acknowledgements {#acknowledgements .unnumbered}
----------------

We would like to thank the anonymous reviewers whose comments helped us improve the presentation of the paper.

[^1]: This work was partially supported by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).

[^2]: This work was partially supported by Irit Dinur’s ERC-StG grant number 239985.

[^3]: i.e., two complexes which either differ on the simplices contained on the complex or on the filtration value of a simplex contained in both complexes.

[^4]: up to constant additive factors in the worst case.

[^5]: This complex was referred to as the $\rho$-relaxed strong Delaunay complex in [@D08] and as the $\rho$-relaxed Delaunay complex in [@BDG15].
