Dominique Attali
email: dominique.attali@gipsa-lab.grenoble-inp.fr

André Lieutier
email: andre.lieutier@3ds.com

David Salinas
email: david.salinas@gipsa-lab.grenoble-inp.fr

Efficient data structure for representing and simplifying simplicial complexes in high dimensions

Keywords: Simplicial complexes, data structure, flag complexes, clique complexes, Vietoris-Rips complexes, shape reconstruction, shape simplification, edge contraction, collapse, homotopy equivalence, high dimensions

We study the simplification of simplicial complexes by repeated edge contractions. First, we extend to arbitrary simplicial complexes the statement that edges satisfying the link condition can be contracted while preserving the homotopy type. Our primary interest is to simplify flag complexes such as Rips complexes for which it was proved recently that they can provide topologically correct reconstructions of shapes. Flag complexes (sometimes called clique complexes) enjoy the nice property of being completely determined by the graph of their edges. But, as we simplify a flag complex by repeated edge contractions, the property that it is a flag complex is likely to be lost. Our second contribution is to propose a new representation for simplicial complexes particularly well adapted for complexes close to flag complexes. The idea is to encode a simplicial complex K by the graph G of its edges together with the inclusion-minimal simplices in the set difference Flag(G) \ K. We call these minimal simplices blockers. We prove that the link condition translates nicely in terms of blockers and give formulae for updating our data structure after an edge contraction. Finally, we observe in some simple cases that few blockers appear during the simplification of Rips complexes, demonstrating the efficiency of our representation in this context.

Introduction

As datasets are growing larger in size and in dimension, simplicial complexes built upon these data become gigantic, challenging our ability to extract useful and concise information. In particular, storing all simplices becomes prohibitive. A way to overcome this difficulty is reducing the size of the simplicial complex prior to analysis. During that process, it is desirable to preserve the homotopy type.

In this work, we focus on the simplification of a particular class of simplicial complexes, likely to be encountered in high dimensional data analysis and manifold learning. Specifically, we are interested in flag complexes also known as clique complexes that have the property of containing simplices wherever the adjacency of vertices permits one. Precisely, the flag complex of a graph G is the largest simplicial complex whose 1-skeleton is G. Obviously, flag complexes are completely determined by their 1-skeletons, which provide a concise form of storage. A standard way of building the 1-skeleton of a flag complex is to consider the proximity graph of a point cloud. The flag complex of such a graph is called a Rips complex. In the light of recent results, [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF][START_REF] Attali | Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] Rips complexes seem to be good candidates for reproducing the homotopy type of the shape sampled by the point cloud. In this context, simplification can be used as a preprocessing phase for reducing, for instance, the cost of computing topological invariants such as Betti numbers. [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF][START_REF] Perry | Plex: Simplicial complexes in MATLAB[END_REF] )

Following what has been done within the computer graphics and visualization communities, one can consider several elementary operations for simplifying a simplicial complex: vertex removal, [START_REF] Schroeder | Decimation of triangle meshes[END_REF] vertex clustering, [START_REF] Rossignac | Multi-resolution 3D approximations for rendering complex scenes[END_REF] triangle contraction. [START_REF] Gieng | Constructing hierarchies for triangle meshes[END_REF] We primarily concentrate here on edge contraction, the operation that consists in merging two vertices. It was used in the pioneering work of Hoppe et al. [START_REF] Hoppe | Progressive meshes[END_REF] for generating progressive meshes and has been intensively studied ever since. Garland and Heckbert [START_REF] Garland | Surface simplification using quadric error metrics[END_REF] proposed an elegant way of prioritizing edge contractions for surface simplification. Dey et al. [START_REF] Dey | Topology preserving edge contraction[END_REF] introduced a local condition called the link condition that characterizes edge contractions that permit a homeomorphic modification of 2-and 3-manifolds.

It would be tempting as we repeatedly apply edge contractions on a flag complex to keep its nature of flag complex, thus preserving its light form of storage along the simplification process. As already observed by Zomorodian in Ref. 22 and confirmed by our first experiments, this seems to be "almost" possible. Indeed, Zomorodian uses a representation by simplicial sets that allows him to collapse any edge while keeping the homotopy type unchanged. He observed that, along the simplification process, most cells remain regular simplices. We suggest here another strategy that preserves the representation by simplicial complexes along the simplification.

Our first contribution is the proof that the link condition introduced in Ref. 7 can also be used to guarantee homotopy-preserving edge contractions in arbitrary simplicial complexes. Our second contribution is a new data structure for encoding arbitrarily simplicial complexes. This data structure is particularly well-adapted for high-dimensional simplicial complexes which are "almost" flag complexes. Besides the 1-skeleton, we encode parsimoniously how the complex differs from the flag complex of its 1-skeleton. Precisely, we represent any simplicial complex K by its 1skeleton G together with the set of inclusion-minimal simplices in the set difference Flag(G) \ K. These minimal simplices are called blockers. The intuition is that simplicial complexes "close" to flag complexes will have a small amount of blockers.

We show that the link condition translates nicely in terms of blockers in our new data structure and give an explicit expression of the blockers created (and destroyed) during an edge contraction. We have implemented the data structure and the edge contraction operation. Our first experiments indicate that the simplification of Rips complexes in some simple cases and using a reasonable strategy for prioritizing edge contractions leads to the apparition of very few blockers. This seems to make the proposed representation efficient in practice.

When drawing simplicial complexes in the figures, we adopt the convention that besides drawing 1-skeletons, either we shade inclusion-maximal simplices or hatch blockers. When no triangles are shaded or hatched, the convention is that the blocker set is empty or equivalently that the simplicial complex is a flag complex.

Basic definitions

In this section, we recall standard definitions and notations that can be found in textbooks. [START_REF] Munkres | Elements of algebraic topology[END_REF] The cardinality of a set X will be denoted ♯X. We will use the notation

A ⊂ B to indicate that A is a subset of B and A B to indicate that A is a proper subset of B.

Abstract simplicial complexes

