Building Efficient and Compact Data Structures for Simplicial Complexes

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

We would like to thank Eylon Yogev for helping us with some of the experiments. We would like to thank the anaonymous reviewers for pointing out a mistake in the previous version of the proof of Lemma 8, and for helping us improve the presentation of the paper. We would like to thank Rajesh Chitnis for pointing out a short proof of Lemma 8. We would like to thank François Godi for pointing out a mistake in the analysis of the cost of the edge contraction operation for the Simplex Array List as it appeared in [8]. We would like to thank Marc Glisse for several comments on earlier versions of this paper and also for pointing out a tightening of the cost of the edge contraction operation for the Simplex Array List. We would like to thank Marc Glisse and Sivaprasad S. for implementing SAL and sharing their results with us. Finally, we would like to thank Dorian Mazauric for pointing out Theorem 2.

Authors and Affiliations

1. Geometrica, INRIA Sophia Antipolis-Méditerranée, 2004 route des Lucioles, BP 93, 06902, Sophia Antipolis, France

   Jean-Daniel Boissonnat

2. Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

   Karthik C. S.

3. Microsoft Research India, Bangalore, India

   Sébastien Tavenas

Corresponding author

Correspondence to Karthik C. S..

An extended abstract appeared in the proceedings of the \(31{\mathrm{st}}\) International Symposium on Computational Geometry.

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

Karthik C. S.: This work was partially supported by Irit Dinur’s ERC-StG Grant Number 239985. Some parts of this work were done at ENS Lyon and at University of Nice - Sophia Antipolis, and were supported by LIP fellowship and Labex UCN@Sophia scholarship respectively.

S. Tavenas: A part of this work was done at LIP, ENS Lyon (UMR 5668 ENS Lyon - CNRS - UCBL - INRIA, Université de Lyon).

Appendix 1: Adapted Hopcroft’s Algorithm

We precisely describe here Hopcroft’s algorithm adapted to the compression of ST to provide as output \({\mathcal {C}}(\mathrm {ST})\). The idea is to write the Simplex Tree as the Simplex Automaton: each vertex of the tree becomes a state in the automaton. Then, one just needs to reduce the Simplex Automaton using Hopcroft’s algorithm and finally obtain the compressed Simplex Tree by partitioning the states of the Minimal Simplex Automaton. We see in Fig. 4, the compressed Simplex Tree of the simplicial complex described in Fig. 1.

Appendix 2: Operations on the Maximal Simplex Tree

We provide below a list of basic operations on the MxST. In the following subsections we denote by \(T_{\mathrm {MxST}}\) the maximum time taken to search for particular children of any node in MxST (\(T_{\mathrm {MxST}}={\mathcal {O}}(\log n)\) for red–black trees).

1.1 Identifying the Maximal Cofaces of a Simplex

As seen in Sect. 4, a simplex \(\sigma \in K\) is implicitly stored in MxST(K) as a face of its (at most k) maximal cofaces. Identifying the maximal cofaces of a simplex means to find the leaves of MxST(K) that contain the maximal cofaces of \(\sigma \) and also to find, on each path from the root to such a leaf, the location of the vertices of \(\sigma \).

We formalize this by first defining a bijection f from the set of all maximal simplices of K to the set of all leaves in \(\mathrm {MxST}(K)\) and also define a function g that maps every simplex \(\sigma \in K\) to the set of all maximal simplices in K which contain \(\sigma \) (thus if \(f(\sigma )=\emptyset \) then \(\sigma \notin K\)). For simplicity, we will denote \(f(g(\sigma ))\) by \(L(\sigma )\) and \(\mid \) \(L(\sigma )\) \(\mid \) by k\(_\sigma \) from now on. Since identifying a simplex \(\sigma \) reduces to traversing MxST(K), this operation costs \({\mathcal {O}}(kdT_{\mathrm {MxST}})={\mathcal {O}}(kd\log n)\).

1.2 Insertion

Let \(\sigma \) be a simplex not in K and let \(K'\) be the complex obtained by adding \(\sigma \) and its subsimplices to K. Observe that \(\sigma \) is necessarily maximal in \(K'\) and write \(d_{\sigma }\) for the dimension of \(\sigma \). We describe how to insert \(\sigma \) in MxST. We first check if there exists maximal simplices in MxST(K) that are contained in \(\sigma \). This can be done in \({\mathcal {O}}(kd_{\sigma }T_{\mathrm {MxST}})\) time, by looking at the MxST truncated to depth \(d_\sigma \). If such simplices exist, we will need to delete them before inserting \(\sigma \), which takes time at most \({\mathcal {O}}(kd_{\sigma }T_{\mathrm {MxST}})\) (see analysis of step 3 of Algorithm 2). Then, we insert \(\sigma \) in MxST. This takes at most \({\mathcal {O}}(d_{\sigma }T_{\mathrm {MxST}})\) time, which is significantly better than the time taken for the Simplex Tree, which needs \({\mathcal {O}}(2^{d_\sigma }T_{\mathrm {MxST}})\) time. We conclude that the time for inserting \(\sigma \) is \({\mathcal {O}}(kd_{\sigma }T_{\mathrm {MxST}})={\mathcal {O}}(kd_\sigma \log n)\).

