Jean-Daniel Boissonnat
email: jean-daniel.boissonnat@inria.fr.

An Efficient Representation for Filtrations of Simplicial Complexes

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.

Introduction

Persistent homology is a method for computing the topological features of a space at different spatial resolutions [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF]. 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 [START_REF] Boissonnat | The compressed annotation matrix: An efficient data structure for computing persistent cohomology[END_REF][START_REF] Boissonnat | Computing persistent homology with various coefficient fields in a single pass[END_REF], 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 [START_REF] Tamal | Computing topological persistence for simplicial maps[END_REF]. Persistent homology found applications in many areas ranging from image analysis [START_REF] Gunnar | On the local behavior of spaces of natural images[END_REF][START_REF] Perea | A klein-bottle-based dictionary for texture representation[END_REF], to cancer research [ABD + 12], virology [START_REF] Minhow | Topology of viral evolution[END_REF], and sensor networks [START_REF] Silva | Coverage in sensor networks via persistent homology[END_REF].

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 [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF]. 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 [START_REF] Attali | Efficient data structure for representing and simplifying simplicial complexes in high dimensions[END_REF]. A dual idea is to store only the simplices that are maximal for the inclusion. Following this last idea, Boissonnat et al. [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF] 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 com-plex 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, . . . , 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.

Theorem 1. Let K be a d-dimensional simplicial complex. Let κ 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 κd.

• The cost of basic operations (such as membership, insertion, removal, elementary collapse, etc.) through the CSD representation is