An abstract simplex is any finite non-empty set. The dimension of a simplex σ is one less than its cardinality, dim σ = ♯σ -1. A k-simplex designates a simplex of dimension k. If τ ⊂ σ is a non-empty subset, we call τ a face of σ and σ a coface of τ . If in addition τ σ, we say that τ is a proper face and σ is a proper coface. An abstract simplicial complex is a collection of simplices, K, that contains, with every simplex, the faces of that simplex. The dimension of K is the largest dimension of one of its simplices. The closure of a set of simplices Σ, denoted Cl(Σ), is the smallest simplicial complex containing Σ. The closure of a simplex σ is Cl(σ) = ∅ =τ ⊂σ {τ }. The vertex set of the abstract simplicial complex K is the union of its elements, Vert(K) = σ∈K σ. A subcomplex of K is a simplicial complex L ⊂ K. A particular subcomplex is the i-skeleton consisting of all simplices of dimension i or less, which we denote by K (i) . The 0-skeleton is the set of inclusion-minimal simplices. Besides classical definitions, the following concept will be useful: Definition 1. Let K be a simplicial complex whose dimension is k. The expansion of K, denoted Expand (K), is the largest simplicial complex having K as a kskeleton. In particular, the expansion of a graph G is the flag complex of G and is denoted Flag(G).

Throughout the paper, we will restrict ourselves to finite simplicial complexes. Note that the expansion of the 0-skeleton K (0) is the power set of the vertex set Vert(K) minus the empty set, Expand K (0) = 2 Vert(K) \ {∅} and consists of all simplices σ ⊂ Vert(K) spanned by vertices in K. In particular, it has a unique inclusion-maximal simplex which is Vert(K). In Section 4, we will be interested by expansions of i-skeletons, Expand K (i) , which form for increasing values of i an inclusion-decreasing sequence of simplicial complexes all containing K; see Figure 3 for a schematic drawing of K and the expansion of its 0-and 1-skeletons.

Intersection and union

Two abstract simplices τ and σ are disjoint if they have no vertices in common or equivalently if τ ∩σ = ∅. It will be convenient to denote the union of two simplices σ and τ simply στ instead of σ ∪ τ . In the same spirit, we shall use indifferently one of the two notations {v 0 , v 1 , . . . , v k } or v 0 v 1 . . . v k to designate the k-simplex spanned by vertices v 0 , v 1 , . . . , v k . In particular, we shall make no distinction between the vertex v of K and the 0-simplex {v} ∈ K. We shall also use the notation ab instead of {a, b} to designate the edge connecting vertex a and vertex b.

Underlying space

Let π : Vert(K) → R n be an injective map that sends the n vertices of K to n affinely independent points of R n , such as for instance the n vectors of the standard basis of R n . The underlying space of K is the point set |K| = σ∈K Hull π(σ) and is defined up to a homeomorphism. We shall say that a transformation f between two simplicial complexes K and K ′ preserves the topological type if the underlying spaces of K and K ′ are homeomorphic, |K| ≈ |K ′ | and we say that f preserves the homotopy type if the underlying spaces are homotopy equivalent, |K| ≃ |K ′ |.

Homotopy-preserving edge contraction

In this section, we give a local condition on the link of an edge ab in a simplicial complex K under which the contraction of the edge ab preserves the homotopy type of K. This condition, called the link condition, was introduced in Ref. 7 to characterize edge contractions that permit a homeomorphic modification when the simplicial complex K is the triangulation of a 2-manifold or a 3-manifold. Unlike previous works, [START_REF] Dey | Topology preserving edge contraction[END_REF][START_REF] Thomas | Link conditions for simplifying meshes with embedded structures[END_REF] we make no assumptions on the simplicial complex K. In particular, we do not require that K triangulates a manifold.

Edge contraction

Recall that Vert(K) designates the set of vertices of K and consider a, b ∈ Vert(K) and c ∈ Vert(K). To describe the edge contraction ab → c, we define a vertex map f that takes vertices a and b to c and takes all other vertices to themselves:

f (v) = c if v ∈ {a, b}, v if v ∈ {a, b}. (1)
We then extend f to all simplices σ = {v 0 , . . . , v k } of K, setting f (σ) = {f (v 0 ), . . . , f (v k )}. The edge contraction ab → c is the operation that changes

K to K ′ = {f (σ) | σ ∈ K}.
By construction f is surjective and K ′ is a simplicial complex. Note that the edge contraction ab → c is well defined even when ab does not belong to K.

Link condition

Let σ be a simplex of the simplicial complex K. The link of σ in K is the simplicial complex

Lk K (σ) = {τ ∈ K | τ ∪ σ ∈ K, τ ∩ σ = ∅}.
When K is clear from the context, we will drop it and denote the link of σ in K simply by Lk(σ). In particular, whenever we contract an edge ab ∈ K to a new vertex c ∈ K ′ , it is unambiguous to write Lk(a), Lk(b), Lk(ab) for the links of a, b and ab in K and Lk(c) for the link of c in K ′ . We are now ready to state our main result (see Figure 1).

Theorem 1 (Link condition theorem). Let K be a simplicial complex. The contraction of the edge ab ∈ K preserves the homotopy type whenever Lk(ab) = Lk(a) ∩ Lk(b).

An example of edge ab satisfying the link condition Lk(ab) = Lk(a) ∩ Lk(b) is given in Figure 1, where simplicial complexes are depicted with the convention adopted at the end of the introduction. Note that the converse of Theorem 1 is in general not true (see Figure 2). The end of the section is devoted to the proof of Theorem 1. First, we review the Nerve Theorem on which rests our proof. We then give the proof before finishing the section with two technical lemmas about links. x y v Fig. 1. Form left to right: link of a, link of b, link of ab and simplicial complex after contraction of the edge ab. One can check that ab satisfies the link condition. Equivalently, no blocker contains ab (see Section 4.3). As a consequence, the contraction of ab preserves the homotopy type. Note that the edge contraction ab → c creates the blocker cxy and α = x and β = y satisfy (i) and (ii) in Lemma 4. The contraction of any of the edges cv, xv and yv removes blocker cxy.

Recall that the nerve of a finite collection of sets, F is the simplicial complex that consists of all non-empty subcollections whose sets have a non-empty common intersection, The Nerve Theorem has several versions, 5 one of the earliest being due to Leray. [START_REF] Leray | Sur la forme des espaces topologiques et sur les points fixes des représentations[END_REF] For the proof of Theorem 1, we shall use the following form:

Nrv F = {G ⊂ F | G = ∅}
Theorem 2 (Nerve Theorem). Consider a triangulable space X which is the union of a finite collection of closed sets F, i.e. X = F. If for every subcollection G ∈ Nrv F, the intersection G is contractible, then the underlying space of Nrv F is homotopy equivalent to X.

Proof of Theorem 1. Suppose ab ∈ K satisfies the link condition Lk(ab) = Lk(a)∩Lk(b) and let K ′ be the complex obtained after the edge contraction ab → c.

