Removal operations in nD generalized maps for efficient homology computation

Removal Operations in nD Generalized Maps for Efficient Homology Computation Guillaume Damiand1, Rocio Gonzalez-Diaz2, and Samuel Peltier3 1Universit´e de Lyon, CNRS, LIRIS, UMR5205, F-69622, France 2Universidad de Sevilla, Dpto. de Matem´atica Aplicada I, S-41012, Spain 3Universit´e de Poitiers, CNRS, XLIM-SIC, UMR6172, F-86962, France Abstract. In this paper, we present an efficient way for computing homology generators of nD generalized maps. The algorithm proceeds in two steps: (1) cell removals reduces the number of cells while preserving homology; (2) homology generator computation is performed on the reduced object by reducing incidence matrices into their Smith-Agoston normal form. In this paper, we provide a definition of cells that can be removed while preserving homology. Some results on 2D and 3D homology generators computation are presented. Keywords: nD Generalized Maps, Cellular Homology, Homology Generators, Removal Operations. 1 Introduction In this paper, we propose a method for efficiently computing homology generators of subdivided cellular objects. The main idea is to simplify a subdivided object into a smaller one while preserving its homology. This principle is similar to the one used in [10] which is mainly algebraic (i.e. based on reduction of chain complexes), while our approach is mainly combinatorial. In this work, we define a simplification algorithm based on the cell removal operations defined on generalized maps. Its principle is to simplify as much as possible the number of cells while preserving homology. Then we reduce incidence matrices (used for describing boundary operators) into their Smith-Agoston normal form for computing homology generators [3]. Moreover, generators computed in the reduced object can easily be projected into the original one. The paper is structured as follows: in Sect. 2 all the necessary background regarding n-Gmaps is recalled. Section 3 presents the main result of the paper: the definition of the simplification algorithm based on the removal of two types of cells, and the proof of the homology preservation. Finally, some experiments are presented in Sect. 4 in order to illustrate that the simplification step widely reduces the number of cells, and also the homology generator computation. 2 Preliminary Works An n-Gmap is a combinatorial structure devoted to the representation of cellular subdivision of orientable or not orientable nD quasi-manifolds, with or without M. Ferri et al. (Eds.): CTIC 2012, LNCS 7309, pp. 20–29, 2012. c Springer-Verlag Berlin Heidelberg 2012 Removal Operations in n-Gmaps for Efficient Homology Computation 21 boundaries (see [11,12] for more details). Any polytopal complex can be described by an n-Gmap, while the converse is not true (an i-cell can be non homeomorphic to an i-disk). It is possible to associate a semi-simplicial set with any n-Gmap. An n-Gmap is not constructed directly from the cells of the subdivision but from more elementary objects: darts. The set of darts is structured through involutions that describe how they are linked to each other. Definition 1 (n-Gmap). An n-dimensional generalized map,calledn-Gmap, with 0≤n,isa(n+2)-tuple G=(D,α0,...,α n)where: 1. Dis a finite set of darts; 2. ∀i, 0≤i≤n,αiis an involution on D; 3. ∀i:0≤i≤n−2,∀j:i+2≤j≤n,αi◦αjis an involution. The cells of the subdivision are defined implicitly as set of darts thank to the orbit notion (see Def. 2). An orbit in an n-Gmap can be seen as the set of darts that we can reach from a given dart and using as many times as possible the given involutions. Definition 2 (Orbit). Let Φ={π0,··· ,π n}be a set of permutations defined on a set D.Φis the permutation group of Dgenerated by Φ.Theorbit of an element d∈Drelatively to Φ,denotedΦ(d)is the set {φ(d)|φ∈Φ}. As we can see in Def. 3, each i-dimensional cell is an n-Gmap is obtained by an orbit using all the involutions except αi. Definition 3 (i-cell). Let Gbe an n-Gmap, and d∈Dbe a dart. Given i, 0≤i≤n,thei-dimensional cell containing d,calledi-cell and denoted by ci(d), is α0,...,α (i−1),α (i+1),...,α n(d). Due to the definition of cells as sets of darts, the incident and adjacency relations on cells can easily be tested. Two distinct cells c1and c2are incident if c1∩c2=∅, and two i-cells c1and c2are adjacent if there is two darts d1∈c1and d2∈c2 satisfying d1=αi(d2). When a dart dbelongs to an i-dimensional border, we have αi(d)=dand we say that dis i-free. In the example of Fig. 1, face f3is described by α0,α 1(1) = {1,2,3,4,5,6}, edge e1by α0,α 2(13) = {13,14,15,16},andvertexv1by α1,α 2(2) = {2,3,7,14,15,24}.v1and e1are incident since α1,α 2(2) ∩α0,α 2(13) = {14,15} =∅.f1and f3are adjacent since 23 ∈f1,1∈f3,andα2(1) = 23. In this paper, the main operations used to simplify an n-Gmap are the removal operations (see [7,6] for the definitions). Intuitively, removing a removable cell c merges the two (i+ 1)-cells incident to c, without modifying the other cells. Definition 4 (Removable cell). Let Gbe an n-Gmap, cbe an i-cell of G.c is removable if one of the two conditions is satisfied: i=n−1;or0≤i<n−1and ∀d∈c, αi+1 ◦αi+2(d)=αi+2 ◦αi+1(d). The notion of removable cell cis strongly related to the number of its (i+1) incident cells, called the degree of cand denoted degree(c). A direct consequence of Def. 4 is that an i−cell cof degree >2isnotremovable. 22 G. Damiand, R. Gonzalez-Diaz, and S. Peltier f1 f3 e1 2 e f2 v1 v2 (a) 1 65 4 3 2 21 20 19 18 17 22 23 24 16 15 9 10 11 12 13 14 78 (b) Fig. 1. Example of a 2G-map G=(D, α0,α 1,α 2). (a) A 2D cellular complex containing 3 faces; 9 edges and 7 vertices. (b) The 2G-map describing this cellular complex, having 24 darts (represented by numbered black segments). Two darts linked by α0are drawn consecutively and separated by a gray segment (for example α0(19) = 20), two darts linked by α1share a common point (for example α1(20) = 21), and two darts linked by α2are drawn parallel, the gray segment over these two darts (for example α2(13) = 16). In the example of Fig. 1, all the edges are removable (since an (n−1)-cell is always removable in an nG-map), vertex v2is removable while vertex v1not. Removing edge e1merges faces f1and f2in one face having as boundary the boundary of f1plus the boundary of f2minus edge e1. To be able to compute homology of an n-Gmap, we need to have a boundary operator (defined in [5,4]). The boundary operator is defined for n-Gmaps having orientable cells. Note that it is possible to represent a non-orientable object (e.g. a Klein bottle) with a n-Gmaphaving only orientable cells. In the following we detail the notions of orientable cell and signed cell (cf. Defs. 5 and 6). Definition 5 (Orientable i-cell). An i-cell cis orientable if c=e1∪e2such that: ∀d∈c,∀j,0≤j≤n,j=i:dis not j-free ⇒dand αj(d)do not belong to the same set e1or e2.cis non-orientable otherwise. If cis orientable, then it can be partitioned in two sets of darts representing its two orientations and we can associate a value −1or+1toeachofitsdart,called asign. In the following, we only consider n-Gmap having all its cells signed. Definition 6 (Signed i-cell). Let cbe an orientable i-cell. The corresponding signed i-cell is ctogether with a sign for each of its dart d,denotedsgi(d): •sgi(d)=−sgi(αj(d)) ∀j:0≤j<isuch that dis not j-free; •sgi(d)=sgi(αj(d)) ∀j:i<j≤n. For defining a boundary operator on n-Gmaps, we first define the signed incidence number between two cells ciand ci−1which describes the number of times that ci−1appears in the boundary of ci. Definition 7 (Signed incidence number). let {pj}j=1···kbe a set of darts s.t. the orbits {α0,··· ,α (i−2)(pj)}j=1···kmake a partition of α0,...,α (i−1)(d). The signed incidence number between ciand ci−1is defined by (ci:ci−1)=  pj,j=1···k|pj∈ci−1 sgi(pj).sgi−1(pj). Removal Operations in n-Gmaps for Efficient Homology Computation 23 Note that this definition is equivalent to the one given in [5]. Now the boundary operator ∂Gof any i-cell cis defined as ∂G(c)=c(c:c)c,wherec are (i−1)−cells incident to c. The boundary operator ∂Gsatisfies ∂G◦∂G=0 when involutions αiare without fixed points for 0 ≤i≤n−1. Moreover, we have proven in [4] that the homology defined on n-Gmaps by this boundary operator is equivalent to the simplicial homology of the associated quasimanifolds when the homology of the canonical boundary of each i-cell is that of an (i−1)-sphere, and when ∀d∈D,∀i∈{0,...,n},dis i-free or αi(d)∈ α0,...,α i−2,α i+2,...,α n(d). In the following, all the considered n-Gmaps satisfied these conditions. 3 Removal Operations Preserving Homology In this section, we prove that removing a degree two cell or a dangling cell preserves the homology of the n-Gmap. 3.1 Chain Complexes and Chain Contractions Let S={Sq}qbe a graded. A q-chain is a finite formal sum of elements of Sqwith coefficients in Z.LetCq(S) denote the group of q-chains of S.The chain complex (C∗(S),∂) is the chain group C∗(S)={Cq(S)}qtogether with a boundary operator ∂.Givenann-Gmap G,letSGbe the set of all the cells of G.(C∗(SG),∂ G) is the chain complex associated to G. Achain contraction [13] of (C∗(S),∂)to (C∗(S),∂) is a triple (f={fq: Cq(S)→Cq(S)}q,g={gq:Cq(S)→Cq(S)}qand φ={φq:Cq(S)→ Cq+1(S)}q) such that: (i) fand gare chain maps; i.e. fq◦∂q=∂ q◦fqand gq◦∂q= ∂ q◦gqfor all q; (ii) φis a chain homotopy of idC∗(S)={idq:Cq(S)→Cq(S)}q to g◦f={gq◦fq:Cq(S)→Cq(S)}q;i.e.φq−1◦∂q+∂ q+1◦φq=idq−gq◦fqfor all q; (iii) f◦g=idC∗(S). If a chain contraction of (C∗(SG),∂ G)to(C∗(SG),∂ G) exists, then the n-Gmaps Gand Ghave isomorphic homology groups. 3.2 Degree Two Cells Proposition 1. Let cbe an i-cell in an n-Gmap. If cis removable and degree two cell, then there are two (i+1)-cells aand bsatisfying: |(a:c)|=|(b:c)|=1 and for all other (i+1)-cells c,(c:c)=0. Proof. Since cis degree two, there are two (i+ 1)-cells aand bthat are incident to c. For these two cells, we have c∈∂G(a)andc∈∂G(b). So, (a:c)=0and (b:c)=0.If|(a:c)|>1, contradiction with removal property, thus |(a:c)|=1 (and the same for |(b:c)|=1).Forallother(i+ 1)-cells c,cis not incident to cotherwise the degree was greater than two. Thus (c:c)=0.  Proposition 2. Let cbe an i-cell in an n-Gmap. If cis a removable degree two cell, and if each j-cell eincident to c, is after the removal of caj-cell equal to e\c, then homology is preserved after the removal of c. 24 G. Damiand, R. Gonzalez-Diaz, and S. Peltier Note that the removal of a cell may induce removal of other cells (for example, it is possible to build a sphere made of one vertex, one degree two edge and two faces. Removing the edge would supress all the darts and so the vertex and the two faces). The second condition ensures that only one cell is removed Proof. Let (C∗(SG),∂ G) be the chain complex associated to G.Sincecis degree two, there are two (i+ 1)-cells aand bthat are incident to c.ThesetSG of the cells of the n-Gmap Gobtained after removing the cell cconsists in SG\{a, b, c}∪{a}where ais the resulting (i+ 1)-cell from merging the two cells aand b. Since, by Prop. 1, |(a:c)|=|(b:c)|= 1 and for all other (i+1)- cells c,(c:c) = 0, we can construct a chain contraction (f,g,φ)of(C∗(SG),∂ G) to (C∗(SG),∂ G) as follows: f(x)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ c−(b:c)∂G(b),if x=c, a,if x=a, 0,if x=b, x, otherwise; g(x)=a−(a:c)(b:c)b, if x=a, x, otherwise; φ(x)=(b:c)b, if x=c, 0,otherwise. To check that (f,g,φ) is a chain contraction is left to the reader. Moreover, we know that each j-cell incident to cis preserved by the removal operation. Then Gand Ghave isomorphic homology groups.  3.3 Dangling Cells Let (C∗(S),∂) be a chain complex. Let s, t ∈Ssuch that |(s:t)|=1and (s:t) = 0 for any s∈S,s=s.Ifweremovesand tfrom Sto get S,we obtain another chain complex (C∗(S),∂) which is called an elementary collapse of S. A chain contraction of (C∗(S),∂)to(C∗(S),∂)isgivenby f(x)=⎧ ⎨ ⎩ 0,if x=s, t−(s:t)∂(s),if x=t, x, otherwise; g(x)=x;φ(x)=(s:t)t, if x=t, 0,otherwise. Therefore an elementary collapse preserves homology. A subset of Sis collapsible if they can all be removed from Sin a sequence of elementary collapses. Let cbe a k-cell, the closure of c, denoted c,isthesetmadeofcplus all the j-cells, 0 ≤j<kthat are incident to c. The closure of a set Sof cells, denoted S, is the union of the closures of all the cells of S. Definition 8 (Dangling cell). Let cbe an i-cell. We denote Cthe set of (i−1)- cells of ∂G(c),andB={c∈∂G(c)|degree(c)>1}.cis dangling if cis orientable, its degree is 1,{c}∪C\Bis collapsible, and each j-cell e∈¯ B,is after the removal of caj-cell equal to e\c. Proposition 3. Let cbe an i-cell in an n-Gmap. If cis removable and dangling cell, then its removal preserves the homology of the n-Gmap. Proof. Removing cwill remove also all the cells in C\Bbecause these cells are included in c(i.e. their set of darts is included in the set of darts of c). As {c}∪C\Bis collapsible, and as all the other cells are preserved, the homology of the n-Gmap is preserved by the definition and property of collapsible.  Removal Operations in n-Gmaps for Efficient Homology Computation 25 3.4 Simplification Preserving Homology The main principle of the simplification algorithm consists in removing successively all the degree two cells and all the dangling cells for all the dimensions starting from (n−1)-cells to 0-cells. For that, we start to define Algo. 1 which simplifies all the i-cells of a given n-Gmap for a given dimension i. Algorithm 1. Simplification of i-cells. Input:Ann-Gmap G. Output: Simplify all the i-cells of Gwhile preserving the same homology. foreach i-cell cof Gdo if cis removable and the degree of cis 2 then Remove f; else if cis removable and cis a dangling cell then push(P, c); repeat c←pop(P); push in Pall the dangling i-cells adjacent to c; Remove c; until empty(P); In this algorithm, we consider successively each i-cell c, and there are three possible cases. First, if cis not removable, then we are sure that ccannot be removable in a future step of the algorithm. Indeed, we only remove i-cells and this does not modify the (i+ 1)-cells incident to c. Second, if cis removable and itsdegreeistwo,weremovec.Third,ifcis removable and dangling, we also remove c, but now we have to reconsider all the i-cells adjacent to c. Indeed, these cells can possibly become dangling due to the removal of c.Attheendof the loop, we have considered all the i-cells and removed all the degree 2 cells and the dangling cells that were removable. Now the global simplification method consists only in simplifying all the icells of the n-Gmap for all the cells by decreasing dimensions. We have to work in decreasing dimensions because the removal of an i-cell modifies the degree of all the incident (i−1)-cells. At the end of the global simplification algorithm, we have removed all the removable cells of degree 2 or dangling. By using Props. 2 and 3, we know that the final n-Gmap obtained after all the removals has the same homology than the initial n-Gmap. 4 Experiments In order to illustrate the interest of our simplification algorithm, we show results on homology generator computation for the five objects shown in Fig. 2. Objects (a), (b) and (c) are described by 2-Gmaps; objects (d) and (e) are described by 3-Gmaps. 26 G. Damiand, R. Gonzalez-Diaz, and S. Peltier (a) (b) (c) (d) (e) Fig. 2. (a) 2-torus. (b) Klein bottle. (c) pinion. (d) tower. (e) Menger sponge. Table 1. Results of our experiments. We give the number of cells (columns #cells)for initial objects, and after the simplification algorithm. The last column gives the time of the simplification step. The two columns Homology computation give the memory space and the time of the homology generators computation (0s means less than 10−6s). Object Initial Simplified # cells Homology # cells Homology Simplif. Cell dim. 0123computation 0123computation time 2-torus 404 802 396 - 14Mb 5.76s 691- 2.36Kb 0s 0s Klein 900 1800 900 - 74Mb 128.47s 231- 0.41Kb 0s 0s Pinion 470 701 231 - 11Mb 3.56s 231- 0.41Kb 0s 0s Tower 906 1856 952 4 85Mb 140.97s 10 15 4 1 6.53Kb 0s 0s Menger 896 2304 1728 400 159Mb 372.50s 189 365 97 1 2938.00Kb 0.81s 0.03s To compute the homology generators, we iterate through all the cells of the n- Gmap and we compute incidence matrices (which describes the boundary of the cells) using the incidence number definition. Then we reduce incidence matrices into their Smith-Agoston normal form for computing homology generators [3]. Compared to the classical Smith normal form, the specificity of the Agoston reduced normal form is that for a given dimension d, the basis of the boundaries Bpis a subset of the basis of cycles Zp, thus the quotient group Hp=Zp/Bp can directly be obtained by simply removing from Zpthe boundaries of infinite order. Note that several optimizations exists for the reduction of incidence matrices [15,8]. Even if they can be used, we do not use them here as we focus on showing the improvement obtained with the simplification process. The computation of homology generators was implemented in Moka [16], a 3D topological modeler based on 3-Gmap. For this reason, the computation of homology generators is limited to 2D and 3D cases, but all the functions are generic in any dimension. The results are presented in Table 1, where the simplification step widely reduces the number of cells. On the last column one can see that the simplification step is very fast. Memory space is also reduced as the size of incidence matrices are directly linked to the number of cells. Removal Operations in n-Gmaps for Efficient Homology Computation 27 (a) (b) (c) Fig. 3. The generators of H1(in red) computed on simplified objects, and projected on initial objects (drawn in grey). (a) Klein bottle. (b) Tower. (c) Menger sponge. Lastly, we can see in Fig. 3 the different generators of H1obtained for some objects. By using the definition of removal operations, we are able to project the generators of the simplified object on the initial one (by using a similar technique as in [14,9]). We have made a second type of experiments in order to compare our approach with other existing methods. To our knowledge there is no other general method which compute homology generator of cellular objects. Thus we compare our solution with Chomp and RedHom [1,2] which compute homology generators of cubical complexes. We chose these two methods since the two softwares are publicly available. However, it must be noticed that representing a cubical complex by a n-Gmaps is not efficient since a cube is described by 48 darts; the interest of cellular model is precisely to represent non regular subdivisions. In order to test the scale up property of the three methods, we chose three objects (see in Fig. 4(a), (b) and (c)), and multiply the size of each voxel by 4 to 9 for the first two objects, and by 2 to 7 for the last object which contains more voxels. We can see in Fig. 4 the time required to compute homology generators of each object by the three compared methods. These results are really encouraging for our method which obtain the best computation time for the first two objects, with an important gain for the second one. For the third object, Chomp,andMoka performances are very similar (even if Chomp is a little bit quicker), while RedHom is really faster. In this last case, Chomp,andMoka have similar computation time than for the two first objects, while RedHom is extremely fast. We suppose there is an optimization allowing to remove directly some block of voxels. Indeed, the upper part of the last object is composed by a full block of voxels. This kind of improvement can also be made for our method. These experiments show that our method is very competitive since it is not optimized for a specific type of subdivision but it is generic for any cellular complex. Thus its main interest is its genericity and we can conclude from this comparison that this is not to the detriment of the efficiency. Moreover, we can improve our results by adding a thinning pre-processing step that reduces the number of voxels while preserving the homology. 28 G. Damiand, R. Gonzalez-Diaz, and S. Peltier 0 2 4 6 8 10 12 14 0 100000 300000 500000 700000 Number of voxels Chomp RedHom Moka time (in seconds) (a) 50 40 30 20 10 00400000 800000 1200000 Number of voxels time (in seconds) Chomp RedHom Moka (b) 0 2 4 6 8 10 12 14 16 18 400000 0800000 1200000 Number of voxels time (in seconds) Chomp RedHom Moka (c) Fig. 4. Homology computation time comparison for Chomp,RedHom and Moka.Objects are made of voxels filling the bounding box (in wireframe), the filled surfaces being borders of cavities or tunnels. (a) Cub1: 1067 voxels; 1 connected components; 9 tunnels; 5 cavities. (b) Cub2: 1828 voxels; 1 connected components; 7 tunnels; 4 cavities. (c) Cub3: 4003 voxels; 1 connected components; 6 tunnels; 3 cavities. 5Conclusion In this paper, we have presented an algorithm that simplifies an n-Gmap while preserving its homology. For that, it removes degree two cells and dangling cells. Then we can compute homology on the reduced n-Gmap and project the generator on the original object. Some results show the interest of the simplification step, both in memory space and in computation time. Some questions are still open. The first question is about the conditions on removed cells. Is it possible to remove some other type of cells while preserving the homology? The answer is no in 2D and 3D, but still open in higher dimension. This question is related to the definition of the minimal generalized map having the same homology. In 3D, to obtain this minimal map, we need to use another type of operation (fictive edge shifting). Thus we would like to study the extension of this operation in higher dimension to define the minimal n-Gmap. References 1. Chomp, http://chomp.rutgers.edu/ 2. Redhom, http://redhom.ii.uj.edu.pl/ 3. Agoston, M.K.: Algebraic Topology, a first course. In: Dekker, M. (ed.) Pure and Applied Mathematics (1976)