Õ((κ • d) 2 ).
The proof of the above two items follows from the discussions in Section 3.3 and Section 3.4 respectively. We would like to point out here that while the cost of static operations such as membership is only Õ(d) for the Simplex Tree, to perform any dynamic operation such as insertion or removal, the Simplex Tree requires exp(d) time. Moreover, as shown in Section 3.4, the cost of most basic operation using CSD is linear in κ.

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 κ critical simplices in time O κn 2.38 . Additionally, we provide a matrix-parsing algorithm for building d-dimensional relaxed Delaunay complexes over the witness set W in 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 2, 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 3, 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 4, we give a new algorithm for the construction of Flag complexes. In Section 5, we give a new algorithm for the construction of relaxed Delaunay complexes. Finally, in Section 6, we conclude by highlighting some open directions for future research. The filtration value of a higher dimensional simplex is the largest filtration value of its edges.

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 ∈ V ⇒ {p} ∈ K 2. σ ∈ K, τ ⊆ σ ⇒ τ ∈ K
Each element σ ∈ K is called a simplex or a face of K and, if σ ∈ K has precisely s + 1 elements (s ≥ -1), σ is called an s-simplex and the dimension of σ, denoted by d σ 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 σ = {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 σ and the facets of σ are its proper faces of maximal dimension. A simplex τ ∈ K admitting σ as a face is called a coface of σ. 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 (τ, σ) in K where τ is the only coface of σ.

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 K(n, d, k, m), and K denotes a simplicial complex in K(n, d, k, m).

In Figure 1 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, . . . , t} and t = {0, 1, . . . , 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 → R satisfying f (τ ) ≤ f (σ) whenever τ ⊆ σ [EH10]
. Moreover, we will assume that the filtration values range over t . We say that a simplex σ ∈ K is a 'critical simplex' if for all cofaces τ of σ we have f (σ) < f (τ ). For example, the critical simplices in the example described in Figure 1

Lower Bounds

Boissonnat et al. proved the following lower bound on the space needed to represent simplicial complexes [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF].

Theorem 2. [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF] Consider the class of all d-dimensional simplicial complexes with n vertices containing k maximal simplices, where d ≥ 2 and k ≥ n + 1, and consider any data structure that can represent the simplicial complexes of this class. Such a data structure requires log ( n/2 d+1 ) k-n bits to be stored. For any constant ε ∈ (0, 1) and for 2 ε n ≤ k ≤ n (1-ε)d and d ≤ n ε/3 , the bound becomes Ω(kd log n).

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

Lemma 3. Let β = t+1 d+1 be greater than 1. For any simplicial complex K of dimension d containing m simplices, the number of distinct filtrations f : K → t is at least β m . If β > (d + 1) δ for some constant δ > 0 then, any data structure that can represent filtrations of the class of all d-dimensional simplicial complexes containing m simplices requires Ω(m log t) bits to be stored.

Proof. Let us fix a simplicial complex K of dimension d containing m simplices. We will now build functions f i : K → t . For every i ∈ β m -1 , let b(i) be the representation of i as a m digit number in base β and let b(i) j be the j th digit of b(i). Let g be a bijection from

K to [m]. We define f i (σ) = d σ • β + b(i) g(σ) + 1.
We note that all the f i s are distinct functions as for any two distinct numbers i and j in β m -1 , we have that b(i) = b(j). Finally, we note that each of the f i s is a filtration of K. This is because, for any two simplices τ, σ ∈ K, such that τ ⊂ σ (i.e., d τ < d σ ), and any i ∈ β m -1 , we have that

f i (τ ) ≤ (d τ + 1) • β < d σ • β + 1 ≤ f i (σ).
It follows that there are at least β m distinct filtrations of K. By the pigeonhole principle, we have that any data structure that can represent filtrations of K requires log (β m ) bits. It follows that if β > (d + 1) δ for some constant δ > 0 then β > (t+1) δ (β-1) δ . Thus, any data structure that can represent filtrations of K requires at least δ 1+δ • m log(t + 1) = Ω(m log t) bits to be stored.

Even if t

d ≤ 1, we can show that any data structure that can represent d-dimensional simplicial complexes containing m simplices with filtration ra nge t requires Ω( m √ 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] The lower bounds in Lemma 3 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 2 and combine it with the ideas from the proof of Lemma 3, to obtain the following lower bound.

Theorem 4. Consider the class of all simplicial complexes on n vertices of dimension d, associated with a filtration over the range of t , such that the number of critical simplices is κ, where d ≥ 2 and κ ≥ n+1, and consider any data structure that can represent the simplicial complexes of this class. Such a data structure requires log ( n/2 d+1 ) κ-n t κ-n bits to be stored. For any constant ε ∈ (0, 1) and for 2 ε n ≤ κ ≤ n (1-ε)d and d ≤ n ε/3 , the bound becomes Ω(κ(d log n + log t)).

Proof. The proof of the first statement is by contradiction. Let us define h = κn ≥ 1 and suppose that there exists a data structure that can be stored using only s < log α def = log ( n/2 d+1 ) κ-n t h bits. We will construct α simplicial complexes (associated with a filtration), all with the same set P of n vertices, the same dimension d, with exactly κ maximal simplices, and with a filtration over the range of t . By the pigeon hole principle, two different simplicial complexes * , say K and K ′ , are encoded by the same word. So any algorithm will give the same answer for K and K ′ . But, by the construction of these complexes, there is either a simplex which is in K and not in K ′ or there is a simplex whose filtration value in K is different from the simplex's filtration value in K ′ . This leads to a contradiction.

The simplicial complexes and their associated filtration are constructed as follows. Let P ′ ⊂ 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 β = ( n/2 d+1 ) h in number, since the total number of maximal d dimensional simplices is n/2 d+1 and we choose h of them. Let us call them Γ 1 , . . . , Γ β . We now extend each Γ i so as to obtain a simplicial complex whose vertex set is P and has exactly κ 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 Γ i , vert(Γ i ), may be a strict subset of P ′ . Let its cardinality be n 2r i and observe that 0 ≤ r i < n 2 . Consider now the complete graph on the n 2 + r i vertices of P \ vert(Γ i ). Any spanning tree of this graph gives n 2 + r i -1 edges and we arbitrarily choose n 2r i + 1 edges from the remaining edges of the graph to obtain n distinct edges spanning over the vertices of P \ vert(Γ i ). We have thus constructed a 1-dimensional simplicial complex K i on the n 2 + r i vertices of P \ vert(Γ i ) with exactly n maximal simplices. Finally, we define the complex Λ i = Γ i ∪ K i that has P as its vertex set, dimension d, and κ 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 Λ i , i = 1, • • • , β, 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:

log    n/2 d + 1 κ -n t κ-n    ≥ log n (d+1)(κ-n) 2 (d+1)(κ-n) (d + 1) (d+1)(κ-n) (κ -n) (κ-n) + (κ -n) log t = (d + 1)(κ -n) log n -(d + 1)(κ -n) -(d + 1)(κ -n) log(d + 1) -(κ -n) log(κ -n) + (κ -n) log t > (d + 1)(κ -n) log n -3(d + 1)(κ -n) -(d + 1)(κ -n) log d -(κ -n) log κ + (κ -n) log t ≥ (d + 1)(κ -n)(log n -3 -log d) -(κ -n)(1 -ε)d log n + (κ -n) log t ≥ dε(κ -n) log n + (κ -n) log n -(d + 1)(κ -n) 3 + ε 3 log n + (κ -n) log t ≥ 2ε 3 1 - ε 2 κd log n + 1 - ε 2 κ log t + 1 - ε 2 κ log n -3d 1 - ε 2 κ -1 - ε 2 κ 3 + ε 3 log n = Ω(κ(d log n + log t))
We note that in the above computation, the first inequality is obtained by applying the following bound on binomial coefficients:

n d ≥ n d d .

Simplex Tree

Let K ∈ 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 σ = {v ℓ 0 , . . . , v ℓ j } be a simplex, where v ℓ i are vertices of K and

ℓ i ∈ [n] and ℓ 0 < • • • < ℓ j . σ is represented by the word [σ] = [ℓ 0 , • • • , ℓ 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 [σ] = [ℓ 0 , •••, ℓ j ] start from the root, and follow the path containing successively all labels ℓ 0 , •••, ℓ i , where [ℓ 0 , • • •, ℓ i ] denotes the longest prefix of [σ] already stored in the ST. Next, append to the node representing [ℓ 0 , • • •, ℓ i ] a path consisting of the nodes storing labels ℓ i+1 , • • •, ℓ j . The filtration value of σ denoted by f (σ) is stored inside the node containing the label ℓ j , in the above path. In Figure 2, we give ST for the simplicial complex shown in Figure 1.

If K consists of m simplices (including the empty face) then, the associated ST contains exactly m nodes. Thus, we need Θ(m(log n + log t)) space/bits to represent the nodes in ST (since each node stores a vertex which needs Θ(log n) bits to be represented and also stores the filtration value of the simplex that the node corresponds to, which needs Θ(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 3. 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 σ 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 O(d σ log n) and therefore all operations which primarily determine on the X,0 1,0 2,0 3,0 4,0 5,0 6,0 2,5 3,3 4,2 3,5 4,3 4,3 5,2 6,2 6,1 3,5 4,5 4,3 4,5 6,2 4,5

Figure 2: Simplex Tree of the simplicial complex in Figure 1. In each node, the label of the vertex is indicated in black font and the filtration value stored by the simplex is in brown font.

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 1.

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

In this section, we introduce the Critical Simplex Diagram, CSD(K), which is an evolved version of SAL [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF]. 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

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 1, we have

M 0 = {1, 2, 3, 4, 5, 6}, M 1 = {[56]}, M 2 = {[14], [356]}, M 3 = {[134],
[24]}, M 4 = ∅, 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 Ψ max (i) the subset of simplices of M h that contain vertex i for all possible

(0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (2,2) (3,1)
(5,1)

(3,2)

(5,1)

(3,1)

(2,1)

(5,1)

(2,2)

(3,1) (3,2)
(5,1)

(1,1)

(2,1)

(1,1)

(2,1)

A 1 A 2 A 3 A 4 A 5 A 6
Figure 3: Critical Simplex Diagram for the complex in Figure 1. The shaded region in each A i corresponds to A ⋆ i .

h ∈ t . In other words,

Ψ max (i) = {σ ∈ K i ∈ σ, f (σ) < f (τ ), ∀τ ∈ K, σ ⊂ τ }. Let Ψ = max i∈[n] |Ψ max (i)|.
We denote by Γ 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 ≥ Γ 0 ≥ Γ 1 ≥ • • • ≥ Γ d = 1, Γ 0 ≤ Ψ ≤ m.
Moreover, when t = 0, we have Ψ = Γ 0 . We describe the construction of CSD below.

Construction

We initially have n empty arrays A 1 , . . . , 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 , . . . , 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 3 we have the CSD representation of the simplicial complex of Figure 1, 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 ∈ t , we build the CSD by inserting the simplices in M h in decreasing ordering of h. For every simplex σ = v ℓ 0 • • • v ℓ j in M h , we associate a unique key generated using a hash function H, H(σ) ∈ [|M h |], and insert the nodes with label (h, H(σ)) in to the arrays A ℓ 0 , . . . , A ℓ j . For every j ′ ∈ [j], we introduce an edge between (h, H(σ)) in A ℓ 0 and (h, H(σ)) in A ℓ j ′ . In other words, σ, 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 σ + 1 nodes where v ℓ 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 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 3). Inside each A i , we first sort nodes based on whether they are in A ⋆ i or not. Further, inside A ⋆ i and inside A i \A ⋆ i , we sort the nodes according to the lexicographic order of their labels. We note that A ⋆ i is a contiguous subarray of A i , i.e., all consecutive elements in A ⋆ i are also consecutive elements in A i , as can be observed in Figure 3.

We remark here that we use a hash function 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

The number of nodes in each A i is at most Ψ, and the total number of nodes in CSD, we denote by |CSD|, is at most Ψ • n. Note that the number of edges in CSD is also at most Ψ • 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 3.1 is the union of all M h . The actual relation between Ψ and |M | can be stated as follows:

n i=1 |Ψ max (i)| = σ∈M (d σ + 1).
Further, in each node we store a filtration value (which requires log t bits) and a hashed value (which requires max In the case of CSD, we are interested in the value of Γ 0 and Ψ which we use to estimate the worst-case cost of basic operations in CSD, in the following subsection.

Operations on the Critical Simplex Diagram

Let us now analyze the cost of performing basic operations on 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

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 O(log |A i |). Below we will discuss how to implement A ⋆ i and the same will hold for A i \ A ⋆ i which we treat separately. Each subarray of A ⋆ i 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 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 , followed by

A i \ A ⋆ i .

Intersecting arrays

Let σ be a simplex of dimension d σ and denote its vertices by v ℓ 0 , . . . , v ℓ dσ . We will need to compute A σ , defined as the intersection of A ℓ 0 , . . . , A ℓ dσ , and A ⋆ σ , defined as the intersection of A ⋆ ℓ 0 , . . . , A ⋆ ℓ dσ . To compute A σ , we first find out the array with fewest elements amongst A ℓ 0 , . . . , A ℓ dσ . Then, for each element x in that array, we search for x in the other d σ arrays, which can be done in time O d σ log max i |A ℓ i | . Hence A σ can be computed in time

O min i |A ℓ i | d σ log max i |A ℓ i | . As we have seen before, |A ℓ i | ≤ Ψ ≤ m.
We can compute A ⋆ σ in the same way as described above for A σ in time

O min i |A ⋆ ℓ i | d σ log max i |A ⋆ ℓ i | . As we have seen before, |A ⋆ ℓ i | ≤ Γ 0 ≤ k.

Static Operations on the Critical Simplex Diagram

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 Ψ (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 Γ 0 .

Membership of a Simplex

We first observe that σ ∈ K if and only if A ⋆ σ = ∅. This is because if σ ∈ K, then there exists a maximal simplex in K which contains σ. The star graph associated to this maximal simplex has nodes in all the A ⋆ ℓ i , and all those nodes have the same label. This implies that A ⋆ σ = ∅, and the converse is also true. It follows that determining if σ is in K reduces to computing A ⋆ σ and checking whether it is non-empty. This procedure is very similar to the analogous procedure using SAL [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF]. Therefore, membership of a simplex can be determined in time O(d σ Γ 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

Given a simplex σ of K we want to access its filtration value f (σ). We observe that f (σ) is the minimal filtration value of the nodes in A σ since the filtration function is monotone w.r.t. inclusion. Hence, accessing the filtration value of σ reduces to computing A σ . Therefore, the filtration of a simplex can be determined in time O(d σ Ψ log Ψ).

For example, consider the CSD in Figure 3. We have to find the filtration value of σ = [134] in the complex of Figure 1. We see that A 1 ∩ A 3 ∩ 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

Given a simplex σ = v l 0 , ..., v l dσ , we could procure the filtration value of its d σ + 1 facets by the access filtration value query, and thus requiring a total running time of O(d 2 σ Ψ log Ψ). However, we will modify the access filtration value query to obtain filtration value of the

d σ + 1 facets of σ in running time of O(d σ Ψ log Ψ). Let A ℓr = argmin i |A ℓ i |, for some r ∈ d σ . Let
B be a subset of A ℓr such that every element of A ℓr which appears in exactly d σ -1 of the sets in A ℓ 0 , . . . , A ℓ r-1 , A ℓ r+1 , . . . , A ℓ dσ is in B. We can identify B in time O(|A ℓr |d σ log Ψ). To each entry (s, x) in B we associate the index of the set A ℓ 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

σ ′ = v ℓ 0 • • • v ℓ j-1 • v ℓ j+1 • • • v ℓ dσ ,
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 σ ′ is f (σ). This computation for all the d σ + 1 facets requires a total time of O(|B| log |B| + d σ log |B|) = O((Ψ + d σ ) log Ψ). Therefore the total running time is O(d σ Ψ log Ψ).

Computing Filtration Value of Cofaces of codimension 1

Given a simplex σ, we perform the access filtration value query to obtain all critical simplices that contain σ. We traverse the star graphs that contain the nodes in A σ , to list these critical simplices in time O(dΨ log Ψ). From this list, we can compute the filtration value of all the cofaces of σ of codimension 1 in O(dΨ log Ψ) time.

Dynamic Operations on the Critical Simplex Diagram

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 is the operation of inserting σ into the complex without checking if there are simplices in the complex which were previously critical but are now faces of σ with the same filtration value as f (σ). Additionally, in the case of lazy insertion, we assume that the information about σ 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 O(d σ log Ψ) time (i.e., the cost of updating the arrays).

Insertion

Suppose we want to insert a simplex σ with filtration value f (σ) such that any coface of σ in K has a filtration value larger than f (σ). The insertion operation consists of first checking if σ is a maximal simplex in K by the is maximal query. If σ 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 σ. If σ is not maximal, then we just have to lazy insert σ into the complex. We remark here that we do not need to remove the faces of σ which were previously critical simplices and had filtration value at least f (σ) 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 3.5).

Suppose σ is a maximal simplex then, insert the star graph corresponding to σ in A ⋆ ℓ 0 , . . . , A ⋆ ℓ dσ . Updating the arrays A ℓ i takes time O(d σ log Ψ). Next, we have to check if there exist maximal simplices in K which are now faces of σ, and either remove them if their filtration value is equal to f (σ) or move them outside A ⋆ ℓ i if their filtration value is strictly less than that of f (σ). We restrict our search for faces of σ which were previously critical by looking for every vertex v in σ, at the set of all maximal simplices which contain v, denoted by Z v . We can compute Z v in time O(d σ Γ 0 log Γ 0 ). Then, we compute ∪ v∈σ Z v whose size is at most (d σ + 1)Γ 0 and check if any of these maximal simplices are faces in σ (can be done in O(d 2 σ Γ 0 ) time). If such a face of σ in ∪ v∈σ Z v has filtration value equal to f (σ) then, we remove that connected component. To remove all such connected components takes time O(d 2 σ Γ 0 log Γ 0 ). On the other hand, if filtration value of the face is less than f (σ) then, we will have to move the node outside A ⋆ ℓ i and place it appropriately to maintain the sorted structure of A ℓ i . To reallocate all such connected components takes time O(d 2 σ Γ 0 log Ψ). Summarizing, to handle removal of face or reallocating the concerned faces of σ which were previously maximal takes time at most O(d 2 σ Γ 0 (log Γ 0 + log Ψ)). If σ is not a maximal simplex then, we insert the star graph corresponding to σ in A ℓ 0 , . . . , A ℓ dσ . Updating the arrays A ℓ i takes time O(d σ log Ψ). Therefore, the total running time in this case is O(d σ log Ψ). Therefore, the total time for insertion is

O(d 2 σ Γ 0 (log Γ 0 + log Ψ)) = O(d 2 σ Γ 0 log Ψ).

Removal

To remove a face σ, we first perform an access filtration value query of σ (requires O(Ψd σ log Ψ) time). We deal with the simplices in A ⋆ σ and A σ \ A ⋆ σ separately. For every simplex τ ∈ A ⋆ σ , i.e., for every coface τ of σ in K which is a maximal simplex, we remove its corresponding star graph from the CSD. Since there are at most Γ dσ maximal simplices which contain σ, the above removal of star graphs can be done in O(Γ dσ d log Ψ) time. Next, for each maximal simplex τ (containing σ) that we removed, and for every i ∈ d σ we check if the facet of τ obtained by removing v ℓ i-1 from τ , is a maximal simplex. If yes, we lazy insert the facet as a maximal simplex with the same filtration value as τ . If no, we lazy insert the facet as a non-maximal simplex with the same filtration value as τ . Note that in order to check if the above mentioned d σ +1 facets of τ are maximal, we do not have to make d σ +1 is maximal queries, but can do the same checking in O(Γ dσ d log Ψ) time by using the same idea that is described in the 'computing filtration value of facets' paragraph in Section 3.4.2. Additionally, we remark here that we can lazy insert the above selected facets of the the critical cofaces of σ, 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 τ ∈ A σ \ A ⋆ σ i.e., for every coface τ of σ in K which is a critical (not maximal) simplex, we replace its corresponding star graph by star graphs of its d σ + 1 facets with the same filtration value, where the i th facet is obtained by removing v ℓ i-1 from τ . Introducing a star graph and updating the arrays A ℓ i takes time O(d τ log Ψ). Further, if σ is a critical simplex (can be checked by is critical query) then, we know that there is a connected component representing σ. 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 O(dd σ Ψ log Ψ). We note here that as before, we lazy insert the above selected facets of the the critical cofaces of σ, without checking if the facets themselves are critical.

Therefore, the total time for insertion is O(Ψdd

σ log Ψ + Γ dσ d σ d log Ψ + Γ 2 dσ d log Ψ) = O((Ψd σ + Γ 2 dσ )d log Ψ).

Elementary Collapse

A simplex τ is collapsible through one of its faces σ, if τ is the only coface of σ. Such a pair (σ, τ ) is called a free pair, and removing both faces of a free pair is an elementary collapse. Given a pair of simplices (σ, τ ), to check if it is a free pair is done by obtaining the list of all maximal simplices which contain σ, through the membership query (costs O(d σ Γ 0 log Γ 0 ) time) and then checking if τ is the only member in that list with codimension 1. If yes, then we remove τ from the CSD by just removing all the nodes in the corresponding arrays in time O(d τ log Ψ).

Next, for every facet σ ′ of τ other than σ, we check if σ ′ is a critical simplex (post removal of τ ) by asking the is critical query. If yes, we lazy insert σ ′ in time O(d σ log Ψ). Finally, if σ is a critical simplex then, we remove it in the same way we removed τ and for every facet of σ we similarly check if it is a critical simplex (post removal of σ) by asking the is critical query. If yes, we lazy insert that facet in time O(d σ log Ψ). Thus, the total running time is

O(d σ (d σ Ψ log Ψ + Γ 0 log Γ 0 )) = O(d 2 σ Ψ log Ψ).

Summary

We summarize in Table 1 the asymptotic cost of basic operations discussed above and compare it with ST, through which the efficiency of CSD is established.

ST CSD

Storage Θ(m log(nt)) O(Ψn log(Ψt)) Membership of a simplex σ Θ(d σ log n) O(d σ Γ 0 log k) Access Filtration Value Θ(d σ log n) O(d σ Ψ log Ψ) Computing Filtration Value of Facets O(d 2 σ log n) O(d σ Ψ log Ψ) Computing Filtration Value of Cofaces of codimension 1 Θ(nd σ log n) O(dΨ log Ψ) Lazy Insertion of a simplex σ - O(d σ log Ψ) Insertion of a simplex σ O(2 dσ d σ log n) O(d 2 σ Γ 0 log Ψ) Removal of a face O(m log n) O((Ψd σ + Γ 2 dσ )d log Ψ) Elementary Collapse Θ(nd σ log n) O(d 2 σ Ψ log Ψ)
Table 1: Cost of performing basic operations on CSD in comparison with ST.

If the number of critical simplices is not large then |CSD| is smaller than |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 Ψ 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 Ψ or Γ 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 Γ 0 and not Ψ (recall that Γ 0 ≤ Ψ). 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

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 O(kd log k) memory space, which matches the lower bound in Theorem 2, when k = n O(1) . In this case, CSD is very similar to SAL [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF]. Marc Glisse and Sivaprasad S. [GS] 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. , Ψ, and Ψ avg for the simplicial complex generated from the above data set with increasing values of t. Additionally, we provide Γ avg 0 which is the number of maximal simplices that an average vertex contains and Ψ avg which is the average size of A i .

CSD is also a compact data structure to store filtrations, as its size matches (up to constant factors) the lower bound of Ω(|M |(d log n + log t)) in Theorem 4. Moreover, if Ψ is small, CSD is not only a compact data structure since |CSD| is upper bounded by Ψn, but, as shown in Table 1, 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 Ψ that reflects some "local complexity" of the simplicial complex. In the worst-case, Ψ = Ω(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, Ψ 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 R 5 and constructed its Rips filtration (see Section 4 for definition) using libraries provided by the GUDHI project [START_REF]GUDHI User and Reference Manual[END_REF]. We computed Γ 0 and Ψ 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 2 below, the values of |ST| and |CSD| for the various filtration ranges of the Rips complex constructed above. In Figure 4 is a graphical illustration of the data.

We note from Table 2 that Γ 0 is significantly smaller than k(≈ 2.7 × 10 4 ), and also that Γ avg 0 is much smaller than Γ 0 . Also, from Figure 4, it is clear that there is an order of magnitude gap between |CSD| and |ST|. Next, we note that Ψ is remarkably smaller than m (even notably smaller than n), and this implies efficient implementation of all operations. More importantly, we remark here that Ψ avg = |CSD|/n is at most 77.8 in the above experiment. Finally, we observe that despite increasing t at a rapid rate, |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. The blue curve corresponds to log 10 |CSD| on the left y axis plotted against log 10 t on the x-axis. The red curve corresponds to Ψ on the right y axis plotted against log 10 t on the x-axis. The green curve(line) corresponds to log 10 |ST| on the left y axis plotted against log 10 t on the x-axis.

Local Sensitivity of the Critical Simplex Diagram

It is worth noting that while the cost of basic operations are bounded using Γ 0 and Ψ, the actual cost is bounded by parameters such as min 3) to get a better estimate on the cost of these operations. These parameters are indeed local. To begin with, min i |A ⋆ ℓ i | captures the local information about a simplex σ sharing a vertex with other maximal simplices of the complex. More precisely, it is the minimum, over all the vertices of σ, of the largest number of maximal simplices that contain the vertex. If σ has a vertex which is contained in a few maximal simplices then, min

i |A ⋆ ℓ i | is small. Similarly, min i (|A ℓ i |)
is the minimum, over all the vertices of σ, 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 σ -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

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 σ ∈ K from f (σ) to s σ (< f (σ)). In the case of ST, we will have to modify the filtration value inside the node containing σ and additionally check (and modify if needed) its faces in decreasing order of dimension. This requires time Θ(2 dσ d σ (log n + log t)).

However, in the case of CSD, we can perform a lazy insertion of σ into CSD in time O(d σ log Ψ), and the data structure is robust to such an insertion. This is because, all the operations can be performed correctly and with the same † efficiency after the lazy insertion (even if some previously critical simplices need to be removed due to the lazy insertion of σ). For instance, consider the is critical query on some simplex τ . If τ was a face of σ before modifying f (σ) then, the minimal filtration value of the nodes in A τ correctly gives the filtration value of τ as s σ will now be one of the entries in A τ . Otherwise, if τ was not a face of σ then the filtration value of τ remains unchanged, as the lazy insertion of σ 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 3.4.3. We remark here that if we lazy insert r simplices then in the worst case, Ψ grows to r + Ψ. In other words, the presence of redundant simplices, implies that the efficiency dependence will now be on r + Ψ instead of Ψ, but the redundancy will not affect the correctness of the operations.

A Sequence of Representations for Simplicial Complexes and their Filtrations

Boissonnat et al. [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF] 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 Λ , we had Λ i = i-SAL (SAL referred to earlier in this paper is equal to 1-SAL). Further, they note that in the i 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-SAL, i ∈ 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 Γ i which decreases as i increases.

We note here that CSD described in this paper is exactly the same as 0-SAL, when t = 0 (we ignore the structure of the connected component, which is a path in SAL but a star in CSD). Therefore, CSD supersedes 0-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 Λ , 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 Π , where Π 0 = CSD and Π i = t j=0 i-SAL(M j ), for all i ∈ N. Further, for all i ∈ N, we will refer to the data structure Π i by the name i-CSD (we will continue to refer to 0-CSD as CSD). As we move along the sequence Π, 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 Γ i which decreases as i increases. Additionally, we gain efficiency in accessing filtration value of a simplex as the complexity no longer depends on Ψ = Ψ 0 but on a smaller parameter, Ψ 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 [GS] for Data Set mentioned in Section 3.4, and then performed insertion and removal of random simplices, and contracted randomly † up to constant additive factors in the worst case. 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-CSD is the best data structure in the CSD family (for every i ∈ N).

Construction of Flag Complexes

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, • ) 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 R r (P ) where a simplex σ ∈ R r (P ) if and only if pq ≤ 2r for every pair of vertices of σ. 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 [CCG + 09].

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 ∆ denote the maximum degree of the vertices of G. To represent K using ST, Boissonnat and Maria [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF] propose computing and inserting the ℓ-skeleton of K into the ST and incrementally increasing ℓ from 1 to d. Therefore, the time for construction of the ST representing the flag complex is 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 3.2 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 O(k • n ω ) [MU04],
where ω < 2.38 [START_REF] François | Powers of tensors and fast matrix multiplication[END_REF] is the matrix multiplication exponent, i.e., n ω is the time needed to multiply two n × n matrices. We store these maximal simplices in a Prefix Tree (like MxST of [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF]). 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 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 O S f (e i ) d log n and then computing M f (e i ) will require time O S f (e i ) • d • M f (e i ) using the best known algorithms in literature [Yel92, YJ93, Pri97, 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 O M f (e i ) ∆ ω using the algorithm presented by Makino and Uno [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF] 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 ∆ + 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 O M f (e i ) d log n by checking each simplex σ in M f (e i ) with the Prefix tree built in the preprocessing step in time O(d σ 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 or not, within each A j . This takes time O M f (e i ) d log Ψ .

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.

Performance of CSD for Flag Complexes

We would like to note here that the case when k = O(n), was argued to be of particular interest by Boissonnat et al. [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF]. It can be observed in flag complexes, constructed from planar graphs and expanders [START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF], and in general, from nowhere dense graphs [START_REF] Grohe | Characterisations of nowhere dense graphs (invited talk)[END_REF], and also from chordal graphs [START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF]. Generalizing, they noted that for all flag complexes constructed from graphs with degeneracy 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 O(1) [START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF]. We add to this list of observations by noting that the flag complexes of K ℓ -free graphs have at most max{n, n∆ ℓ-2 /2 ℓ-2 } maximal simplices [START_REF] Prisner | Graphs with few cliques[END_REF], where ∆ is the maximum degree of any vertex in the graph. Thus, when ∆ and ℓ are constants, we have k = O(n). Finally, we note that the flag complexes of Helly circular-arc (respectively, circle) graphs [START_REF] Gavril | Algorithms on circular-arc graphs[END_REF][START_REF] Durn | Some new results on circle graphs[END_REF], and boxicity-2 graphs [START_REF] Spinrad | Efficient Graph Representations[END_REF] have k = n O(1) from Corollary 4 of [START_REF] Rosgen | Complexity results on graphs with few cliques[END_REF]. This encompasses a large class of complexes encountered in practice and if the number of maximal simplices is small, CSD is a very efficient data structure as Γ 0 ≤ k.

Adaptation to Simplicial Maps

A map F : K → K ′ is simplicial if for every simplex σ = {v 0 , v 1 , . . . , v k } in K, F (σ) = {F (v 0 ), F (v 1 ), . . . , F (v k )} is a simplex in K ′ . In this subsection, we discuss the adaptation of CSD to handle simplicial maps. For the purpose of demonstration, we consider Dey et al.'s [START_REF] Tamal | Computing topological persistence for simplicial maps[END_REF] application of simplicial maps to topological data analysis over Rips complexes. They construct a sequence of Rips simplicial complexes, K α i i connected by simplicial maps, where Proof. Let τ = {v 0 , . . . v dτ } be a critical simplex in M with filtration value f (τ ). By definition of Del ρ (Q, P ), we have that there exists a point x ∈ P which (f (τ )ρ/t)-strongly witnesses τ . Since τ is critical, we have that for every q ∈ Q \ τ , the following holds. ∀i ∈ d τ , | xv ixq | > ρf (τ )/t. Therefore, we have that for every i ∈ [d τ + 1], A(x, ℓ i x ) ∈ τ , or more precisely, σ dτ +1 x = τ .

The above lemma provides a characterization of Del ρ (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 [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF]), 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 Del ρ (Q, P ) through CSD.

Under the assumption that for any x, ℓ, D(x, ℓ) could be computed in O(1) time (i.e., D is computed as part of the preprocessing), Boissonnat and Maria [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF] described an algorithm to construct the ST representation of the relaxed witness complex. Their algorithm can be easily adapted to construct Del x for all the x ∈ P , i.e., by parsing the matrix D one row at a time. From the discussions about the robustness of CSD discussed in Section 3.5, 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 O(|P |d 2 log Ψ). After the construction, we may perform a clean-up operation to remove the redundant simplices that were inserted.

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 1. 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 Ψ and Γ 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 O(κd log n) (κ = |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.

Figure 1 :

 1 Figure 1: A simplicial complex with two maximal simplices : tetrahedron [1234] and triangle [356]. The filtration value of all vertices is 0. Filtration values of edges are shown in the figure.The filtration value of a higher dimensional simplex is the largest filtration value of its edges.

  are all the vertices, the edges [56], [14], and [24], the triangles [356] and [134], and the tetrahedron [1234].

  h∈ t log |M h | ≤ log m bits). We can thus upper bound the space needed to store the nodes of CSD by Ψ • n(log m + log t) or by |M | • 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 O(1) time. Thus, CSD matches the lower bound in Theorem 4, up to constant factors (as m = O n d ).

Figure 4 :

 4 Figure4: Values of log 10 |ST|, log 10 |CSD|, and Ψ for the simplicial complex generated from above data set with increasing values of t. The blue curve corresponds to log 10 |CSD| on the left y axis plotted against log 10 t on the x-axis. The red curve corresponds to Ψ on the right y axis plotted against log 10 t on the x-axis. The green curve(line) corresponds to log 10 |ST| on the left y axis plotted against log 10 t on the x-axis.

(

  |A ℓ i |), and Z v (introduced in the Insertion paragraph in Section 3.4.

  This entire construction takes time O(|M |(∆ ω + d log(kdΨ))) = O |M |n 2.38 , which is significantly better than that of constructing a representation of K by ST (which required time O(mnd log n)), as |M | can be considerably (exponentially) smaller than m.

  ρ w (Q, P ) in time O(tmd log n). In the case of CSD, we propose a new matrix-parsing algorithm which builds Del ρ (Q, P ) in time O(|P |d 2 log Ψ) (assuming an oracle to access D). It is easy to see that all the simplices in W can be constructed in O(|W |d log n) = O(|P |d 2 log n) time by sequentially computing the simplices σ i

Table 2 :

 2 Values of |CSD|, Γ 0

	No 0	t 0	|ST| 10,508,486 179,521 115 17.9 115 17.9 Γ 0 Γ avg 0 Ψ Ψ avg |CSD|
	1	10	10,508,486 490,071 115 17.9 329 49.0
	2	25	10,508,486 618,003 115 17.9 429 61.8
	3	100	10,508,486 728,245 115 17.9 723 72.8
	4	500	10,508,486 765,583 115 17.9 839 76.5
	5	2,000	10,508,486 774,496 115 17.9 860 77.4
	6	10,000	10,508,486 777,373 115 17.9 865 77.7
	7	25,000	10,508,486 778,151 115 17.9 865 77.8
	8	100,000	10,508,486 778,319 115 17.9 866 77.8
	9	1,000,000 10,508,486 778,343 115 17.9 866 77.8
	10 10,000,000 10,508,486 778,343 115 17.9 866 77.8

* 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.

Acknowledgements

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

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

† This work was partially supported by Irit Dinur's ERC-StG grant number 239985.

α i is the Rips parameter. The vertex set of K α i+1 i+1 is obtained by extracting a subset (net) of the vertex set of K α i i . They define a map π through which they map each vertex of K α i i to its closest vertex in K α i+1

i+1 . Next, they take α i+1 > α i so that the image of the edges of K α i i are edges in K α i+1 i+1 . Since the complexes are Rips complexes, the image of all the simplices of

i+1 . To implement this procedure using CSD, we need to collapse the vertices of vert(K

i+1 as given by π. 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 [START_REF] Boissonnat | The simplex tree: An efficient data structure for general simplicial complexes[END_REF] provide an essentially optimal algorithm running in O(md log n) time for edge contraction.

In the case of CSD, we will assume that |vert(K

i+1 entirely from scratch using the fast edge-deletion algorithm. For every vertex v in vert(K

i+1 ), we first build a set T v from the set of maximal simplices containing v as follows. If σ is a maximal simplex containing v, then we include the simplex τ = σ ∩ vert(K

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

i+1 , then we lazy insert the simplex. On the other hand, if the simplex was critical in

i+1 and reallocate appropriately. The total cost of performing the above procedure is O(|T |dΨ log Ψ), where

. This running time is significantly better than that of implementing the simplicial map using ST, as Ψ, and consequently Γ 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

Let Q be a finite subset of a metric space (P, • ) where P is a discrete point-set. Given a relaxation parameter ρ ≥ 0, we define the notion of being 'witnessed' as follows. A simplex σ = {q 0 , . . . , q dσ } ⊆ Q belongs to the relaxed Delaunay complex ‡ Del ρ (Q, P ) [dS08, BDG15] if and only if there exists x ∈ P such that for all q i ∈ σ, and for all q ∈ Q the following holds:

The parameter ρ defines a filtration on the relaxed Delaunay complexes, which has been used in topological data analysis. More explicitly, the filtration value of a simplex σ in Del ρ (Q, P ) is the smallest ρ ′ ≤ ρ, such that σ is in Del ρ ′ (Q, P ). For this entire section, we assume that the filtration range is t .

We define a matrix D of size |P | × |Q| as follows. For every x ∈ P and ℓ ∈ [|Q|] let D(x, ℓ) denote the ℓ th nearest neighbor of x in Q (ties are broken arbitrarily). For every x ∈ P , i ∈ t , let ℓ i x be the largest integer such that x -D(x, 1)x -D(x, ℓ i x ) ≤ ρi/t. Let σ i x = {D(x, 1), D(x, 2), . . . , D(x, ℓ i x )} and let W = σ i x x ∈ P, i ∈ t . We note below that M (recall notation from Section 3.1), the set of critical simplices in the complex is contained in W .

Lemma 5. M ⊆ W. ‡ This complex was referred to as the ρ-relaxed strong Delaunay complex in [dS08] and as the ρ-relaxed Delaunay complex in [START_REF] Boissonnat | A probabilistic approach to reducing algebraic complexity of delaunay triangulations[END_REF].


Amelia Carolina Sparavigna

Analysis of a natural honeycomb by means of an image segmentation

Keywords: Image Processing, Image Segmentation, Natural Structures, Bees, Animal Production Studies, Agricultural Science, Apis Mellifera, Cell Size, Brood Combs

The paper is applying a method of image segmentation to the study of the size of the natural honeycomb structures. The proposed segmentation is based on a thresholding of the original image of the honeycomb, which is turned into a binary black and white image. This binary image is further partitioned into multiple sets of pixels, known as "super-pixels", each containing a cell of the honeycomb. Each superpixel is characterized by a label, and to each label corresponds the size of the cell. In this manner, we can easily measure the size of each cell of the honeycomb and distinguish the cells of the workers from those of the drones.

A honeycomb is the hexagonal arrangement of cells made of wax, built by the bees in their nests. These cells are used to host the larvae and to store the honey. To secrete the wax for the honeycomb, the bees are largely consuming the honey that they produce [START_REF] Graham | The hive and the honey bee[END_REF]; for this reason, the wax structure is left intact, in its most part, when the honey is extracted by the beekeepers, so that the bees have not to reconstruct the entire structure. Let us observed that some wasps construct hexagonal combs too, but they are made of paper instead of wax. Some species, such as that of the Mexican honey wasps [START_REF] Sugden | Observations on foraging, population and nest biology of the Mexican honey wasp[END_REF], are storing the honey in the nest, technically forming a paper honeycomb. Sometimes then, the term "honeycomb" is also used for such structures. A common explanation exists as to why honeycomb is made of hexagonal cells. The hexagonal structure is giving a partition of a surface with equal-sized cells, which are minimizing the total perimeter of the cells. This is known as the "honeycomb conjecture" [START_REF] Hales | The honeycomb conjecture[END_REF][START_REF] Morgan | The hexagonal honeycomb conjecture[END_REF][START_REF] Peterson | The honeycomb conjecture[END_REF]. Thus, the bees need to use in the hexagonal structure the least material to create the cells within a given volume. Another explanation was given by D'Arcy Wentworth Thompson [START_REF] Thompson | On growth and form[END_REF]: the hexagonal shape simply results from the process of individual bees putting the cells together. The process is somewhat analogous to the lattice that we can see appearing in a field of soap bubbles. The individual cells have not a geometric perfection, and therefore, in a regular honeycomb we can observe deviations of a few percent from the "perfect" hexagonal shape [START_REF] Vv | Wikipedia, Honeycomb[END_REF]. Moreover, in the transition zones between the larger cells of drone comb and the smaller cells of worker comb, or when the bees encounter obstacles, the shapes are often distorted. When the cells are used as brood comb, the queen bee lays eggs in them. The cells for the brood comb vary in diameter: the size ranges between less than 4.6 millimeters to greater than 6 millimeters [START_REF] Vv | Wikipedia, Brood comb[END_REF]. As we can see in the Figure 1, the drone bees require the largest cell size. Some evidence suggests that a smaller cell enables faster development time from egg to a fully developed, adult bee [START_REF] Mcmullan | The influence of small-cell brood combs on the morphometry of honeybees (Apis mellifera)[END_REF]. A detailed discussion and data of the cell size are available from [START_REF] Bush | Natural cell size and its implications to beekeeping and Varroa mites[END_REF]. The cells in honeycombs has been recently studied also in [START_REF] Nazzi | The hexagonal shape of the honeycomb cells depends on the construction behavior of bees[END_REF]. In these references, the authors obtained the size of the cells by a direct inspection of the samples and by the use of a ruler. In fact, the measurement of all the cells is a quite long work; we could ask ourselves whether an automatic method, based on the image processing for instance, could be helpful in such studies. The answer is positive. Let us follow the approach of an image segmentation, as proposed in [START_REF] Sparavigna | A method for the segmentation of images based on thresholding and applied to vesicular textures[END_REF]. In image processing, a segmentation is a process of partitioning an image into multiple sets of pixels, that are defined as superpixels. Each super-pixel is characterized by a label or parameter. In [START_REF] Sparavigna | A method for the segmentation of images based on thresholding and applied to vesicular textures[END_REF], we have proposed a method for determining the super-pixels based on the thresholding of a grey-scale digital image. Thresholding is obtained using a clip-level (the threshold value), according to which the greyscale image is turned into a black and white image. First of all then, let us see how the Figure 1 becomes after its conversion in grey tones and thresholding. Here the result is given in the Figure 2. The cells which are crossed by the image frame have been removed. The black pixels of the Figure 2 are analyzed according to [START_REF] Sparavigna | A method for the segmentation of images based on thresholding and applied to vesicular textures[END_REF], to subdivide them in super-pixels. Each of the super-pixels has a different label. If we use the colour tones to render the super-pixels, the result is like that given in the Figure 3. As we can see in the Figure 3, each super-pixel corresponds to a cell of the honeycomb structure. It is therefore quite simple to deduce the size of each cell, because it is the size of the corresponding super-pixel. We can plot the areas (in pixels) corresponding to the labels (Figure 4). We can also plot the distribution of the super-pixels, and consequently their frequencies, for given sizes of the cells (Figure 5). From this plot, we can appreciate the regularity of the small cells, those of the workers, that we find in the honeycomb of the Figure 1. The drone cells have a larger distribution of sizes. In the following Figure 6, we are giving some of the areas of the super-pixels (let us note that the values are the numbers of black pixels composing the super-pixel).

Figure 1 :

 1 Figure 1: Here we can see a honeycomb containing transition from worker to drone cells. Where there is the transition, the bees make irregular and five-cornered cells, that in the image are marked with red dots. (Image Courtesy, 2011, Audrius Meskauskas, Wikipedia).

Figure 2 :

 2 Figure 2: Thresholding of the image in the Figure 1. The original image is converted into a greyscale image which is reduced to a black and white image. The cells which are crossed by the image frame are removed from the binary image.

Figure 3 :

 3 Figure 3: The black pixels are grouped into super-pixels. Each of them is colored with a different colour tone.

Figure 4 :

 4 Figure 4: Size (in pixels) of the super-pixels for the given labels.

Figure 5 :

 5 Figure 5: The distribution of the super-pixels according to their size.

Figure 6 :

 6 Figure 6: Some of the areas of the super-pixels. We see the numbers of black pixels composing the super-pixels.

The results given above are showing that we can use one of the fundamental methods of the image processing, the segmentation of the images [13,14], to evaluate the distribution, in size, of the natural honeycomb cells. The proposed approach can be interesting for the numerical and statistical analysis of the brood combs and the role of the size of the cells in the beekeeping [15][16][17][18].