The proof considers two coverings, one for |K| and one for |K ′ |, whose nerves N and N ′ are proved to be isomorphic and for which we establish that |K| ≃ |N | and

|N ′ | ≃ |K ′ |.
By abuse of language, we will write |σ| for the underlying space of the closure of σ.

Consider first the collection of sets {|σ ′ |, σ ′ ∈ K ′ } which covers |K ′ | and let N ′ denote its nerve. Clearly, for any non-empty subcollection Σ ′ ⊂ K ′ , the intersection

σ ′ ∈Σ ′ σ ′ is either empty or a simplex of K ′ and therefore the common intersection σ ′ ∈Σ ′ |σ ′ | of sets in the subcollection {|σ ′ |, σ ′ ∈ Σ ′ } is either empty or contractible. The Nerve Theorem then implies that |K ′ | ≃ |N ′ |. Let f : |K| → |K ′ | be the simplicial map induced by the vertex map f : Vert(K) → Vert(K ′ ) defined in Eq. (1). Consider the collection of sets { f -1 [|σ ′ |], σ ′ ∈ K ′ }
obtained by taking the preimages of sets in the first collection. This collection covers |K| and we denote its nerve by N . The two nerves N and N ′ are isomorphic because the surjectivity of f implies that for all Σ ′ ⊂ K ′ , we have the equivalence:

σ ′ ∈Σ ′ f -1 [|σ ′ |] = f -1 σ ′ ∈Σ ′ |σ ′ | = ∅ ⇐⇒ σ ′ ∈Σ ′ |σ ′ | = ∅.
Furthermore, if the intersection on the right-hand side

σ ′ ∈Σ ′ |σ ′ | is non-empty,
then there exists a simplex τ ′ ∈ K ′ such that τ ′ = σ ′ ∈Σ ′ σ ′ and by Lemma 2 which is proved below, the intersection on the left-hand side

σ ′ ∈Σ ′ f -1 [|σ ′ |] = f -1 [|τ ′ |] = |f -1 [Cl(τ ′ )]| is contractible. To summarize, we established that |K| ≃ |N | ≈ |N ′ | ≃ |K ′ |, showing that |K| and |K ′ | have same homotopy type.
The proof of Theorem 1 requires to establish that

|f -1 [Cl(τ )]| is contractible for all simplices τ in K ′ = f (K) under the condition that Lk(ab) = Lk(a) ∩ Lk(b). We will prove a stronger result, namely that |f -1 [Cl(τ )]| is collapsible. Recall that the star of a simplex σ in K, denoted St K (σ)
, is the collection of simplices of K having σ as a face. Provided that there is a unique inclusion-maximal simplex η = σ in the star of σ, it is well-known that |K| deformation retracts to |K \ St K (σ)| and the operation that removes St K (σ) is then called a collapse. [START_REF] Dey | Computational topology[END_REF] A simplicial complex is said to be collapsible if it can be reduced to a single vertex by a finite sequence of collapses. In particular, the underlying space of a collapsible complex is contractible. We start with a technical lemma. Proof. Using f -1 [{cσ}] = {aσ, bσ, abσ} ∩ K and the surjectivity of f , we get that

cσ ∈ K ′ ⇐⇒ f -1 [{cσ}] = ∅ ⇐⇒ {aσ, bσ, abσ} ∩ K = ∅ ⇐⇒ {aσ, bσ} ∩ K = ∅ ⇐⇒ aσ ∈ K or bσ ∈ K.
Lemma 2. Suppose ab ∈ K satisfies Lk(ab) = Lk(a) ∩ Lk(b) and let K ′ be the simplicial complex obtained after the edge contraction ab → c. The preimage f -1 [Cl(σ)] of the closure of any simplex σ ∈ K ′ is non-empty and collapsible.

Proof. For all σ ∈ K ′ , we give an expression of the preimage f -1 [Cl(σ)] which entails its collapsibility. Recalling that the closure of a simplex is Cl(σ) = ∅ =τ ⊂σ {τ } and noting that the preimage of a union is the union of the preimages, we consider three cases:

Case 1: f -1 [Cl(c)] = f -1 [{c}] = {a, b, ab} is collapsible. Case 2: If σ ∩ c = ∅, then for all faces τ of σ, we also have τ ∩ c = ∅ and therefore f -1 [{τ }] = {τ }. It follows that f -1 [Cl(σ)] = ∅ =τ ⊂σ f -1 [{τ }] = ∅ =τ ⊂σ {τ } = Cl(σ).
= τ ⊂ σ f -1 [{cτ }] =        {aτ, bτ, abτ } if τ ∈ Lk(ab), {aτ } if τ ∈ Lk(a) \ Lk(ab), {bτ } if τ ∈ Lk(b) \ Lk(ab). Since Cl(cσ) = {c} ∪ Cl(σ) ∪ ∅ =τ ⊂σ {cτ }, we obtain that f -1 [Cl(cσ)] = {a, b, ab} ∪ Cl(σ) ∪ ∅ =τ ⊂σ f -1 [{cτ }]. Writing Σ • Σ ′ = {σσ ′ | σ ∈ Σ, σ ′ ∈ Σ} and setting L = Cl(σ) ∩ Lk(ab) we get that f -1 [Cl(cσ)] =        Cl(abσ) if σ ∈ Lk(ab), Cl(aσ) ∪ {b, ab} ∪ {b, ab} • L if σ ∈ Lk(a) \ Lk(ab), Cl(bσ) ∪ {a, ab} ∪ {a, ab} • L if σ ∈ Lk(b) \ Lk(ab). Hence, if σ ∈ Lk(ab), the preimage f -1 [Cl(cσ)] is clearly collapsible. If σ ∈ Lk(a) \ Lk(ab)
, we can always find a set of simplices λ 1 , . . . , λ k whose closure is equal to the simplicial complex L = Cl(σ) ∩ Lk(ab) and such that, for all 1 ≤ i, j ≤ k, the simplex λ i is neither a face nor a coface of the simplex λ j . In other words, the set of simplices λ 1 , . . . , λ k are the inclusion-maximal simplices of L. By construction, abλ i is the only proper coface of bλ i in f -1 [Cl(cσ)]. After a sequence of k elementary collapses consisting in removing pairs of simplices (bλ i , abλ i ), we are left with the simplicial complex Cl(aσ) ∪ {b, ab} which is collapsible. The case σ ∈ Lk(b) \ Lk(ab) is done similarly.