1.3 Removing a Face

Given a simplex \(\sigma \), we have to remove it (and its cofaces) from the MxST. We can perform the operation of removing simplices (the simplex and its cofaces) as described in Algorithm 2.

Step 1 was shown earlier to take \({\mathcal {O}}(kdT_{\mathrm {MxST}})\) time. Since \({\varGamma }\) is maximal, it is associated to a leaf in the tree. Let \(P({\varGamma })\) be the path from the root to the leaf associated to \(\sigma \). For removing a maximal simplex \({\varGamma }\), one needs to locate on \(P({\varGamma })\), the last node w such that the out–degree for the edges is strictly more than one (it corresponds to the last node which is shared with another maximal simplex). Then, one just has to delete the edge on the corresponding path going from w. So removing one maximal simplex (at step 3) takes time \({\mathcal {O}}(dT_{\mathrm {MxST}})\) (since we might have to potentially delete up to d nodes). At step 4, \(d_{\sigma }\) facets of \({\varGamma }\) need to be inserted and each insertion was shown earlier to be doable in time \({\mathcal {O}}(T_{\mathrm {MxST}}d_{{\varGamma }})\)) (since we do not have to check if there exists maximal simplices in MxST(K) that are contained in facets \({\varGamma }\)). The total algorithm costs time \({\mathcal {O}}(\)k\(_\sigma \) \( dT_{\mathrm {MxST}}+ \)k\(_\sigma \) \( T_{\mathrm {MxST}}d_{{\varGamma }} ) = {\mathcal {O}}(kd\log (n))\).

1.4 Elementary Collapse

An elementary collapse consists of removing both simplices of a free pair. It preserves the homotopy type of the complex. We break down the computation of an elementary collapse into 3 steps which is described in Algorithm 3.

It easily follows from the above results that Step 1 takes \({\mathcal {O}}(kd\log (n))\) time. As for the removing operation, step 2 is feasible in time \({\mathcal {O}}(dT_{\mathrm {MxST}})\) (see analysis of step 3 of Algorithm 2). For step 3, we have \(d_\tau \) facets to check if they are now maximal and then insert the ones that are indeed maximal. This can be done in time \({\mathcal {O}}(kdd_\sigma \log (n))\).

1.5 Edge Contraction

Edge contraction is another operation on simplicial complexes that preserves the homotopy type under certain conditions and which can be implemented on the MxST using the above operations. We break down the computation of an edge contraction into 3 steps which is described in Algorithm 4.

Steps 1 and 3 can be done in time \({\mathcal {O}}(kd\log n)\) (follows from our previous results). However, to perform step 2, we need to remove the simplices which were previously maximal, but are no longer maximal after the edge contraction. This can be done in time \({\mathcal {O}}(kd\cdot k^\prime )\) [27], where \(k^\prime \) is the number of maximal simplices after the edge contraction. So an edge contraction can be performed in time \({\mathcal {O}}(kd\log n+kdk^\prime )={\mathcal {O}}(kd(k+\log n))\). Finally, we note that the above algorithm is a multiplicative factor of \(k/\log n\) in the worst case away from the upperbound for MxST. For any k, d, let us consider the simplicial complex in Example 6.

Example 6

Let \(K\in {\mathcal {K}}(kd/4 + k/2 + d+1,k,d,m)\) be defined by the union of the sets of maximal simplices given below:

1. 1.

   \(\{1,2,\dots , d,d+i|1\le i\le k/2\}\).

2. 2.

   \(\{i\cdot d+1+k/2,i\cdot d+2+k/2,\dots , i\cdot d+k/2+d\mid 1\le i\le k/4\}\).

3. 3.

   \(\{i\cdot d+1+k/2,i\cdot d+2+k/2,\dots , i\cdot d+k/2+d-1, kd/4 + k/2 + d+1\mid 1\le i\le k/4\}\).

4. 4.

   \(\{1,kd/4 + k/2 + d+1\}\).

If the vertex \(kd/4 + k/2 + d+1\) is contracted to 1 then, the new simplicial complex is generated by the union of the sets of maximal simplices given below:

1. 1.

   \(\{1,2,\dots , d,d+i|1\le i\le k/2\}\).

2. 2.

   \(\{i\cdot d+1+k/2,i\cdot d+2+k/2,\dots , i\cdot d+k/2+d\mid 1\le i\le k/4\}\).

3. 3.

   \(\{1, i\cdot d+1+k/2,i\cdot d+2+k/2,\dots , i\cdot d+k/2+d-1\mid 1\le i\le k/4\}\).

The new MxST has at least \(k(d-1)/4\) new nodes (of size \(\log n\)) that need to be added. Thus, we have a lower bound of \({\varOmega }(kd\log n)\) on the operation of edge contraction for MxST.

Reprints and permissions