Removal operations in nD generalized maps for efficient homology computation

Remo al Ope a ions in nD Gene alized Maps o Efficien Homology Compu a ion Guillaume Damiand1, Rocio Gonzalez-Diaz2, and Samuel Pel ie 3 1Uni e si ´e de Lyon, CNRS, LIRIS, UMR5205, F-69622, F ance 2Uni e sidad de Se illa, Dp o. de Ma em´a ica Aplicada I, S-41012, Spain 3Uni e si ´e de Poi ie s, CNRS, XLIM-SIC, UMR6172, F-86962, F ance Abs ac . In his pape , we p esen an efficien way o compu ing ho- mology gene a o s o nD gene alized maps. The algo i hm p oceeds in wo s eps: (1) cell emo als educes he numbe o cells while p ese - ing homology; (2) homology gene a o compu a ion is pe o med on he educed objec by educing incidence ma ices in o hei Smi h-Agos on no mal o m. In his pape , we p o ide a defini ion o cells ha can be e- mo ed while p ese ing homology. Some esul s on 2D and 3D homology gene a o s compu a ion a e p esen ed. Keywo ds: nD Gene alized Maps, Cellula Homology, Homology Gene a o s, Remo al Ope a ions. 1 In oduc ion In his pape , we p opose a me hod o efficien ly compu ing homology gene - a o s o subdi ided cellula objec s. The main idea is o simpli y a subdi ided objec in o a smalle one while p ese ing i s homology. This p inciple is simila o he one used in [10] which is mainly algeb aic (i.e. based on educ ion o chain complexes), while ou app oach is mainly combina o ial. In his wo k, we define a simplifica ion algo i hm based on he cell emo al ope a ions defined on gene alized maps. I s p inciple is o simpli y as much as possible he numbe o cells while p ese ing homology. Then we educe incidence ma ices (used o desc ibing bounda y ope a o s) in o hei Smi h-Agos on no - mal o m o compu ing homology gene a o s [3]. Mo eo e , gene a o s compu ed in he educed objec can easily be p ojec ed in o he o iginal one. The pape is s uc u ed as ollows: in Sec . 2 all he necessa y backg ound ega ding n-Gmaps is ecalled. Sec ion 3 p esen s he main esul o he pape : he defini ion o he simplifica ion algo i hm based on he emo al o wo ypes o cells, and he p oo o he homology p ese a ion. Finally, some expe imen s a e p esen ed in Sec . 4 in o de o illus a e ha he simplifica ion s ep widely educes he numbe o cells, and also he homology gene a o compu a ion. 2 P elimina y Wo ks An n-Gmap is a combina o ial s uc u e de o ed o he ep esen a ion o cellula subdi ision o o ien able o no o ien able nD quasi-mani olds, wi h o wi hou M. Fe i e al. (Eds.): CTIC 2012, LNCS 7309, pp. 20–29, 2012. c Sp inge -Ve lag Be lin Heidelbe g 2012 Remo al Ope a ions in n-Gmaps o Efficien Homology Compu a ion 21 bounda ies (see [11,12] o mo e de ails). Any poly opal complex can be desc ibed by an n-Gmap, while he con e se is no ue (an i-cell can be non homeomo phic o an i-disk). I is possible o associa e a semi-simplicial se wi h any n-Gmap. An n-Gmap is no cons uc ed di ec ly om he cells o he subdi ision bu om mo e elemen a y objec s: da s. The se o da s is s uc u ed h ough in olu ions ha desc ibe how hey a e linked o each o he . De ini ion 1 (n-Gmap). An n-dimensional gene alized map,calledn-Gmap, wi h 0≤n,isa(n+2)- uple G=(D,α0,...,α n)whe e: 1. Dis a ini e se o da s; 2. ∀i, 0≤i≤n,αiis an in olu ion on D; 3. ∀i:0≤i≤n−2,∀j:i+2≤j≤n,αi◦αjis an in olu ion. The cells o he subdi ision a e defined implici ly as se o da s hank o he o bi no ion (see De . 2). An o bi in an n-Gmap can be seen as he se o da s ha we can each om a gi en da and using as many imes as possible he gi en in olu ions. De ini ion 2 (O bi ). Le Φ={π0,··· ,π n}be a se o pe mu a ions de ined on a se D.Φis he pe mu a ion g oup o Dgene a ed by Φ.Theo bi o an elemen d∈D ela i ely o Φ,deno edΦ(d)is he se {φ(d)|φ∈Φ}. As we can see in De . 3, each i-dimensional cell is an n-Gmap is ob ained by an o bi using all he in olu ions excep αi. De ini ion 3 (i-cell). Le Gbe an n-Gmap, and d∈Dbe a da . Gi en i, 0≤i≤n, hei-dimensional cell con aining d,calledi-cell and deno ed by ci(d), is α0,...,α (i−1),α (i+1),...,α n(d). Due o he defini ion o cells as se s o da s, he inciden and adjacency ela ions on cells can easily be es ed. Two dis inc cells c1and c2a e inciden i c1∩c2=∅, and wo i-cells c1and c2a e adjacen i he e is wo da s d1∈c1and d2∈c2 sa is ying d1=αi(d2). When a da dbelongs o an i-dimensional bo de , we ha e αi(d)=dand we say ha dis i- ee. In he example o Fig. 1, ace 3is desc ibed by α0,α 1(1) = {1,2,3,4,5,6}, edge e1by α0,α 2(13) = {13,14,15,16},and e ex 1by α1,α 2(2) = {2,3,7,14,15,24}. 1and e1a e inciden since α1,α 2(2) ∩α0,α 2(13) = {14,15} =∅. 1and 3a e adjacen since 23 ∈ 1,1∈ 3,andα2(1) = 23. In his pape , he main ope a ions used o simpli y an n-Gmap a e he emo al ope a ions (see [7,6] o he defini ions). In ui i ely, emo ing a emo able cell c me ges he wo (i+ 1)-cells inciden o c, wi hou modi ying he o he cells. De ini ion 4 (Remo able cell). Le Gbe an n-Gmap, cbe an i-cell o G.c is emo able i one o he wo condi ions is sa is ied: i=n−1;o 0≤i<n−1and ∀d∈c, αi+1 ◦αi+2(d)=αi+2 ◦αi+1(d). The no ion o emo able cell cis s ongly ela ed o he numbe o i s (i+1) inciden cells, called he deg ee o cand deno ed deg ee(c). A di ec consequence o De . 4 is ha an i−cell co deg ee >2isno emo able. 22 G. Damiand, R. Gonzalez-Diaz, and S. Pel ie 1 3 e1 2 e 2 1 2 (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 o a 2G-map G=(D, α0,α 1,α 2). (a) A 2D cellula complex con aining 3 aces; 9 edges and 7 e ices. (b) The 2G-map desc ibing his cellula complex, ha ing 24 da s ( ep esen ed by numbe ed black segmen s). Two da s linked by α0a e d awn consecu i ely and sepa a ed by a g ay segmen ( o example α0(19) = 20), wo da s linked by α1sha e a common poin ( o example α1(20) = 21), and wo da s linked by α2a e d awn pa allel, he g ay segmen o e hese wo da s ( o example α2(13) = 16). In he example o Fig. 1, all he edges a e emo able (since an (n−1)-cell is always emo able in an nG-map), e ex 2is emo able while e ex 1no . Remo ing edge e1me ges aces 1and 2in one ace ha ing as bounda y he bounda y o 1plus he bounda y o 2minus edge e1. To be able o compu e homology o an n-Gmap, we need o ha e a bounda y ope a o (defined in [5,4]). The bounda y ope a o is defined o n-Gmaps ha ing o ien able cells. No e ha i is possible o ep esen a non-o ien able objec (e.g. a Klein bo le) wi h a n-Gmapha ing only o ien able cells. In he ollowing we de ail he no ions o o ien able cell and signed cell (c . De s. 5 and 6). De ini ion 5 (O ien able i-cell). An i-cell cis o ien able i c=e1∪e2such ha : ∀d∈c,∀j,0≤j≤n,j=i:dis no j- ee ⇒dand αj(d)do no belong o he same se e1o e2.cis non-o ien able o he wise. I cis o ien able, hen i can be pa i ioned in wo se s o da s ep esen ing i s wo o ien a ions and we can associa e a alue −1o +1 oeacho i sda ,called asign. In he ollowing, we only conside n-Gmap ha ing all i s cells signed. De ini ion 6 (Signed i-cell). Le cbe an o ien able i-cell. The co esponding signed i-cell is c oge he wi h a sign o each o i s da d,deno edsgi(d): •sgi(d)=−sgi(αj(d)) ∀j:0≤j<isuch ha dis no j- ee; •sgi(d)=sgi(αj(d)) ∀j:i<j≤n. Fo defining a bounda y ope a o on n-Gmaps, we fi s define he signed inci- dence numbe be ween wo cells ciand ci−1which desc ibes he numbe o imes ha ci−1appea s in he bounda y o ci. De ini ion 7 (Signed incidence numbe ). le {pj}j=1···kbe a se o da s s. . he o bi s {α0,··· ,α (i−2)(pj)}j=1···kmake a pa i ion o α0,...,α (i−1)(d). The signed incidence numbe be ween ciand ci−1is de ined by (ci:ci−1)=  pj,j=1···k|pj∈ci−1 sgi(pj).sgi−1(pj). Remo al Ope a ions in n-Gmaps o Efficien Homology Compu a ion 23 No e ha his defini ion is equi alen o he one gi en in [5]. Now he bound- a y ope a o ∂Go any i-cell cis defined as ∂G(c)=c(c:c)c,whe ec a e (i−1)−cells inciden o c. The bounda y ope a o ∂Gsa isfies ∂G◦∂G=0 when in olu ions αia e wi hou fixed poin s o 0 ≤i≤n−1. Mo eo e , we ha e p o en in [4] ha he homology defined on n-Gmaps by his bound- a y ope a o is equi alen o he simplicial homology o he associa ed quasi- mani olds when he homology o he canonical bounda y o each i-cell is ha o an (i−1)-sphe e, and when ∀d∈D,∀i∈{0,...,n},dis i- ee o αi(d)∈ α0,...,α i−2,α i+2,...,α n(d). In he ollowing, all he conside ed n-Gmaps sa - isfied hese condi ions. 3 Remo al Ope a ions P ese ing Homology In his sec ion, we p o e ha emo ing a deg ee wo cell o a dangling cell p ese es he homology o he n-Gmap. 3.1 Chain Complexes and Chain Con ac ions Le S={Sq}qbe a g aded. A q-chain is a fini e o mal sum o elemen s o Sqwi h coefficien s in Z.Le Cq(S) deno e he g oup o q-chains o S.The chain complex (C∗(S),∂) is he chain g oup C∗(S)={Cq(S)}q oge he wi h a bounda y ope a o ∂.Gi enann-Gmap G,le SGbe he se o all he cells o G.(C∗(SG),∂ G) is he chain complex associa ed o G. Achain con ac ion [13] o (C∗(S),∂) o (C∗(S),∂) is a iple ( ={ q: Cq(S)→Cq(S)}q,g={gq:Cq(S)→Cq(S)}qand φ={φq:Cq(S)→ Cq+1(S)}q) such ha : (i) and ga e chain maps; i.e. q◦∂q=∂ q◦ qand gq◦∂q= ∂ q◦gq o all q; (ii) φis a chain homo opy o idC∗(S)={idq:Cq(S)→Cq(S)}q o g◦ ={gq◦ q:Cq(S)→Cq(S)}q;i.e.φq−1◦∂q+∂ q+1◦φq=idq−gq◦ q o all q; (iii) ◦g=idC∗(S). I a chain con ac ion o (C∗(SG),∂ G) o(C∗(SG),∂ G) exis s, hen he n-Gmaps Gand Gha e isomo phic homology g oups. 3.2 Deg ee Two Cells P oposi ion 1. Le cbe an i-cell in an n-Gmap. I cis emo able and deg ee wo cell, hen he e a e wo (i+1)-cells aand bsa is ying: |(a:c)|=|(b:c)|=1 and o all o he (i+1)-cells c,(c:c)=0. P oo . Since cis deg ee wo, he e a e wo (i+ 1)-cells aand b ha a e inciden o c. Fo hese wo cells, we ha e c∈∂G(a)andc∈∂G(b). So, (a:c)=0and (b:c)=0.I |(a:c)|>1, con adic ion wi h emo al p ope y, hus |(a:c)|=1 (and he same o |(b:c)|=1).Fo allo he (i+ 1)-cells c,cis no inciden o co he wise he deg ee was g ea e han wo. Thus (c:c)=0.  P oposi ion 2. Le cbe an i-cell in an n-Gmap. I cis a emo able deg ee wo cell, and i each j-cell einciden o c, is a e he emo al o caj-cell equal o e c, hen homology is p ese ed a e he emo al o c. 24 G. Damiand, R. Gonzalez-Diaz, and S. Pel ie No e ha he emo al o a cell may induce emo al o o he cells ( o example, i is possible o build a sphe e made o one e ex, one deg ee wo edge and wo aces. Remo ing he edge would sup ess all he da s and so he e ex and he wo aces). The second condi ion ensu es ha only one cell is emo ed P oo . Le (C∗(SG),∂ G) be he chain complex associa ed o G.Sincecis deg ee wo, he e a e wo (i+ 1)-cells aand b ha a e inciden o c.These SG o he cells o he n-Gmap Gob ained a e emo ing he cell cconsis s in SG {a, b, c}∪{a}whe e ais he esul ing (i+ 1)-cell om me ging he wo cells aand b. Since, by P op. 1, |(a:c)|=|(b:c)|= 1 and o all o he (i+1)- cells c,(c:c) = 0, we can cons uc a chain con ac ion ( ,g,φ)o (C∗(SG),∂ G) o (C∗(SG),∂ G) as ollows: (x)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ c−(b:c)∂G(b),i x=c, a,i x=a, 0,i x=b, x, o he wise; g(x)=a−(a:c)(b:c)b, i x=a, x, o he wise; φ(x)=(b:c)b, i x=c, 0,o he wise. To check ha ( ,g,φ) is a chain con ac ion is le o he eade . Mo eo e , we know ha each j-cell inciden o cis p ese ed by he emo al ope a ion. Then Gand Gha e isomo phic homology g oups.  3.3 Dangling Cells Le (C∗(S),∂) be a chain complex. Le s, ∈Ssuch ha |(s: )|=1and (s: ) = 0 o any s∈S,s=s.I we emo esand om S o ge S,we ob ain ano he chain complex (C∗(S),∂) which is called an elemen a y collapse o S. A chain con ac ion o (C∗(S),∂) o(C∗(S),∂)isgi enby (x)=⎧ ⎨ ⎩ 0,i x=s, −(s: )∂(s),i x= , x, o he wise; g(x)=x;φ(x)=(s: ) , i x= , 0,o he wise. The e o e an elemen a y collapse p ese es homology. A subse o Sis collapsible i hey can all be emo ed om Sin a sequence o elemen a y collapses. Le cbe a k-cell, he closu e o c, deno ed c,is hese madeo cplus all he j-cells, 0 ≤j<k ha a e inciden o c. The closu e o a se So cells, deno ed S, is he union o he closu es o all he cells o S. De ini ion 8 (Dangling cell). Le cbe an i-cell. We deno e C he se o (i−1)- cells o ∂G(c),andB={c∈∂G(c)|deg ee(c)>1}.cis dangling i cis o ien able, i s deg ee is 1,{c}∪C Bis collapsible, and each j-cell e∈¯ B,is a e he emo al o caj-cell equal o e c. P oposi ion 3. Le cbe an i-cell in an n-Gmap. I cis emo able and dangling cell, hen i s emo al p ese es he homology o he n-Gmap. P oo . Remo ing cwill emo e also all he cells in C Bbecause hese cells a e included in c(i.e. hei se o da s is included in he se o da s o c). As {c}∪C Bis collapsible, and as all he o he cells a e p ese ed, he homology o he n-Gmap is p ese ed by he defini ion and p ope y o collapsible.  Remo al Ope a ions in n-Gmaps o Efficien Homology Compu a ion 25 3.4 Simpli ica ion P ese ing Homology The main p inciple o he simplifica ion algo i hm consis s in emo ing succes- si ely all he deg ee wo cells and all he dangling cells o all he dimensions s a ing om (n−1)-cells o 0-cells. Fo ha , we s a o define Algo. 1 which simplifies all he i-cells o a gi en n-Gmap o a gi en dimension i. Algo i hm 1. Simplifica ion o i-cells. Inpu :Ann-Gmap G. Ou pu : Simpli y all he i-cells o Gwhile p ese ing he same homology. o each i-cell co Gdo i cis emo able and he deg ee o cis 2 hen Remo e ; else i cis emo able and cis a dangling cell hen push(P, c); epea c←pop(P); push in Pall he dangling i-cells adjacen o c; Remo e c; un il emp y(P); In his algo i hm, we conside successi ely each i-cell c, and he e a e h ee possible cases. Fi s , i cis no emo able, hen we a e su e ha ccanno be emo able in a u u e s ep o he algo i hm. Indeed, we only emo e i-cells and his does no modi y he (i+ 1)-cells inciden o c. Second, i cis emo able and i sdeg eeis wo,we emo ec.Thi d,i cis emo able and dangling, we also emo e c, bu now we ha e o econside all he i-cells adjacen o c. Indeed, hese cells can possibly become dangling due o he emo al o c.A heendo he loop, we ha e conside ed all he i-cells and emo ed all he deg ee 2 cells and he dangling cells ha we e emo able. Now he global simplifica ion me hod consis s only in simpli ying all he i- cells o he n-Gmap o all he cells by dec easing dimensions. We ha e o wo k in dec easing dimensions because he emo al o an i-cell modifies he deg ee o all he inciden (i−1)-cells. A he end o he global simplifica ion algo i hm, we ha e emo ed all he emo able cells o deg ee 2 o dangling. By using P ops. 2 and 3, we know ha he final n-Gmap ob ained a e all he emo als has he same homology han he ini ial n-Gmap. 4 Expe imen s In o de o illus a e he in e es o ou simplifica ion algo i hm, we show esul s on homology gene a o compu a ion o he fi e objec s shown in Fig. 2. Objec s (a), (b) and (c) a e desc ibed by 2-Gmaps; objec s (d) and (e) a e desc ibed by 3-Gmaps. 26 G. Damiand, R. Gonzalez-Diaz, and S. Pel ie (a) (b) (c) (d) (e) Fig. 2. (a) 2- o us. (b) Klein bo le. (c) pinion. (d) owe . (e) Menge sponge. Table 1. Resul s o ou expe imen s. We gi e he numbe o cells (columns #cells) o ini ial objec s, and a e he simplifica ion algo i hm. The las column gi es he ime o he simplifica ion s ep. The wo columns Homology compu a ion gi e he memo y space and he ime o he homology gene a o s compu a ion (0s means less han 10−6s). Objec Ini ial Simplified # cells Homology # cells Homology Simpli . Cell dim. 0123compu a ion 0123compu a ion ime 2- o us 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 Towe 906 1856 952 4 85Mb 140.97s 10 15 4 1 6.53Kb 0s 0s Menge 896 2304 1728 400 159Mb 372.50s 189 365 97 1 2938.00Kb 0.81s 0.03s To compu e he homology gene a o s, we i e a e h ough all he cells o he n- Gmap and we compu e incidence ma ices (which desc ibes he bounda y o he cells) using he incidence numbe defini ion. Then we educe incidence ma ices in o hei Smi h-Agos on no mal o m o compu ing homology gene a o s [3]. Compa ed o he classical Smi h no mal o m, he specifici y o he Agos on educed no mal o m is ha o a gi en dimension d, he basis o he bounda ies Bpis a subse o he basis o cycles Zp, hus he quo ien g oup Hp=Zp/Bp can di ec ly be ob ained by simply emo ing om Zp he bounda ies o infini e o de . No e ha se e al op imiza ions exis s o he educ ion o incidence ma- ices [15,8]. E en i hey can be used, we do no use hem he e as we ocus on showing he imp o emen ob ained wi h he simplifica ion p ocess. The compu a ion o homology gene a o s was implemen ed in Moka [16], a 3D opological modele based on 3-Gmap. Fo his eason, he compu a ion o homology gene a o s is limi ed o 2D and 3D cases, bu all he unc ions a e gene ic in any dimension. The esul s a e p esen ed in Table 1, whe e he simplifica ion s ep widely educes he numbe o cells. On he las column one can see ha he simplifica ion s ep is e y as . Memo y space is also educed as he size o incidence ma ices a e di ec ly linked o he numbe o cells. Remo al Ope a ions in n-Gmaps o Efficien Homology Compu a ion 27 (a) (b) (c) Fig. 3. The gene a o s o H1(in ed) compu ed on simplified objec s, and p ojec ed on ini ial objec s (d awn in g ey). (a) Klein bo le. (b) Towe . (c) Menge sponge. Las ly, we can see in Fig. 3 he diffe en gene a o s o H1ob ained o some objec s. By using he defini ion o emo al ope a ions, we a e able o p ojec he gene a o s o he simplified objec on he ini ial one (by using a simila echnique as in [14,9]). We ha e made a second ype o expe imen s in o de o compa e ou app oach wi h o he exis ing me hods. To ou knowledge he e is no o he gene al me hod which compu e homology gene a o o cellula objec s. Thus we compa e ou solu ion wi h Chomp and RedHom [1,2] which compu e homology gene a o s o cubical complexes. We chose hese wo me hods since he wo so wa es a e pub- licly a ailable. Howe e , i mus be no iced ha ep esen ing a cubical complex by a n-Gmaps is no efficien since a cube is desc ibed by 48 da s; he in e es o cellula model is p ecisely o ep esen non egula subdi isions. In o de o es he scale up p ope y o he h ee me hods, we chose h ee objec s (see in Fig. 4(a), (b) and (c)), and mul iply he size o each oxel by 4 o 9 o he fi s wo objec s, and by 2 o 7 o he las objec which con ains mo e oxels. We can see in Fig. 4 he ime equi ed o compu e homology gene a o s o each objec by he h ee compa ed me hods. These esul s a e eally encou aging o ou me hod which ob ain he bes compu a ion ime o he fi s wo objec s, wi h an impo an gain o he second one. Fo he hi d objec , Chomp,andMoka pe o mances a e e y simila (e en i Chomp is a li le bi quicke ), while RedHom is eally as e . In his las case, Chomp,andMoka ha e simila compu a ion ime han o he wo fi s objec s, while RedHom is ex emely as . We suppose he e is an op imiza ion allowing o emo e di ec ly some block o oxels. Indeed, he uppe pa o he las objec is composed by a ull block o oxels. This kind o imp o emen can also be made o ou me hod. These expe imen s show ha ou me hod is e y compe i i e since i is no op imized o a specific ype o subdi ision bu i is gene ic o any cellula complex. Thus i s main in e es is i s gene ici y and we can conclude om his compa ison ha his is no o he de imen o he efficiency. Mo eo e , we can imp o e ou esul s by adding a hinning p e-p ocessing s ep ha educes he numbe o oxels while p ese ing he homology. 28 G. Damiand, R. Gonzalez-Diaz, and S. Pel ie 0 2 4 6 8 10 12 14 0 100000 300000 500000 700000 Numbe o oxels Chomp RedHom Moka ime (in seconds) (a) 50 40 30 20 10 00400000 800000 1200000 Numbe o oxels ime (in seconds) Chomp RedHom Moka (b) 0 2 4 6 8 10 12 14 16 18 400000 0800000 1200000 Numbe o oxels ime (in seconds) Chomp RedHom Moka (c) Fig. 4. Homology compu a ion ime compa ison o Chomp,RedHom and Moka.Objec s a e made o oxels filling he bounding box (in wi e ame), he filled su aces being bo de s o ca i ies o unnels. (a) Cub1: 1067 oxels; 1 connec ed componen s; 9 unnels; 5 ca i ies. (b) Cub2: 1828 oxels; 1 connec ed componen s; 7 unnels; 4 ca i ies. (c) Cub3: 4003 oxels; 1 connec ed componen s; 6 unnels; 3 ca i ies. 5Conclusion In his pape , we ha e p esen ed an algo i hm ha simplifies an n-Gmap while p ese ing i s homology. Fo ha , i emo es deg ee wo cells and dangling cells. Then we can compu e homology on he educed n-Gmap and p ojec he gene - a o on he o iginal objec . Some esul s show he in e es o he simplifica ion s ep, bo h in memo y space and in compu a ion ime. Some ques ions a e s ill open. The fi s ques ion is abou he condi ions on emo ed cells. Is i possible o emo e some o he ype o cells while p ese ing he homology? The answe is no in 2D and 3D, bu s ill open in highe dimen- sion. This ques ion is ela ed o he defini ion o he minimal gene alized map ha ing he same homology. In 3D, o ob ain his minimal map, we need o use ano he ype o ope a ion (fic i e edge shi ing). Thus we would like o s udy he ex ension o his ope a ion in highe dimension o define he minimal n-Gmap. Re e ences 1. Chomp, h p://chomp. u ge s.edu/ 2. Redhom, h p:// edhom.ii.uj.edu.pl/ 3. Agos on, M.K.: Algeb aic Topology, a fi s cou se. In: Dekke , M. (ed.) Pu e and Applied Ma hema ics (1976)