Encoding complexes with their skeletons and blocker sets

It is common to represent a simplicial complex K of small dimension by the subset L ⊂ K of simplices that are inclusion-maximal, that is, the set of simplices of K which have no proper cofaces in K (see Figure 4, top left). The simplicial complex K can then be recovered from L by taking the closure, K = Cl(L). In this section, we introduce a new way of representing simplicial complexes (see Figures 4 to 5). Roughly, we store the 1-skeleton G of K together with a minimal set of simplices called blockers that indicates how much K differs from the flag complex of G. First, we describe our data structure for encoding simplicial complexes. Then, we explain how to check the link condition and how to maintain the data structure as we contract edges. Pseudo-codes and time complexities are given in Appendix A.

Data structure

Definition 2. Let i ≥ 0. We say that a simplex σ ⊂ Vert(K) is an order-i blocker of K if it satisfies the following three conditions (1) dim σ > i;

(2) σ does not belong to K;

(3) all proper faces of σ belong to K. The set of order-i blockers of K is denoted Blockers i (K).

Equivalently, the order-i blockers of K are the inclusion-minimal simplices of Expand K (i) \ K for all i ≥ 0; see Figures 3 and4. A key consequence is that the pair (K (i) , Blockers i (K)) encodes entirely the simplicial complex K. Indeed, the simplicial complex whose i-skeleton is S and whose order-i blocker set is B can be retrieved from the pair (S, B) using the formula

K = {σ ∈ Expand (S) | σ has no face in B}. (2)
∅ Vert(K)

K (0) K (1) \ K (0) K Expand K (1)
Expand K (0) order 1 blocker order 0 blocker In this paper, we are primarily interested in simplicial complexes K "close" to flag complexes with a "small" 1-skeleton and therefore choose to represent them by the pair (K [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] , Blockers 1 (K)). Indeed, if K = Flag(G) is a flag complex, then its blocker set is empty and K can be represented by the pair (G, ∅). As we simplify the simplicial complex by edge contractions, we hope that the blocker set will remain small. This intuition is sustained by experiments we make in Section 5 in which K is the Rips complex of a point set that samples a shape. Hereafter, blockers will always refer to order-1 blockers.

Let N (v) = N K (v) be the set of vertices w = v such that vw ∈ K and write B(v) = B K (v) for the set of blockers that contain v. Clearly, encoding the pair (K [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] , Blockers 1 (K)) boils down to encoding for each vertex v of K the pair (N (v), B(v)). Precisely, our data structure consists of a linear array V for the vertices and records for each vertex v the set of neighbors N (v) and a set of pointers to blockers in B(v) as illustrated in Figure 5. It follows that the size of our data structure is a constant times v∈Vert(K) (1 + ♯N (v) + 2♯B(v)). To see this, charge each vertex in a blocker to its corresponding vertex in V . During the operation, each vertex in V is charged at most ♯B(v) times.

To conclude this section, we give a crude upper bound on the dimension and number of blockers in a simplicial complex with n vertices. Consider a blocker σ passing through a vertex v. Since σ ⊂ {v} ∪ N (v), we get ♯σ ≤ 1 + ♯N (v) and therefore dim σ ≤ max v∈σ ♯N (v). It follows that N max = max v∈Vert(K) ♯N (v) is an upper bound on the dimension of the blockers and O(2 Nmax ) is an upper bound on the number of blockers through v. The total number of blockers in our data structure is O(n2 Nmax ).

4.2.

Testing whether a simplex belongs to the complex Recall that a simplex σ belongs to K if and only if σ belongs to Expand K (i) and σ has no face in Blockers i (K) (see Eq. ( 2)). It will be convenient to use this equivalence with i = 0 for the proofs and i = 1 for computations. Precisely, in the proofs, we will use that for all σ ⊂ Vert(K), we have the equivalence: σ ∈ K ⇐⇒ σ has no face in Blockers 0 (K). For the computations, we will set i = 1 and test whether σ ⊂ Vert(K) belongs to K by checking whether its edges belong to the 1-skeleton and σ contains no order-1 blocker; see Algorithm 4 in Appendix A for the details.

Checking the Link Condition

The next lemma formulates the link condition in terms of blockers. In other words, τ min is an order-0 blocker. Since τ min ⊂ abσ, τ min / ∈ K, aσ ∈ K and bσ ∈ K, we must have ab ⊂ τ min which contradicts the assumption that no (order-1) blocker of K contains ab.

Testing whether an edge ab ∈ K satisfies the link condition can be done by traversing the blockers through a and testing for each blocker whether it contains b. See Algorithm 1 in Appendix A for the pseudo-code and a discussion of its time complexity.

Updating the data structure after an edge contraction

In this section, we describe how to update the data structure after an edge contraction. More precisely, we consider a simplicial complex K and let K ′ be the simplicial complex obtained after the edge contraction ab → c. Our goal is to compute the pair Proof. First, note that the proper faces of cσ belong to K ′ if and only if (i) is satisfied. Indeed, using Lemma 1, (i) is equivalent to σ ∈ K ′ and cτ ∈ K ′ for all proper faces τ σ. Hence, cσ ∈ Blockers 1 (K ′ ) =⇒ (i). Let us prove that cσ ∈ Blockers 1 (K ′ ) =⇒ (ii). Since cσ ∈ K ′ , neither aσ nor bσ belongs to K. It follows that aσ has a face in Blockers 0 (K) and since σ ∈ K, this face must contain a. Let us denote this face aβ with β ⊂ σ. Similarly, since bσ ∈ K, there exists a face α ⊂ σ such that bα ∈ Blockers 0 (K). Let us prove that αβ = σ. Suppose for a contradiction that αβ is a proper face of σ. (i) implies that αβ ∈ Lk(a) ∪ Lk(b). If αβ belongs to Lk(a), then β being a face of αβ must also belong to Lk(a) which contradicts aβ ∈ Blockers 0 (K). Similarly, if αβ belongs to Lk(b), we also get a contradiction.

