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)