(N K ′ (c), B K ′ (c)). Clearly, N K ′ (c) = (N (a) \ {b}) ∪ (N (b) \ {a}).
Conversely, let us prove that (i) and (ii) =⇒ cσ ∈ Blockers (K ′ ). We have seen that (i) implies that all proper faces of cσ belong to K ′ . To prove that cσ ∈ K ′ , we note that neither aσ nor bσ belongs to K. Indeed, aσ = aαβ ∈ K since its face aβ ∈ Blockers 0 (K) and bσ = bαβ ∈ K since its face bα ∈ Blockers 0 (K). A few remarks. Suppose σ = αβ with dim σ ≥ 1 and ab ∩ σ = ∅ satisfies (i) and (ii) in Lemma 4. Because order-0 blockers have dimension 1 or more, the two sets α and β are non-empty. Writing d i (v) for the largest dimension of order-i blockers through v, it follows directly from the lemma that the largest dimension of order-1 blockers through c satisfies d 1 (c) ≤ d 0 (a) + d 0 (b) (see Figure 6 for an example in which equality is attained). Finally, we show that if α is a vertex, then α ∈ N (a). Suppose α is a vertex. Because dim σ ≥ 1, α is a proper face of σ. Thus, (i) implies α ∈ Lk(a) ∪ Lk(b) and (ii) implies α ∈ Lk(b), yielding α ∈ Lk(a).

We are now ready to derive an expression for the set of blockers through c. First, note that

Blockers 0 (K) = Blockers 1 (K) ∪ {xy | x ∈ K (0) , y ∈ K (0) , xy ∈ K (1) }.
Hence, bα ∈ Blockers 0 (K) if and only if bα ∈ Blockers 1 (K) or α ∈ K (0) \ N (b). Thus, to exhaust simplices σ = αβ with dim σ ≥ 1, ab ∩ σ = ∅ that satisfy (i) and (ii), it suffices to take α in the set of simplices

Z a (b) = {α | bα ∈ B(b), ab ∩ α = ∅} ∪ (N (a) \ (N (b) ∪ {b})) .
Switching a and b, we define Z b (a) similarly and obtain

B K ′ (c) = { cαβ | α ∈ Z a (b), β ∈ Z b (a), αβ ∈ K, ∀τ αβ, τ ∈ Lk(a) ∪ Lk(b) }.
From this formula, we derive immediately an algorithm for computing B K ′ (c) whose pseudo-code is given in Algorithm 5 of Appendix A. The only piece that we still need to explain is how to compute the link of a vertex. This is done in the next section, where more generally we compute the link of a simplex.

Let N σ = max v∈σ ♯N (v). Overall, updating the data structure after the edge contraction ab → c has a cost which increases with the number and dimension of blockers in a neighborhood of a and b and can be done efficiently in O( N a N b log N N (a) ) assuming there are no blockers in a neighborhood of a and b (see Appendix A for the details).

Computing the link of a simplex

Since the link of a simplex α ∈ K is a simplicial complex, we can also represent it by a pair consisting of its 1-skeleton and its order-1 blocker set. We give below formulas expressing each element in the pair. Let N (α) = u∈α N (u). Lemma 5. For every simplex α in the simplicial complex K, we have:

Lk(α) (1) = {σ ⊂ N (α) | dim σ ≤ 1, ασ ∈ K}, Blockers 1 (Lk(α)) = {σ ⊂ N (α) | dim σ ≥ 2, ασ ∈ K, ∀σ ′ σ, ασ ′ ∈ K}.
Proof. By definition, σ is a vertex or an edge of the link of α if and only if dim σ ≤ 1, α ∩ σ = ∅ and ασ ∈ K, yielding the first formula.

By definition, σ is a blocker of the link of α if and only if dim σ ≥ 2, σ ∈ Lk(α) and for all proper faces ∅ = σ ′ σ, we have that σ ′ ∈ Lk(α), yielding the second formula.

Below, we give a characterization of the blockers in the link of a simplex from which we derive an algorithm for computing the link; See Algorithm 3 in Appendix A for the pseudo-code and a discussion of its time complexity. Lemma 6. Let α ∈ K. The simplex σ is a blocker of the link of α if and only if σ ⊂ Vert(Lk(α)), dim σ ≥ 2, there exists β ∈ Blockers 1 (K) such that σ = β \ α and there exists no blocker of K of the form α ′ σ ′ with ∅ = α ′ ⊂ α and σ ′ σ.

Proof. Suppose σ is a blocker in the link of α. By Lemma 5, we have that dim σ ≥ 2, σ ⊂ N (α), ασ ∈ K and ∀σ ′ σ, ασ ′ ∈ K. In particular, it is easy to check that all vertices and all edges of σ belong to K and α ∩ σ = ∅. Therefore, the condition ασ ∈ K implies that there exists a blocker β of K such that β ⊂ ασ. The condition ∀σ ′ σ, ασ ′ ∈ K implies that the blocker β contains σ and therefore σ = β \ α. Furthermore, no blocker of K has the form α ′ σ ′ with α ′ ⊂ α and σ ′ σ.

Conversely, consider σ = β \ α ⊂ Vert(Lk(α)) such that dim σ ≥ 2, β is a blocker of K and there exists no blocker α ′ σ ′ of K with ∅ = α ′ ⊂ α and σ ′ σ. Since β ⊂ ασ, this means that ασ is a coface of the blocker β and therefore does not belong to K. On the other hand, for all ∅ = σ ′ σ, the simplex σ ′ is a proper face of the blocker β and therefore belongs to K. One can check that for all σ ′ σ, the simplex ασ ′ belongs to K since all its edges belong to K and none of its faces are blockers of K. By Lemma 5, σ ∈ Blockers 1 (Lk(α)).

As an immediate corollary, we get that if K is a flag complex, so is the link of any of its vertices. Furthermore, for every vertex x ∈ Lk(v), we have ♯N Lk(v) (x) ≤ ♯N K (x) and ♯B Lk(v) (x) ≤ ♯B K (x). The pseudo-code for computing the link is given in Algorithm 3 of Appendix A.

Poppable blockers

The smaller the number of blockers the more efficient our data structure will be. Given a simplicial complex K represented by the pair (S, B), we are interested in the operation that removes a blocker σ from the blocker set B, while leaving intact the 1-skeleton S. The result is a complex K ′ represented by the pair (S, B \ {σ}). By definition of a blocker, all faces of σ but σ itself belong to K. Thus, removing σ from the blocker set of K has the effect of adding it to the complex, possibly with some cofaces. We get back K from K ′ by removing precisely the star of σ in K ′ , that is K = K ′ \ St K ′ (σ). As we have seen earlier, if there is a unique inclusion-maximal simplex η = σ in the star of σ, then |K ′ | deformation retracts to |K| and the operation that removes σ from the blocker set of K is then called an anti-collapse. More generally, it has been established in Ref. 4 that if Lk K ′ (σ) is a cone, then we can go from K ′ to K by a sequence of collapses. We recall that a simplicial complex L is said to be a cone if it contains a vertex o such that the following implication holds: σ ∈ L =⇒ σ ∪ {o} ∈ L. The vertex o is called the apex of the cone. We will see shortly that checking whether a simplicial complex is a cone is not too complicated. This motivates the following definition: Definition 3. Let K be a simplicial complex. The blocker σ of K is poppable if the link of σ in the simplicial complex K ′ encoded by the pair (K [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] , Blockers 1 (K)\{σ}) is a cone. The operation that goes from K to K ′ is called an extended anti-collapse.

Removing poppable blockers from the data structure does not change the homotopy type. Checking whether a blocker σ is poppable can be done efficiently by first computing the link L of σ in the complex (K [START_REF] Attali | Reconstructing shapes with guarantees by unions of convex sets[END_REF] , Blockers 1 (K) \ {σ}) as explained in the previous section and then checking whether L is a cone. The following lemma leads to a simple algorithm for testing whether L is a cone; see Algorithm 2 in Appendix A for the pseudo-code.

Lemma 7. A simplicial complex L is a cone with apex o if and only if N L (o) = Vert(L) \ {o} and B L (o) = ∅.
Proof. Suppose L is a cone with apex o. Clearly, every vertex v = o of L is connected to o by an edge or equivalently N L (o) = Vert(L) \ {o}. Suppose for a contradiction that oτ is a blocker of L for some simplex τ such that o ∩ τ = ∅. By definition of a blocker, oτ ∈ L and all proper faces of oτ belong to L. In particular τ ∈ L and by definition of a cone oτ ∈ L, yielding a contradiction. Conversely, suppose B L (o) = ∅ and N L (o) = Vert(L) \ {o}. Let τ ∈ L. It is easy to see that oτ ∈ L since all edges of oτ belong to L and oτ contains no blocker.

Experiments

In this section we apply our representation to the simplification of a subfamily of flag complexes, namely Rips complexes and present the results of various computational experiments we performed.

Rips complexes

Given as input a point cloud P in a metric space and a real number r ≥ 0, the proximity graph G r (P ) is the graph whose vertices are the points P and whose edges connect all pairs of points within distance 2r. By definition, the Rips complex is the flag complex of the proximity graph, R(P, r) = Flag(G r (P )). In our experiments, we consider finite point sets P that sample various d-dimensional manifolds X embedded in the D-dimensional Euclidean space. Typically, d ∈ {1, 2, 3}. In our experiments, D ∈ {3, 4, 9, 128 2 }. Rips complexes are built using the extrinsic distance of the embedding space. In the remainder of this section, we establish an upper bound on the initial size of our data structure and compare it with a bruteforce approach that stores all simplices in the Rips complex. For this, we suppose the sampling is neither too sparse nor too dense. Precisely, we suppose that every ball centered at X with radius ε contains at least one point of P and at most κ points of P for some positive number ε ≤ r and some constant κ > 0. In particular, d H (P, X) ≤ ε. We express our upper and lower bounds using respectively covering and packing numbers whose definitions can be found in Ref. 6 and are recalled below.

Write B(x, r) for the closed ball with center x and radius r and let U ⊂ R D . An εcover of U is a set Y ⊂ U with the property that the union of balls centered at Y with radius ε contains U . An ε-packing of U is a set Y ⊂ U with the property that the balls centered at Y with radius ε are pairwise disjoint. The covering number C(x, r, ε) is the size of the smallest ε-cover of X ∩ B(x, r) and the packing number P(x, r, ε) is the size of the largest ε-packing of X ∩ B(x, r). We let C(r, ε) = max x∈X C(x, r, ε) and P(r, ε) = min x∈X P(x, r, ε). If X is a d-dimensional manifold with a positive reach ρ > 0 then the covering number and the packing number are both Θ(r d /ε d ) as ε → 0 and r < ρ. The constant hidden in Θ depends only upon the intrinsic dimension d and does not depend upon the ambient dimension D.

Let us bound the size of our data structure. The number of neighbors of v is upper bounded by

N max = max v∈Vert(R(P,r))
♯N (v).

Since the Rips complex contains no blocker, the size of our data structure initially is a constant times v∈Vert(R(P,r)) (1+♯N (v)) ≤ n(1+N max ). Note that the neighbors of a vertex v in the Rips complex R(P, r) are the points of P \{v} in the ball B(v, 2r). This ball can be covered with C(v, 2r, ε) balls of radius ε centered at X ∩ B(v, 2r), each of them containing at most κ points of P . It follows that ♯N (v) ≤ κC(v, 2r, ε) and N max ≤ κC(2r, ε). Hence, the size of our data structure is bounded by n times a quantity that depends only upon the ratio r/ε, the constant κ and the intrinsic dimension d and not upon the ambient dimension D.

Let us now compare our representation with the one that consists in storing all simplices. We first give an upper and lower bound on the number of k-simplices. Consider a k-simplex σ which has v as a vertex. If σ ∈ R(P, r) then its vertex set is contained in B(v, 2r). On the other hand, if the vertex set of σ is contained in B(v, r) then σ ∈ R(P, r). Put another way, the set of k-simplices of R(P, r) with v as a vertex is a subset of the set of k-simplices obtained by picking v and k distinct neighbors of v in R(P, r). On the other hand, we get a k-simplex of R(P, r) by choosing v and k distinct neighbors of v in R(P, r/2). Let

N ′ min = min v∈Vert(R(P,r/2)) ♯N (v).
We deduce the following upper and lower bounds on the number of k-simplices:

n k + 1 N ′ min k ≤ ♯{σ ∈ R(P, r) | dim σ = k} ≤ n k + 1 N max k .
Summing over all dimensions, we get that n N ′ min +1 2 N ′ min ≤ ♯R(P, r) ≤ n2 Nmax . We saw above that N max ≤ κC(2r, ε). Let us give a lower bound on N ′ min . Recall that the neighbors of a vertex v in the Rips complex R(P, r/2) are the points of P \ {v} in the ball B(v, r). This ball can be packed with P(v, rε, ε) pairwise disjoint balls of radius ε centered at X ∩ B(v, rε), each of them containing at least one point of P . It follows that N ′ min ≥ P(rε, ε) -1. To conclude, if N represents the typical number of neighbors in the proximity graph, a brute-force approach would have to enumerate something in the order of magnitude n N +1 2 N , which is prohibitive for realistic Rips complexes. This should be compared to the size of our data structure which initially is roughly equal to O(nN ). In Figure 7, we plotted the number of k-simplices in the Rips complex of a point set P that samples the boundary of a surface in R 3 . Already in this small example, the number of simplices is gigantic and so is the size of a brute-force representation. . This should be compared with our data structure which has only to store 2646 vertices and 80304 edges to represent the same complex.

Datasets

Let us introduce the datasets we use to present our experiment findings. Each dataset is a set of points P that samples a d-dimensional manifold X embedded in R D . For each dataset, we try to find a scale parameter r, so that |R(P, r)| ≃ X. In this we are helped by Ref. 3 which describes conditions guaranteeing that the Rips complex R(P, r) recovers the homotopy type of X. Table 1 gives for each point set P , its size, the dimension d of the sampled manifold, the ambient dimension D, the smallest degree N min in R(P, r), and the largest degree N max in R(P, r). The first group in the table contains synthetic datasets and the second group contains real datasets.

Synthetic data

We consider three scenarios for generating P . First, we sample the boundary of a (d + 1)-dimensional cube, C d = ∂[-1, 1] d+1 embedded in R d+1 . Specifically, we sample each of the 2d + 2 facets of C d using a regular grid of k d points. Applying this sampling method for k = 21 and d = 2, we get a first point set C 2 whose size is

= {x ∈ R d+1 | x = 1}.
Finally, we sample the special orthogonal group SO 3 using the method described in Ref. 21 and get a point set SO 3 ⊂ R 9 whose size is 50000. We recall that the special orthogonal group SO 3 is diffeomorphic to the real projective space RP 3 and can be embedded in R 9 by representing each rotation in 3D by a 3 × 3 matrix.

Real data

Finally, we consider two real datasets. The first one, referred to as Ramses, is a 3D scan data consisting of points measured on the surface of a statue representing Ramses II. The surface of the statue is homeomorphic to S 2 and its scan is available in the Aim@Shape repository. The second dataset, referred to as Lucky_cat, is a collection of 72 images of a toy cat placed on a turntable and observed by a fixed camera. [START_REF] Nene | Columbia Object Image Library (COIL-100[END_REF] Images of the toy are taken at pose interval of 5 degrees. Each image has size 128 2 = 16384. Since the degree of freedom of the acquisition system is 1, the collection of images can be interpreted as a point cloud that samples a curve in R 16384 . Some of the images in the dataset Lucky_cat are shown in Figure 8. The Rips complex of Lucky_cat we use in our experiments is presented in Figure 9.

Simplification

Once the Rips complex of P is built, we simplify it by iteratively contracting edges.

After each edge contraction, we delete poppable blockers. Initially, all edges are stored in a priority queue Q. We use the length of the edges to prioritize them, so that the shortest edge has highest priority. We then remove the edge ab with highest priority from the priority queue. If ab satisfies the link condition, we contract ab to a new vertex c = a+b 2 and update the data structure, which includes the removal of edges from Q and the insertion of new edges into Q. We also remove poppable blockers during that step. We let the process continue until no edges remain in Q. Each edge contraction decreases the number of vertices by one. We call K i the simplicial complex obtained after i edge contractions and set n i = ♯ Vert(K i ) = ♯ Vert(K 0 )i.

Results and discussion

For each point set P ∈ {C 2 , S 2 , C 3 , S 3 , SO 3 , Ramses}, we plot with respect to the number i of edge contractions the number of blockers, the cumulated number of poppable blockers that have been removed at step i and the average number of neighbors per vertex; see Figure 10. For Lucky_cat, the simplicial complex obtained after simplification is drawn in Figure 9. In our experiments, we observe that the total amount of blockers present in the data structure remains notably small at all times. For Lucky_cat, none other than the penultimate edge contraction produces a blocker. For C 2 and S 2 , all blockers produced before the third from the last step are poppable. It follows that for Lucky_cat, C 2 , and S 2 , the data structure contains no blockers almost until the end of the simplification. This should be compared with results in Ref. 2 in which we were not removing poppable blockers. This slight modification in the simplification process dramatically decreases the number of blockers in the data structure and also accelerates computations since the cost of an edge contraction increases with the number and dimension of blockers around that edge.

Except for SO 3 , the complex remaining at the end of the simplification process possesses a unique blocker whose boundary is precisely the simplified complex. The dimension of this unique remaining blocker is d+1, one more than the dimension d of the sampled surface. Results are thus consistent with the topology of the sampled shape which is a topological d-sphere for all our datasets but SO 3 . The complex we obtain after simplifying the Rips complex of SO 3 possesses 12 vertices and has dimension 4. We computed its homology groups and checked that they coincide with the homology groups of RP 3 . Interestingly, this complex is close to the smallest triangulation of SO 3 which contains 11 vertices. [START_REF] Walkup | The lower bound conjecture for 3-and 4-manifolds[END_REF] We also observe that, in all our experiments, the size of our data structure decreases during the simplification. This can be explained by the fact that every edge contraction decreases the number of vertices and edges and that the additional cost of storing blockers remains negligible compared to the cost of storing the 1skeleton of the complex.

These very first illustrations of our data structure and simplification procedure are quite promising. Indeed, in these preliminary experiments we have only tested one of the simplest criteria for ordering edge contractions, namely the edge length, and restricted ourselves to a strict application of edge contractions. In fact, we believe that together with Ref. 3 this theoretical work lays theoretical foundations and opens a new field of design and experimentation of simplification strategies or computation of topological invariants in our representation. In future work, we plan to revisit in this context usual simplification operations including, beyond edge contraction, point cloud filtering, simplex collapse and anti-collapse. Fig. 10. We plotted as functions of i the number of blockers in the simplicial complex K i on the left, the cumulated number of poppable blockers removed from the data structure up to step i in the middle and the average number of neighbors per vertex on the right. From top to bottom: the initial Rips complex has vertex set C2, S2, C3, S3, SO3, and Ramses.

Fig. 2 .

 2 Fig. 2. Left and middle: two 2-dimensional simplicial complexes with a blocker through ab. Right: The edge contraction ab → c may (top) or may not (bottom) preserves the homotopy type.

Lemma 1 .

 1 Let σ ⊂ Vert(K) \ {a, b} be a simplex spanned by vertices of K disjoint from a and b. The simplex cσ belongs to K ′ if and only if either aσ or bσ belongs to K. Equivalently, σ ∈ Lk(c) if and only if σ ∈ Lk(a) ∪ Lk(b).

Case 3 :

 3 If σ belongs to the link of c in K ′ , then σ ∈ Lk(a) ∪ Lk(b) by Lemma 1. If in addition ab satisfies the link condition Lk(ab) = Lk(a) ∩ Lk(b), this implies that σ belongs either to Lk(ab) or to Lk(a) \ Lk(ab) or to Lk(b) \ Lk(ab). Observing that the same is true for all faces τ of σ, we deduce immediately that for all ∅

Fig. 3 .Fig. 4 .

 34 Fig. 3. Hasse diagram of K.

Fig. 5 .

 5 Fig. 5. Data structure representing the simplicial complex in Figure 4.

Lemma 3 .

 3 Let K be a simplicial complex. The edge ab ∈ K satisfies the link condition Lk(ab) = Lk(a) ∩ Lk(b) if and only if no blocker of K contains ab.Proof. It is not difficult to see that for all simplicial complexes K and for all edges ab ∈ K, we have the inclusion Lk(ab) ⊂ Lk(a) ∩ Lk(b). Let us prove that Lk(ab) = Lk(a) ∩ Lk(b) implies that no blocker of K contains ab. Suppose for a contradiction that the simplex abτ is a blocker of K for some simplex τ such that ab ∩ τ = ∅. By definition of a blocker, all proper faces of abτ belong to K and in particular aτ ∈ K and bτ ∈ K. On the other hand, abτ does not belong to K. It follows that τ ∈ Lk(a), τ ∈ Lk(b) and τ ∈ Lk(ab), implying that Lk(ab) = Lk(a) ∩ Lk(b). Conversely, suppose no blocker of K contains ab and let us prove that Lk(a) ∩ Lk(b) ⊂ Lk(ab). Consider a simplex σ ∈ Lk(a) ∩ Lk(b). By definition, aσ ∈ K, bσ ∈ K and ab ∩ σ = ∅. We claim that abσ belongs to K and therefore σ ∈ Lk(ab). Let us prove the claim by contradiction. Suppose some of the faces of abσ do not belong to K and let τ min be an inclusion-minimal face among them.

  The next lemma prepares the computation of B K ′ (c) by characterizing blockers through c.

Lemma 4 .

 4 Let K ′ be the simplicial complex obtained after the edge contraction ab → c. Suppose σ ⊂ Vert(K) \ {a, b} is a simplex with dim σ ≥ 1. The simplex cσ belongs to Blockers 1 (K ′ ) if and only if the following two conditions are fulfilled:(i) σ ∈ K;every proper face of σ belongs to Lk(a) ∪ Lk(b); (ii) σ = αβ with aβ ∈ Blockers 0 (K) and bα ∈ Blockers 0 (K).

Fig. 6 .

 6 Fig. 6. Triangle ayz is a 2-blocker. We have that Lk(a) = {x, y, z, xy, xz, b, by, bz}, Lk(b) = {y, z, yz, a, ay, az}, Lk(ab) = {y, z}. Note that σ = αβ with α = x and β = yz fulfills (i) and (ii) in Lemma 4. Therefore, the edge contraction ab → c leads to the creation of the 3-blocker cxyz and the destruction of the 2-blocker ayz.

Fig. 7 .

 7 Fig.7. Number of k-simplices in R(P, r) as a function of k for a point set P that samples C 2 . We used a logarithmic scale for the y-axis. Experimentally, we observe that the number of k-simplices is above but close to n k+1

Fig. 8 .

 8 Fig. 8. Twelve of the 72 points in the dataset Lucky_cat. Each point represents a 128 pixel by 128 pixel image of a toy cat taken during its rotation around a fixed axis.

  Left: Rips complex of the point set Lucky_cat. Right: After simplification, we obtain a simplicial complex which consists of three vertices, three edges and has a unique blocker.

Table 1 .

 1 The seven point sets considered in our experiments. × 21 2 = 2646. Applying again this method for k = 18 and d = 3, we get a second point set C 3 whose size is 8 × 18 3 = 46656. For d ∈ {2, 3}, we then normalize C d and get a point set S d which samples the d-sphere S d

	Dataset	♯points d	D	N min	Nmax
	C2	2646	2	3	50	74
	S2	2646	2	3	64	151
	C3	46656	3	4	91	153
	S3	46656	3	4	38	333
	SO3	50000	3	9	33	55
	Ramses	193252	2	3	6	38
	Lucky_cat	72	1	128 2	7	44
	6

Acknowledgements

Authors have been supported in part by ANR Project GIGA ANR-09-BLAN-0331-01.

Appendix A. Pseudo-codes and running times

We provide pseudo-codes for testing the link condition, computing the link of a simplex α, testing whether a vertex belongs to a complex, testing whether a complex is a cone and computing the blockers passing through c after the edge contraction ab → c. To express time complexities, let N σ = max v∈σ ♯N (v), B σ = max v∈σ ♯B(v) and Q σ = max v∈σ max β∈B(v) ♯β. Moreover, let A σ be the number of blockers contained in σ ∪ N (σ). We also suppose that we are able to answer whether v ∈ σ in O(log ♯σ) time and whether τ ⊂ σ in O(♯σ log ♯σ) time. Furthermore, we suppose that removing a vertex from σ takes O(log ♯σ) time.

Summing up these three costs and using V ⊆ N (α) and ♯N (α) ≤ N α , we get that the time complexity for Algorithm 3 is O(l(α)) with:

For L = K, the time complexity of Algorithm 4 is O(g(♯σ, σ)) where g(x, y) = x 2 (log N y + B y log x). If L is the link of a vertex v ∈ K, the time complexity Algorithm 3 Compute the 1-skeleton (V, E) and the blockers B in the link of a simplex α.

V

Recall that d i (v) designates the largest dimension of order-i blockers through v and let d =

We conclude the appendix by computing the complexities when there are no blockers through the vertices impacted by a local operation. The time complexity corresponding to Algorithm 1, answering if an edge ab in K meets the link condition is O(1). The time complexity corresponding to Algorithm 3 which builds a representation of the link of a simplex α, is O( N 2 α log N N (α) ). For Algorithm 4 which tests whether a simplex σ belongs to a subcomplex of K, we get O( (♯σ) 2 log N σ ) and updating the set of blockers takes O( N a N b log N N (a) ) (or O( N a N b log N N (b) )). These complexities give a good picture of the practical behavior of the simplification process when the number of blockers remains sufficiently small.