HAL Id: el-01477399
h ps://hal.a chi es-ou e es. / el-01477399
Submi ed on 27 Feb 2017
HAL is a mul i-disciplina y open access
a chi e o he deposi and dissemina ion o sci-
en i ic esea ch documen s, whe he hey a e pub-
lished o no . The documen s may come om
eaching and esea ch ins i u ions in F ance o
ab oad, o om public o p i a e esea ch cen e s.
L’a chi e ou e e plu idisciplinai e HAL, es
des inée au dépô e à la di usion de documen s
scien i iques de ni eau eche che, publiés ou non,
émanan des é ablissemen s d’enseignemen e de
eche che ançais ou é ange s, des labo a oi es
publics ou p i és.
Compu a ional Homology Applied o Disc e e Objec s
Aldo Gonzalez-Lo enzo
To ci e his e sion:
Aldo Gonzalez-Lo enzo. Compu a ional Homology Applied o Disc e e Objec s. Disc e e Ma hema ics
[cs.DM]. Aix-Ma seille Uni e si e; Uni e sidad de Se illa, 2016. English. � el-01477399�
AIX-MARSEILLE UNIVERSITÉ
École Doc o ale en Ma héma iques e
In o ma ique de Ma seille
THÈSE DE DOCTORAT
en In o ma ique
UNIVERSIDAD DE SEVILLA
Ins i u o de Ma emá icas Uni e sidad de
Se illa
TESIS DOCTORAL
en Ma emá icas
Thèse p ésen ée pou ob eni le g ade uni e si ai e de doc eu
Memo ia p esen ada pa a op a al í ulo de Doc o
Aldo GONZALEZ LORENZO
Compu a ional Homology Applied o Disc e e Objec s
Sou enue le 24/11/2016 de an le ju y :
Massimo FERRI Uni e si à di Bologna Rappo eu
Jacques-Oli ie LACHAUD Uni e si é de Sa oie Rappo eu
Pascal LIENHARDT Uni e si é de Poi ie s Examina eu
Anice o MURILLO Uni e sidad de Málaga Examina eu
Jean-Luc MARI Aix-Ma seille Uni e si é Di ec eu de hèse
Alexand a BAC Aix-Ma seille Uni e si é Di ec eu de hèse
Ped o REAL Uni e sidad de Se illa Di ec eu de hèse
iii
“The scien is s o oday hink deeply ins ead o clea ly. One mus be sane o hink
clea ly, bu one can hink deeply and be qui e insane.”
Nikola Tesla
Abs ac
Compu a ional Homology Applied o Disc e e Objec s
Homology heo y o malizes he concep o hole in a space. Fo a gi en
subse o he Euclidean space, we de ine a sequence o homology g oups,
whose anks a e conside ed as he numbe o holes o each dimension.
Hence, β0, he ank o he 0-dimensional homology g oup, is he numbe
o connec ed componen s, β1is he numbe o unnels o handles and β2
is he numbe o ca i ies. These g oups a e compu able when he space is
desc ibed in a combina o ial way, as simplicial o cubical complexes a e.
Gi en a disc e e objec (a se o pixels, oxels o hei analog in highe di-
mension) we can build a cubical complex and hus compu e i s homology
g oups.
This hesis s udies h ee app oaches ega ding he homology compu-
a ion o disc e e objec s. Fi s , we in oduce he homological disc e e ec o
ield, a combina o ial s uc u e which gene alizes he disc e e g adien ec-
o ield and allows us o compu e he homology g oups. This no ion al-
lows us o see he ela ion be ween di e en exis ing me hods o compu -
ing homology. Nex , we p esen a linea algo i hm o compu ing he Be i
numbe s o a 3D cubical complex, which can be used o bina y olumes.
Finally, we in oduce wo measu es ( he hickness and he b ead h) associa ed
o he holes in a disc e e objec , which p o ide a opological and geome -
ic signa u e mo e in e es ing han only he Be i numbe s. This app oach
p o ides also some heu is ics o localizing holes, ob aining minimal ho-
mology o cohomology gene a o s, opening and closing holes.
∗
Homologie algo i hmique pou les obje s disc e s
La héo ie de l’homologie o malise la no ion de ou dans un espace.
Pou un sous-ensemble de l’espace Euclidien, on dé ini une séquence de
g oupes d’homologie, don leu s angs son in e p é és comme le nomb e
de ous de chaque dimension. Ainsi, β0, le ang du g oupe d’homologie de
dimension zé o, es le nomb e de composan es connexes, β1es le nomb e
de unnels ou anses e β2es le nomb e de ca i és. Ces g oupes son calcu-
lables quand l’espace es déc i d’une açon combina oi e, comme c’es le
cas pou les complexes simpliciaux ou cubiques. À pa i d’un obje disc e
(un ensemble de pixels, oxels ou leu analogue en dimension supé ieu e)
nous pou ons cons ui e un complexe cubique e donc calcule ses g oupes
d’homologie.
Ce e hèse é udie ois app oches ela i es au calcul de l’homologie su
des obje s disc e s. En p emie lieu, nous in oduisons le champ de ec eu s
disc e homologique, une s uc u e combina oi e géné alisan les champs de
ec eu s g adien s disc e s, qui pe me de calcule les g oupes d’homologie.
Ce e no ion pe me de oi la ela ion en e plusieu s mé hodes exis an es
pou le calcul de l’homologie e é èle égalemen des no ions sub iles as-
sociées. Nous p ésen ons ensui e un algo i hme linéai e pou calcule les
i
nomb es de Be i dans un complexe cubique 3D, ce qui peu ê e u ilisé
pou les olumes binai es. En in, nous p ésen ons deux mesu es (l’épaisseu
e la la geu ) associées aux ous d’un obje disc e , ce qui pe me d’ob eni
une signa u e opologique e géomé ique plus in é essan e que les simples
nomb es de Be i. Ce e app oche ou ni aussi quelques heu is iques pe -
me an de localise les ous, d’ob eni des géné a eu s d’homologie ou de
cohomologie minimaux, d’ou i e de e me les ous.
∗
Homología compu acional pa a los obje os disc e os
La eo ía de la homología o maliza la noción de aguje o en un espacio.
Dado un subconjun o del espacio Euclídeo, se de ine una secuencia de g u-
pos de homología, cuyos angos se conside an el núme o de aguje os de
cada dimensión. Así, β0, el ango del g upo de homología de dimensión 0,
es el núme o de componen es conexas, β1es el núme o de úneles o asas y
β2es el núme o de ca idades. Es os g upos son calculables cuando el es-
pacio es desc i o de mane a combina o ia, como ocu e con los complejos
simpliciales o cúbicos. También, dado un obje o disc e o (un conjun o de pí-
xeles, óxeles o elemen os de dimensión supe io ), podemos cons ui un
complejo cúbico y así calcula sus g upos de homología.
Es a esis es udia es en oques ela i os al cálculo de la homología en
los obje os disc e os. En p ime luga , in oducimos el campo de ec o es dis-
c e o homológico, una es uc u a combina o ia que gene aliza el campo de
ec o es g adien e disc e o y que pe mi e calcula los g upos de homolo-
gía. Es e concep o pe mi e e la elación en e a ios mé odos exis en es
pa a el cálculo de la homología. Pos e io men e p esen amos un algo i mo
lineal pa a calcula los núme os de Be i de un complejo cúbico 3D, y po
an o, de un olumen bina io. Po úl imo in oducimos dos medidas (el es-
peso y la ampli ud) asociadas a los aguje os de un obje o disc e o, las cuales
p opo cionan una i ma opológica y geomé ica más in e esan e que sim-
plemen e los núme os de Be i. El cálculo de es as medidas además ambién
apo a unas heu ís icas pa a localiza los aguje os, ob ene gene ado es de
homología o cohomología mínimos, ab i o ce a aguje os.
ii
F ench Ex ended Abs ac –
Résumé é endu
La héo ie de l’homologie o malise la no ion de ou dans un espace. Pou
un sous-ensemble de l’espace Euclidien, on dé ini une séquence de g oupes
d’homologie, don leu s angs son in e p é és comme le nomb e de ous
de chaque dimension. Ainsi, β0, le ang du g oupe d’homologie de dimen-
sion zé o, es le nomb e de composan es connexes, β1es le nomb e de
unnels ou anses e β2es le nomb e de ca i és. Ces no ions peu en aussi
ê e dé inies pou des dimensions supé ieu es, mais il n’y a plus d’in ui ion
géomé ique pou elles. Les g oupes d’homologie son calculables quand
l’espace es déc i d’une açon combina oi e, comme c’es le cas pou les
complexes simpliciaux ou cubiques. Puisqu’un obje disc e (un ensemble
de pixels, oxels ou leu analogue en dimension supé ieu e) peu ê e ans-
o mé en complexe cubique, nous pou ons aussi calcule ses g oupes d’ho-
mologie.
Ce e hèse é udie ois app oches ela i es au calcul de l’homologie su
des obje s disc e s.
Le champ de ec eu s disc e homologique
Le champ de ec eu s disc e homologique (ab égé HDVF en anglais) es in-
odui au Chapi e 3. Le HDVF es une s uc u e combina oi e dé inie su
un CW-complexe ini (no ion géné alisan les complexes simpliciaux e cu-
biques en e au es) qui indui une éduc ion (c . Sec ion 2.3.4), donc nous
pou ons dédui e ses nomb es de Be i, un ensemble de géné a eu s de ho-
mologie ou cohomologie, e c.
É an donné un CW-complexe K, un HDVF es un pai d’ensembles dis-
join s de ses cellules X= (P, S) els que la es ic ion de la ma ice du bo d
sous ces deux ensembles (c’es -à-di e, la sous-ma ice a ec les colonnes co -
espondan es aux cellules de Se les lignes co espondan es aux cellules de
P) es in e sible. Nous démon ons (c . Theo em 3.9) qu’un HDVF indui
une éduc ion.
Nous é udions ensui e commen calcule e icacemen un HDVF a ec sa
éduc ion. En nous appuyan su des o mules connues du calcul ma iciel,
nous ou ons que la meilleu e op ion consis e à ajou e les cellules dans le
HDVF pa couples (don une cellule es ajou ée à Pe l’au e à S) e me e
à jou la éduc ion à chaque é ape. Nous é i ons ainsi ou e in e sion de
ma ice ou calcul du dé e minan . Nous déduisons alo s que le calcul d’un
HDVF e sa éduc ion a une complexi é O(n3).
Nous in oduisons ap ès cinq opé a ions basiques pou ans o me un
HDVF. Bien que la no ion de HDVF soi inspi ée de la héo ie disc è e de
Mo se e que ce ains concep s son pu emen des géné alisa ions de ce e
héo ie, nous ema quons que ces opé a ions son nou elles puisqu’elles
son basées su le o malisme du HDVF.
iii
La sec ion sui an e es dédiée à l’é ude de la ela ion en e le HDVF
e d’au es mé hodes d’homologie algo i hmique. Nous déduisons que le
HDVF géné alise le champ de ec eu g adien disc e (disc e e g adien
ec o ield) e le champ de ec eu g adien disc e i é é (i e a ed disc e e
g adien ec o ield). Nous démon ons aussi commen le calcul de la o me
no male de Smi h (la mé hode classique pou calcule les nomb es de Be i)
es équi alen au calcul d’un HDVF. Pa conséquence, on peu calcule l’ho-
mologie pe sis an e a ec un HDVF en u ilisan les opé a ions basiques.
Nous inissons ce e pa ie a ec une é ude expé imen ale (e non héo-
ique) de la complexi é du calcul du HDVF. Bien que nous es imons sa
complexi é comme O(n3), nous app écions qu’elle es en moyenne O(n2)
ou même O(n1.4)si nous calculons seulemen le HDVF sans sa éduc ion.
Calcul apide des nomb es de Be i su un complexe cubique 3D
Ce e pa ie es le ui d’une é oi e collabo a ion a ec Ma eusz Juda. Nous
in oduisons un algo i hme e icien pou calcule les nomb es de Be i su
un complexe cubique 3D. Ce algo i hme es essen iellemen basé su le
calcul du nomb e de composan es connexes dans deux g aphes, donc sa
complexi é es linéai e.
Calcule les g oupes d’homologie d’un CW-complexe de dimension quel-
conque equie des echniques géné ales, elles que la mé hode basée su
le calcul de la o me no male de Smi h ou le HDVF. Pa con e, si le CW-
complexe es un complexe cubique 3D, il exis e une as uce pou calcule ses
nomb es de Be i s’il es un complexe cubique 3D. Soi Kun el complexe,
nous démon ons (c . P oposi ion 4.3) que son nomb e de Be i de dimen-
sion 0, β0(K), es le nomb e de composan es connexes d’un ce ain g aphe
dé ini su les cellules de dimension 0 e 1 de K. Nous p ou ons ensui e
qu’il exis e une ela ion en e les nomb es de Be i de Ke les nomb es de
Be i de son complémen ai e dans un su -complexe acyclique (c . P oposi-
ion 4.4). Ceci pe me de démon e que β2(K)es le nomb e de compo-
san es connexes d’un ce ain g aphe dé ini su les cellules de dimension 2
e 3 de L−K, où Les un su -complexe de Kacyclique. Ces ésul a s o -
malisen l’idée in ui i e que β0(K)es le nomb e composan es connexes de
Ke β2(K), le nomb e de ca i és ou composan es connexes bo nées de son
complémen ai e. Ces p oposi ions son ou es démon ées en s’appuyan
su le o malisme des HDVFs.
É an donné que β0(K)e β2(K)peu en ê e ob enus en comp an des
composan es connexes, on peu dédui e β1(K)g âce à la o mule d’Eule -
Poinca é. Nous p oposons une app oche simple e i é a i e pou calcule
ses quan i és en u ilisan l’algo i hme classique pou comp e des compo-
san es connexes a ec un pa cou s en p o ondeu . Ensui e nous in oduisons
un algo i hme écu si a ec une echnique di ise pou égne qui pe me de
pa allélise pa iellemen le calcul du nomb e de composan es connexes.
Ce e app oche es spécialemen conçue pou les complexes cubiques e
n’es donc pas alable pou des complexes simpliciaux.
Nous compa ons no e implémen a ion a ec la biblio hèque CAPD : :Red-
Hom e nous mon ons que nous ob enons de meilleu s emps d’exécu-
ion ainsi qu’elle pe me de ai e des complexes plus g ands g âce à ses
moind es besoins de mémoi e.
x
Acknowledgemen s
I would like o hank my ad iso s Jean-Luc Ma i, Alexand a Bac and Ped o
Real o hei guidance, encou agemen , and o p o iding me he eedom
o wo k on he opics ha in e es ed me mos . I am also indeb ed o many
colleagues in he G-Mod eam o hei help in so many echnical p oblems:
A naud Pole e, Jo is Ra aglia, Jules Mo el, E ic Remy and Romain Ra in
o ci e a ew.
I also wan o hank all hose colleagues ha I ha e me —pe sonally o
i ually—du ing hese h ee yea s wi h whom I ha e had so many in e -
es ing discussions: E in Chambe s, F édé ic Chazal, Guillaume Damiand,
Paweł Dło ko, He be Edelsb unne , Lau en Fuchs, Tao Ju, Lu Liu, Clé-
men Ma ia, Pa ick Min, Vidi Nanda, S e e Oudo , Sophie Viseu and he
DG al eam. I am pa icula ly g a e ul o Ma eusz Juda, whose collabo a-
ion led o success ul esul s ha I could o he wise ne e ha e imagined.
I hank my iends, la ma es, amily and my lo e, Apolline, who always
suppo ed me and, in exchange, now know a li le mo e abou holes.
x ii
Con en s
Abs ac
F ench Ex ended Abs ac – Résumé é endu ii
Spanish Ex ended Abs ac – Resumen ex endido xi
Acknowledgemen s x
1 In oduc ion 1
1.1 O e iew .............................. 1
1.2 How o ead his disse a ion .................. 3
2 Common Backg ound 5
2.1 Gene al Topology ......................... 5
2.2 Algeb aic Topology ........................ 7
2.2.1 Homo opy ......................... 8
2.2.2 Homology ......................... 8
2.3 Compu a ional opology ..................... 10
2.3.1 Homo opy ......................... 11
2.3.2 Simplicial homology ................... 11
2.3.3 Cubical homology .................... 14
2.3.4 E ec i e Homology ................... 15
2.3.5 Pe sis en homology ................... 17
2.4 Digi al Geome y ......................... 18
3 The Homological Disc e e Vec o Field 21
3.1 In oduc ion ............................ 21
3.2 P e ious Wo ks .......................... 22
3.3 P elimina ies ............................ 22
3.3.1 CW Complex ....................... 22
3.3.2 Homology o a CW complex . . . . . . . . . . . . . . 23
3.3.3 Homological In o ma ion . . . . . . . . . . . . . . . . 23
3.3.4 Disc e e Mo se Theo y .................. 24
3.3.5 Some Ma ix P ope ies ................. 26
3.4 Mo i a ion ............................. 28
3.5 In oducing he HDVF ...................... 31
3.6 Compu ing a HDVF ....................... 35
3.6.1 Compu ing he Reduced Complex . . . . . . . . . . . 35
3.6.2 Compu ing also he educ ion . . . . . . . . . . . . . 41
3.6.3 Some ques ions abou he algo i hm . . . . . . . . . . 41
3.6.4 Ano he algo i hm o compu ing a HDVF ...... 43
3.7 De o ming a HDVF ........................ 43
3.7.1 Basic Ope a ions ..................... 43
3.7.2 Delinea ing (co)homology gene a o s ......... 46
x iii
3.7.3 Connec i i y be ween HDVFs .............. 49
3.8 Rela ion wi h o he Me hods in Compu a ional Homology . 49
3.8.1 I e a ed Mo se decomposi ion ............. 49
3.8.2 The Smi h no mal o m ................. 50
3.8.3 Pe sis en homology ................... 51
3.9 Expe imen al Complexi y .................... 51
3.10 Conclusion and u u e wo k ................... 54
4 Fas Compu a ion o Be i Numbe s on Th ee-Dimensional Cubi-
cal Complexes 59
4.1 In oduc ion ............................ 59
4.2 The I e a i e Algo i hm ..................... 61
4.3 The Recu si e Algo i hm ..................... 66
4.4 Resul s ............................... 68
4.5 Conclusion ............................. 69
5 Measu ing Holes 71
5.1 In oduc ion ............................ 71
5.2 The measu es ........................... 74
5.2.1 On he compu a ion o he measu es . . . . . . . . . . 77
5.2.2 The obus ness o he measu es ............. 78
5.3 Thickness and b ead h balls ................... 80
5.4 Small gene a o s .......................... 81
5.4.1 Homology gene a o s .................. 93
5.4.2 Cohomology gene a o s ................. 94
5.5 Opening o closing holes ..................... 95
5.5.1 Opening a hole ...................... 98
5.5.2 Closing a hole ....................... 100
5.5.3 We wan oxels, no cubes ................ 102
5.6 Conclusion and u u e wo ks .................. 105
6 Conclusion 109
6.1 Gene al conclusion ........................ 109
6.1.1 Homological Disc e e Vec o Field . . . . . . . . . . . 109
6.1.2 Fas Compu a ion o Be i Numbe s on Th ee-Dimensional
Cubical Complexes .................... 111
6.1.3 Measu ing Holes ..................... 112
6.2 O he wo ks ............................ 113
6.2.1 Cellula skele ons ..................... 113
6.2.2 Opening holes in disc e e objec s ............ 114
xix
Fo Da id Robe Jones.
1
Chap e 1
In oduc ion
1.1 O e iew
Unde s anding an objec can be add essed by de e mining i s olume, i s
con exi y, i s cu a u e, i s medial axis o any o he geome ic desc ip o . A
highe le el analysis can be made h ough opology, which ole a es con in-
uous de o ma ions. This could be seen as a less in e es ing app oach, since
we could no dis inguish a co ee mug om a donu , bu i ac ually p o-
ides a mo e essen ial in o ma ion o he objec . Homology is a powe ul
ool as i s o malizes he concep o hole in algeb aic e ms.
One o he clea es concep s in opology is ha o connec i i y. I ells us
how many disjoin pa s he e a e in an objec . Le us in oduce his no ion
o a simple amily o spaces: g aphs. Conside a g aph G= (V, E). We
ecall ha a pa h is a sequence o inciden edges [e1, e2, . . . , e ], ha is, each
pai o consecu i e edges sha e a e ex. Then, wo e ices u, ∈Va e
said o be connec ed i he e is a pa h connec ing hem, namely [{u, w1},
{w1, w2},··· ,{w , }]. Being connec ed is an equi alence ela ion, so we
can de ine classes and he quo ien se . Gi en a e ex u∈V, he class
[u]is he se o all e ices which a e connec ed o u, ha is, he connec ed
componen con aining u. Thus, he quo ien se unde his ela ion is he
collec ion o he connec ed componen s o he g aph, and i s ca dinal is he
numbe o connec ed componen s.
Homology heo y ex apola es his concep o highe dimensions. In-
s ead o g aphs, we conside simplicial complexes (o any simila s uc u e
such as cubical complexes o CW complexes). Nex , we de ine a homology
g oup Hq o each dimension q≥0. Le us assume ha ou simplicial com-
plex is embedded in R3. Then i s homology g oups a e isomo phic o ee
g oups o he o m Zβ, so hei ank is β. Fo each dimension q≥0, he
ank o Hq—called βq, he q- h Be i numbe —is he numbe o q-holes.
We can in e p e he 0-holes as connec ed componen s, so β0(as he ca -
dinal o he p e iously de ined quo ien se ) is he numbe o connec ed
componen s. The 1-holes co espond o unnels o handles and he 2-holes,
o ca i ies o oids. I is s aigh o wa d o gene alize hese no ions o
highe dimensions, hough we lose geome ic in ui ion. Fo ins ance, a hol-
low squa e has one 1-hole (a handle) and a hollow cube has one 2-hole (a
oid), so a hollow ou -dimensional cube con ains a 3-hole, e en i we can-
no concei e wha i is. Also, i he simplicial complex is embedded in a
highe -dimensional space, like he Klein bo le, i s homology g oups can
con ain a o sion subg oup, which e eals he p esence o “s ange” holes.
∗
2Chap e 1. In oduc ion
Homology g oups a e compu able, so gi en a space wi h a ini e and
combina o ial desc ip ion (such as a simplicial complex), we can igu e ou
how many holes o each dimension i has. Mo eo e , we can e en “d aw”
he holes, al hough his p esen s many disad an ages. Consequen ly, ho-
mology allows us o compa e and unde s and objec s wi h ega d o hei
opology, ha is, hei holes.
This heo y can be conside ed o ha e begun wi h he Eule -Poinca é
cha ac e is ic du ing he 18 h cen u y. Howe e , i s p ac ical applica ions
ha e no been exploi ed un il he las wen y yea s due o i s compu a ional
complexi y. The e a e applica ions in dynamical sys ems [89,93], ma e ial
science [27,112], elec omagne ism [62,40], geome ic modeling [43], image
unde s anding [2,52,96,30] and senso ne wo ks [38]. The gene al idea is
o use homology o analyze and unde s and high dimensional s uc u es in
a igo ous way. Pe sis en homology has e olu ionized hese applica ions,
and mo e han likely a second e olu ion will come wi h he zigzag pe sis en
homology.
∗
The con en o his hesis is o ganized in o h ee main chap e s:
The homological disc e e ec o ield This esea ch was mo i a ed by he
wo ks o Helena Molina-Ab il and Ped o Real abou homological spanning
o es s (see [90] o a gene al pic u e), which we e he s a ing poin o his
PhD hesis. F om his, we de ine a combina o ial s uc u e, namely he ho-
mological disc e e ec o ield (HDVF), which encodes a educ ion on a CW
complex. This concep passed h ough di e en o malisms un il we ound
a clea de ini ion ha allows a deep unde s anding o i s na u e. Roughly
speaking, we de ined i i s ly as a disc e e ec o ield (possibly wi h cy-
cles) i e a i ely buil and we ended up de ining i as a collec ion o cells
sa is ying an algeb aic condi ion ega ding he bounda y o he complex.
This concep , which we p o e o be equi alen o di e en me hods in com-
pu a ional homology, howe e shows an in e es ing combina o ial ela ion
be ween di e en compu ed homology g oups o a same complex.
The HDVF hus imp o es he homological spanning o es in di e en
ways: i wo ks o any dimension, i always compu es (i he g ound ing
is a ield) he homology g oups wi hou needing a la e diagonaliza ion
and i s clea de ini ion allows us o p o e heo ems using i s o malism.
Ne e heless, he e a e s ill many in e es ing open ques ions.
Fas compu a ion o Be i numbe s on h ee-dimensional cubical com-
plexes This esea ch, which was conduc ed in collabo a ion wi h Ma eusz
Juda, de elops an algo i hm o e icien ly compu ing only he Be i num-
be s o a 3D cubical complex ( ha is, wi hou homology gene a o s no a
educ ion). I s desc ip ion is simple and ollows om a cons uc i e p oo
in ol ing he HDVF amewo k. Also, he egula s uc u e o he cubi-
cal complexes allows us o e icien ly pa allelize he algo i hm. We show
ha his algo i hm ou pe o ms he exis ing so wa e specialized in cubical
homology.
1.2. How o ead his disse a ion 3
Measu ing holes Le us in oduce he p oblem ha o igina ed his e-
sea ch by an example. Conside a cubic po ion o cheese wi h edge leng h
o 5 cm. I we ind ou ha he e a e 10 holes— ha is, β2= 10—we canno
eally ell i he cheese is ull o holes o i he e a e jus some small bubbles
inside. A di ec app oach is o weigh he cheese o igu e ou he p opo ion
o oid in he po ion, bu his does no ell us i all holes ha e simila size o
no . Mo eo e , his will no ell us any hing abou he 1-holes— he e may
be some unnels going h ough he po ion o o us-shaped holes inside he
cheese. The idea we had is o g adually expand he cheese and see when
he holes disappea . Mo eo e , because we a e opologis s and we always
hink abou duali y, we can also sh ink o e ode he cheese and see when he
holes disappea , which gi es us an idea o he agili y o he holes.
This example gi es a good in ui ion abou he wo measu es ha we
in oduce in Chap e 5. By using pe sis en homology and he signed dis-
ance ans o m o a disc e e objec we ob ain a pai o alues— he hickness
and he b ead h— o each hole, e en hough holes canno be canonically
loca ed. These measu es ha e many good p ope ies: hei de ini ion is
gene al o objec s o any dimension and o any ype o holes and hey
a e s able unde small pe u ba ions on he bounda y o he objec s. Mo e
su p isingly, hey seem use ul o isualize holes, ind small gene a o s o
homology o cohomology and close o open holes. Le us poin ou ha we
can do his o all he holes o jus o some o hem—which we can choose
ega ding hei measu es. These las esul s a e qui e isual, so we illus a e
hem by p esen ing some examples.
1.2 How o ead his disse a ion
The common backg ound o he h ee main chap e s is p esen ed in Chap-
e 2, while he speci ic p elimina ies o each chap e a e included in i .
The h ee chap e s a e o de ed ch onologically, bu his o de also e-
eals an inc easing in e es in disc e e objec s. Roughly speaking, Chap-
e 3p esen s a amewo k o compu ing he homology o CW-complexes
(including cubical complexes); Chap e 4shows how o coun he numbe
o holes in a 3D disc e e objec and Chap e 5s udies u he he geome y
o i s holes, e en in highe dimensions. Consequen ly, he chap e s a e no
comple ely independen :
•Chap e 3can be ead wi hou he o he wo.
•Chap e 4uses concep s om Chap e 3in he p oo s, bu hey can be
omi ed i one is only in e es ed in he algo i hm.
•Chap e 5can almos be ead wi hou e e ing o Chap e 3, excep
o Sec ion 5.4 and 5.5.
No e ha each chap e con ains i s own conclusion. The gene al conclu-
sion in Chap e 6 ecalls he main esul s o each opic and explains some
u u e wo ks no s ic ly ela ed o he esea ch de eloped he ein.
2.3. Compu a ional opology 11
2.3.1 Homo opy
The undamen al g oup is classically compu ed wi h he Sei e – an Kam-
pen heo em. Un o una ely, i p o ides a g oup ep esen a ion (a se o le -
e s wi h ela ions be ween hem) o he undamen al g oup, which is com-
pu a ionally useless. The p oblem o elling i he undamen al g oup o
a space is he i ial g oup is undecidable, as i educes o he hal p ob-
lem. Thus, he e is no algo i hm ha ex ac s any in o ma ion om he
g oup ep esen a ion gi en by he Sei e – an Kampen heo em and hence
he undamen al g oup canno be used (compu a ionally) as a opological
in a ian . Ne e heless, le us poin ou ha [11] succeeds in compa ing
di e en undamen al g oups by ex ac ing some compu able in a ian s.
2.3.2 Simplicial homology
The easies way o unde s anding homology in compu a ional e ms is h ough
simplicial complexes.
Simplicial complexes
Gi en a collec ion o poin s {p0, . . . , pm} ⊂ Rn, hei con ex hull is
hp0, . . . , pmi=(m
X
i=0
λipi|λi≥0,
m
X
i=0
λi= 1)
We ecall also ha a collec ion o poin s {p0, . . . , pm} ⊂ Rnis in gene al
posi ion i he se o ec o s {−−→
p0pi|i≥1}is linea ly independen . In o he
wo ds, no (m−1)-dimensional la con ains all he poin s.
De ini ion 2.13. Aq-simplex is he con ex hull o q+1 poin s in gene al posi ion.
Le σ=hp0, . . . , pqibe a simplex, i s aces a e he simplices τ=hIi o e e y
subse I⊂ {p0, . . . , pq}.
Aq-simplex σis said o be o dimension qand we deno e i by σ(q)
when his is no clea . No e ha his no a ion is also used o o he ypes o
complexes.
De ini ion 2.14. A ( ini e) simplicial complex Kis a collec ion o simplices such
ha (1) o e e y σ∈K, i s aces a e also con ained in Kand (2) o e e y σ, τ ∈
K, i s in e sec ion is emp y o a common ace. I s dimension is he maximal
dimension o i s simplices. Fo each q≥0, we deno e by Kq he se o he q-
simplices o K.
We now de ine he (simplicial) chain complex (C, d)associa ed o he
simplicial complex K:
•Fo each q≥0,Cqis he ee R-module gene a ed by he q-simplices
o K
Cq=(X
i
λi·σi|λi∈R, σi∈Kq)
•dqis de ined o e he q-simplices as he al e na ing sum o i s (q−1)-
aces
dq(hx0, . . . , xqi) =
q
X
i=0
(−1)i+1 ·hx0,...,ˆxi,...xqi
12 Chap e 2. Common Backg ound
whe e ˆximeans ha he poin xihas been emo ed. Fo he 0-simplices
we de ine d0= 0.
I is easy o check ha o e e y q > 0,dq−1dq= 0. Thus (C, d)is a chain
complex and he (simplicial) homology g oups o Ka e well de ined. No e
ha Kis a opological space and hus we can de ine i s singula homol-
ogy g oups. Fo una ely, hey a e isomo phic o he simplicial homology
g oups.
Mo e abou he homology g oups
Le us now look mo e closely a he homology g oups. They a e quo ien
spaces, whe e each elemen is a class unde he equi alence ela ion
∀x, y ∈Cq, x ∼y⇔x−y∈im(dq+1).
They a e ini ely gene a ed R-modules, so he e exis s a gene a ing se (a
basis i i is a ec o space). By he undamen al heo em o ini ely gene -
a ed abelian g oups [37, §5.2], he e a e wo di e en “no maliza ions” o
his gene a ing se :
1. The R-module is isomo phic o Rβq×R/λ1R×R/λ2R×. . ., whe e
each λidi ides λi+1. This is called he in a ian ac o decomposi ion.
2. The R-module is isomo phic o Rβq×R/λ1R×R/λ2R×. . ., whe e
each λiis a powe o some p ime numbe . This is called he p ima y
decomposi ion.
As mos o he li e a u e abou compu a ional homology, we use he i s
decomposi ion. The numbe βqis called he q- h Be i numbe and λ1, . . . , λ
a e he o sion coe icien s o dimension q. Le us ecall ha i he ambien
space is R3 he e a e no o sion coe icien s.
The homology g oups depend on he g ound ing R. Mos o he wo ks
in compu a ional homology choose R=Z2since he ope a ions be ween
chains a e simple , he homology g oups a e ec o spaces and hus he e
a e no o sion coe icien s. Howe e , he homology g oups wi h any g ound
ing Rcan be deduced om he homology g oups wi h coe icien s in Zby
he uni e sal coe icien heo em [67, §3.A].
Can we see he homology g oups? I ou simplicial complex is in R3
hen he e a e no o sion coe icien s and we can conside he g ound ing
as Z2. Chains a e jus se s o simplices and he elemen s o he homology
g oups (which a e equi alence classes since hey a e quo ien g oups) a e
collec ions o se s o simplices. Figu e 2.3 shows h ee ep esen a i es o
he same elemen o he homology g oup. This means ha he di e ence
be ween any wo o hem (ac ually hei symme ic di e ence) is a bound-
a y, ha is, i belongs o im(d2).
Ins ead o seeing all he elemen s in he homology g oups i may be
mo e in e es ing o isualize only a basis o hese g oups and choose a ep-
esen a i e o each gene a o . The e o e, he e is a double choice. Fig-
u e 2.4 shows wo gene a o s o he one-dimensional homology g oup.
The i s se o cycles gi es he image ha we expec om a se o gene a-
o s: hey co espond o he holes o he simplicial complex. We ha e also
2.3. Compu a ional opology 13
FIGURE 2.3: Th ee cycles o C1belonging o he same class
in H1(C).
added he second se o cycles which is a basis o H1(C)bu whe e he
holes a e no so well loca ed.
FIGURE 2.4: Two possible ep esen a ions o he basis o
H1(C).
This p o ides a good pic u e abou homology. On he one hand, we
conside he Be i numbe s o a simplicial complex as he numbe o holes
o each dimension, which usually co esponds wi h he in ui ion. No e ha
a wi e- ame cube and e ahed on (see Figu e 2.5) ha e i e and h ee 1-
holes espec i ely, ins ead o six and ou . One usually sees an ex a hole,
which is he sum o he o he holes, bu his depends on he poin o iew.
Thus, he Be i numbe s le us o mally de ine he numbe o holes in a
space ega dless o i s embedding. On he o he hand, we canno say whe e
hese holes a e, as he e is a la ge numbe o possible se s o gene a o s and
he e is no canonical choice.
FIGURE 2.5: A wi e- ame cube and e ahed on seen om
wo di e en poin s o iew.
How o compu e he homology g oups
The simplicial homology g oups a e compu able. Since he bounda y op-
e a o s a e linea , hey can be encoded as a sequence {Dq}n
q=1 o ma ices,
called bounda y ma ices. The classical me hod o compu ing he homology
g oups was in oduced in [99] and consis s in compu ing he Smi h no mal
o m o he bounda y ma ices.
14 Chap e 2. Common Backg ound
De ini ion 2.15. The Smi h no mal o m o a (no necessa ily squa e) ma ix A∈
Mn×m(R)wi h en ies in a ing Ris he ma ix
N=∆ 0
0 0 ∈Mn×m(R)
such ha ∆is a diagonal squa e ma ix
∆ =
α10 0 0
0α20 0
0 0 ...0
0 0 0 α
wi h αidi iding αi+1 o 1≤i < and he e a e wo in e ible ma ices Pand Q
such ha PAQ =N.
The me hod p esen in [99] ob ains he in a ian ac o decomposi ion o
he homology g oups. A a ian o his me hod in oduced in [102] ob ains
also a basis o he homology g oups. A e y clea desc ip ion o his me hod
can be ound in [8].
Le us poin ou ha compu ing he Smi h no mal o m o a ma ix is
simila o pe o m a Gaussian elimina ion, excep ha e e y pi o mus
di ide all he emaining en ies. I Ris a ield hen he e is no di icul y. I
no , one has o pe o m elemen a y ope a ions on he ows and columns o
he ma ix un il an en y di iding all he o he s appea s. Then his en y is
chosen as a pi o and we make all he o he en ies in i s ow and column
in o ze os.
S o johann in oduced in [111] an algo i hm wi h supe -cubical com-
plexi y o compu ing he Smi h no mal o m o a ma ix o e he in ege s
o o e he in ege s modulo d. Le us also poin ou ha he compu a ion
o he Smi h no mal o m can p oduce huge in ege s [65].
2.3.3 Cubical homology
In his sec ion we in oduce he cubical complexes and hei homology
g oups. These complexes a e e y simila o he simplicial complexes, ex-
cep ha hey a e buil wi h q-dimensional squa es ins ead o q-dimensional
iangles.
Le us ix ou ambien space as Rn. An elemen a y in e al is an in e al
o he o m [k, k + 1] o a degene a e in e al [k, k], whe e k∈Z.
De ini ion 2.16. An elemen a y cube is he Ca esian p oduc o nelemen a y
in e als
σ= [x1, x1+δ1]×···×[xn, xn+δn]xi∈Z, δi∈ {0,1}
=: [x, δ]x∈Zn, δ ∈ {0,1}n
I s Khalimsky coo dina es is he ec o σK= 2x+δ∈Zn, he sum o he
in e als endpoin s. The numbe o non-degene a e in e als in his p oduc σ(o
he numbe o odd en ies in i s Khalimsky coo dina es) is he dimension o σ. An
elemen a y cube o dimension qwill be called a q-cube.
Gi en wo elemen a y cubes σand τ, we say ha σis a ace o τi σ⊂τ.
2.3. Compu a ional opology 15
Fo ins ance, he Khalimsky coo dina es o he elemen a y cube σ=
[1,1] ×[2,3] ×[1,2] a e (2,5,3) and hence i is a 2-cube.
De ini ion 2.17. A ( ini e) nD cubical complex Kis a collec ion o elemen a y
cubes such ha o e e y σ∈K, i s aces a e also con ained in K. I s dimension
is he maximal dimension o i s elemen a y cubes. Fo each q≥0, we deno e by
Kq he se o he q-cubes o K.
Le us poin ou ha we do no demand any condi ion abou he in-
e sec ion o di e en elemen a y cubes due o he egula s uc u e o he
cubical complex.
We now de ine he (cubical) chain complex (C, d)associa ed o he cubi-
cal complex K:
•Fo each q≥0,Cqis he ee R-module gene a ed by he q-cubes o K
Cq=(X
i
λi·σi|λi∈R, σi∈Kq)
•dqis de ined o e he q-cubes as he al e na ing sum o i s (q−1)- aces
along each axis
dq([x, δ]) =
n
X
i=1
(−1)o(i)·([x+δi·ei, δ −δi·ei]−[x, δ −δi·ei])
whe e o(i)deno es he numbe o ones in (δ1, . . . , δi)(o equi alen ly,
he numbe o non-degene a e in e als among he i i s elemen a y
in e als o [x, δ]), x+δi·ei= (x1, . . . , xi+δi, . . . , xn)and δ−δi·ei=
(δ1,...,0, . . . , δn). Fo he 0-cubes we de ine d0= 0.
Again, i is easy o check ha o e e y q > 0,dq−1dq= 0. Thus (C, d)is
a chain complex and he (cubical) homology g oups o Ka e well de ined.
No e again ha Kis a opological space whose singula homology g oups
a e isomo phic o i s cubical homology g oups.
2.3.4 E ec i e Homology
Compu ing he homology g oups using he Smi h no mal o m is p ac i-
cally impossible o la ge complexes due o i s high complexi y. A solu ion
o educe he amoun o in o ma ion o compu e is he no ion o educ ion.
I is a s ong ela ion be ween wo chain complexes ha gua an ees ha
hey ha e isomo phic homology g oups. This is he main ool in e ec i e
homology heo y [106]. We ypically educe he ini ial chain complex o an-
o he one much smalle (called educed complex). In he ollowing we omi
he subsc ip s whene e i is clea om he con ex .
De ini ion 2.18. A educ ion be ween wo chain complexes (C, d)and (C′, d′)is
a iple o g aded homomo phisms ρ= (h, , g)such ha :
•hq:Cq→Cq+1 o e e y q≥0
• q:Cq→C′
qis a chain map: q−1dq=d′
q q
•gq:C′
q→Cqis also a chain map: gq−1d′
q=dqgq
16 Chap e 2. Common Backg ound
•g = 1C−dh −hd
• g = 1C′
•hh, h, hg = 0
A educ ion is usually ep esen ed wi h he ollowing diag am:
Fo ins ance, conside he ollowing chain complexes (C, d)and (C′, d′),
whose chain g oups a e eely gene a ed wi h R=Z:
C0=hσ1, σ2, σ3i, C1=hσ4, σ5, σ6i, C2=hσ7i, C3= 0,···
d1=
−1 0 −1
0−1 1
110
, d2=
−1
1
1
C′
0=hτ1, τ2i, C1=hτ3i, C2= 0,···
d′
1=−1
1, d′
2= 0
Hence (h, , g)is a educ ion, whe e
h0=
0 0 0
0 0 0
−100
, h1=−1 0 0
0=110
001, 1=110
g0=
0 0
1 0
0 1
, g1=
0
1
0
We ha e ollowed Se ge ae ’s e minology. The e a e equi alen o
simila de ini ions in he li e a u e: con ac ion [45, §12], s ong de o ma ion
e ac ion [82, §2], Eilenbe g-Zilbe da a [63, §4] o i ialized ex ension [98, §2].
I we emo e he las line o condi ions, he esul ing ela ion is called
achain homo opy equi alence. I ensu es ha bo h chain complexes ha e iso-
mo phic homology g oups, whe e he isomo phisms a e he induced maps
and gin he homology g oups. Howe e , hese las condi ions p o ide
mo e in o ma ion: hey decompose he chain complex in o wo subcom-
plexes: ke ( )and im(g), whe e he o me is acyclic (i s homology g oups
a e all i ial) and he la e is isomo phic o he educed chain complex
(C′, d′). This can be hough as a homo opical hinning o he complex,
2.3. Compu a ional opology 17
whe e we emo e pa s om he o iginal chain complex wi hou modi ying
i s homology.
A educ ion is pe ec i d′= 0. In such case, H(C)∼
=H(C′) = C′and
hus he homology g oups a e di ec ly ob ained. Mo eo e , g(C′)is a basis
o H(C). Also, le x∈Cqbe a cycle. I i is a bounda y hen
(x) = d(y) = d′ (y) = 0
since d′= 0. Hence,
g (x)
|{z}
0
=x−dh(x)−hd(x) = x−dh(x)⇒x=dh(x)
Tha is, xis a bounda y i and only i (x) = 0 and in ha case x=d(y)
o he chain y=h(x). These ac s should jus i y he in e es o ha ing a
pe ec educ ion.
Le us poin ou ha i he homology g oups o a chain complex ha e a
o sion subg oup hen he e is no pe ec educ ion, since a pe ec educ-
ion in ol es homology g oups eely gene a ed, and hence o he o m Zβ.
Also, a educ ion can always be ob ained ia he Smi h no mal o m com-
pu a ion as desc ibed in [8, p. 48]. This educ ion is pe ec i he homology
g oups a e o sion- ee. O he wise, i s educed bounda y ma ices a e in
he Smi h no mal o m.
I ρ= (h, , g)is a educ ion om (C, d) o (C′, d′), i is easy o p o e ha
ρ∗= (h∗, g∗, ∗)is a educ ion be ween he cochain complexes (C, d∗)and
(C′,(d′)∗). Consequen ly, a pe ec educ ion also p o ides a basis o he
cohomology g oups, namely ∗(C).
2.3.5 Pe sis en homology
Pe sis en homology s udies he global beha io o he homology g oups
o a complex ha changes along ime. Fo mally, we conside a nes ed se-
quence o simplicial complexes.
De ini ion 2.19. A il a ion o a simplicial complex Kis a sequence o subcom-
plexes
∅=K0⊂K1⊂ ··· ⊂ Km=K
I can also be desc ibed by a unc ion :K→[1, m]mapping each cell o he
index o he i s subcomplex con aining i .
No e ha (σ)< (τ) o all σ < τ since a cell mus appea a e i s
aces. We can hus build a il a ion om any unc ion on a complex by
aking he maximum o he images o all he aces o a cell (e en i sel ).
Pe sis en homology o malizes he idea ha , in a il a ion, some holes
las longe (a e mo e pe sis en ) han o he s. The inclusion be ween he
subcomplexes o he il a ion, which induces a chain map be ween hei
chain g oups and a homomo phism be ween hei homology g oups, plays
a cen al ole. Le (Ci, di)be he chain complex associa ed o he subcomplex
Kiand ιi,p :Ci→Ci+p he inclusion om Ki o Ki+p.
18 Chap e 2. Common Backg ound
De ini ion 2.20. The p-pe sis en q- h homology g oup o Kiis
Hi,p
q= ke (di
q)/(im(di+p
q+1)∩ke (di
q)) ∼
=im(ιi,p
q)
In ui i ely, i is he se o cycles in Ki ha emain non-bounding o he
p ollowing s eps. The ank o i s ee subg oup is called he p-pe sis en
q- h Be i numbe o Ki. This de ini ion has h ee pa ame e s: i,pand q. I
we we e able o de ine he bi h and dea h ime o each homology class in
he il a ion, hen we could easily deduce he p-pe sis en Be i numbe s
(see he k- iangle Lemma in [44]). Zomo odian and Ca lsson in oduced
a co espondence in [119] ha associa es each il a ion F o i s pe sis en
diag am, a se o in e als P D(F) = ∪q≥0P Dq(F) = {(i, j)|0≤i≤j≤ ∞}.
Un o una ely, his is only possible i he g ound ing is a ield. A simple
algo i hm is gi en, which amoun s o compu e he Smi h no mal o m by
choosing pi o s in he o de de e mined by he il a ion.
The se PDq(F)can be in e p e ed as poin s in he plane o as in e als
in he line. The poin s o he o m (i, j)wi h j < ∞co espond o q-holes
ha a e bo n in Kiand die in Kj, while he poin s o he o m (i, ∞)con-
o m he q-holes ha a e p esen in Kand appea in Ki. I he il a ion
is desc ibed as a unc ion , we deno e i s pe sis en diag am by PD( ).
Cohen-S eine e al. p o ed in [19] ha PD( )is s able unde small pe u -
ba ions o .
2.4 Digi al Geome y
Adisc e e objec is a ini e subse o Zn. I is also called bina y image (i n= 2)
o bina y olume (i n= 3) in o de o make he di e ence agains a g ay-
scale image o a colo image. I s elemen s a e called pixels when n= 2,
oxels when n= 3 o poin s in gene al.
We endow a disc e e objec wi h a connec i i y ela ion. Le us ecall
some usual connec i i y ela ions. Le be x= (x1, . . . , xn)∈Zn,
||x||1=|x1|+···+|xn|and ||x||∞= max {|x1|,··· ,|xn|}
Thus, i x, y ∈Z2,
•xand ya e 4-connec ed i ||x−y||∞≤1and ||x−y||1≤1
•xand ya e 8-connec ed i ||x−y||∞≤1and ||x−y||1≤2
Also, i x, y ∈Z3,
•xand ya e 6-connec ed i ||x−y||∞≤1and ||x−y||1≤1
•xand ya e 18-connec ed i ||x−y||∞≤1and ||x−y||1≤2
•xand ya e 26-connec ed i ||x−y||∞≤1and ||x−y||1≤3
Wi h his no a ion, he numbe accompanying he “connec ed” wo d
ells he numbe o poin s connec ed o a poin in Zn. No e ha hese de i-
ni ions can be ex ended o any dimension. The e lexi e and ansi i e clo-
su e o his connec i i y ela ion allows us o de ine connec ed componen s
o a disc e e objec .
2.4. Digi al Geome y 19
We can ac ually build cubical complexes om disc e e objec s in o de
o ob ain highe -dimensional opological in o ma ion h ough he homol-
ogy g oups. We in oduce wo kinds o cubical complexes associa ed o a
disc e e objec ega ding he 2n-connec i i y and he (3n−1)-connec i i y.
P imal associa ed cubical complex Le Xbe a disc e e objec , we deno e
by Kp[X]i s p imal associa ed cubical complex. Le us gi e a cons uc i e
de ini ion: o each poin x= (x1,··· , xn)o Xwe add o he cubical com-
plex he n-cube [x1, x1+ 1] ×···×[xn, xn+ 1] oge he wi h i s aces. This
cons uc ion can be ound in [16].
Dual associa ed cubical complex We deno e he dual associa ed cubical
complex by Kd[X]. Le us i s adap he no ion o clique o ou con ex : a
d-clique is a maximal (in he sense o inclusion) se o poin s o Znsuch ha
he in e sec ion o hei co eponding n-cubes is a d-cube. Fi s , o e e y
poin (in ac n-clique) x= (x1,··· , xn)o he disc e e objec , we add he
0-cube σ= [x1, x1]×···× [xn, xn]. Then, o e e y d-clique (d < n) in he
disc e e objec , we add o he cubical complex a (n−d)-cube such ha i s
e ices a e he poin s o he d-clique. This app oach was used in [84].
We can also de ine he dual associa ed cubical complex in a di e en
ashion. Conside K he ull nD cubical complex and, o each poin x=
(x1,··· , xn)no in X, emo e om K he 0-cube σ= [x1, x1]×···×[xn, xn]
and i s co aces. The esul ing cubical complex coincides wi h Kd[X].
Figu e 2.6 illus a es a bina y olume and i s wo associa ed cubical
complexes.
FIGURE 2.6: Le : a bina y olume. Cen e : i s p imal as-
socia ed cubical complex. Righ : i s dual associa ed cubical
complex
3.3. P elimina ies 27
Lemma 3.3. (Schu de e minan o mula) Le be
M=A B
C D
a block ma ix (A∈Mn×n(Z), B ∈Mn×k(Z), C ∈Mk×n(Z)and D∈Mk×k(Z)).
I Ais in e ible hen
de (M) = de (A)·de (D−CA−1B).
Lemma 3.4. (The Banachiewicz iden i y) Le be
M=A B
C D
a block ma ix (A∈Mn×n(Z), B ∈Mn×k(Z), C ∈Mk×n(Z)and D∈Mk×k(Z)).
I Aand D−CA−1Ba e in e ible, hen Mis in e ible and
M−1=A−1+A−1B(D−CA−1B)−1CA−1−A−1B(D−CA−1B)−1
−(D−CA−1B)−1CA−1(D−CA−1B)−1
We ecall ha he anspose o a ma ix Ais deno ed A⊤.
Lemma 3.5. (She man-Mo ison o mula) Le A∈Mn×n(Z)and u, ∈Zn. I
Ais in e ible and 1 + ⊤Au 6= 0 hen
A+u ⊤−1=A−1−A−1u ⊤A−1
1 + ⊤Au .
Lemma 3.6. Le A∈Mm×n(Z), we say ha i is an [ , c]-ma ix i each ow
con ains a mos non-ze o en ies and each column con ains a mos cnon-ze o
en ies. Thus,
•I A∈Mm×n(Z)is an [ , c]-ma ix and B∈Mm×n(Z)is an [ ′, c′]-ma ix,
hen A+Bis an [ + ′, c +c′]-ma ix and i can be compu ed wi hin
O(min(m·( + ′),(c+c′)·n)) ope a ions.
•I A∈Mm×n(Z)is an [ , c]-ma ix and B∈Mn×p(Z)is an [ ′, c′]-
ma ix, hen A·Bis an [ ′, cc′]-ma ix and i can be compu ed wi hin
O(m·min( , c′)·p)ope a ions.
Lemma 3.7. (Ma ix in e sion lemma) Le A∈Mn×n(Z)and u, ∈Zn. I Ais
in e ible hen
de (A+u ⊤) = de (A)·1 + ⊤A−1u.
P oo . We w i e
M=1−
u A
Since de (M) = de (M ), by he Schu de e minan o mula (see Lemma 3.3),
de (M) = de (M )
de (1) ·de (A+u ) = de (A)·de (1 + A−1u)
de (A+u ) = (1 + A−1u)·de (A)
28 Chap e 3. The Homological Disc e e Vec o Field
FIGURE 3.2: Le : an i e a ed Mo se decomposi ion, whe e
he ed a ow belongs o he i s DGVF and he pu ple one,
o he second DGVF. Righ : a (s anda d) DGVF inducing he
same educ ion.
3.4 Mo i a ion
The disc e e Mo se heo y app oach has a s ong in e es as i add esses he
compu a ion o homology as a pu ely combina o ial p oblem a he han
an algeb aic one. The associa ed educ ion can be encoded jus as a lis o
pai s o cells. I also p o ides an app oxima ion o he Be i numbe s ha
can some imes be accu a e (depending on he choice o he in eg al a ows)
bu ha is always w ong o some well known spaces as, o ins ance, he
Bing’s house [6] (also called house wi h wo ooms) o he dunce ha [117].
We can inc ease a DGVF (and hus imp o e he app oxima ion) by can-
celing pai s o c i ical cells: ind wo c i ical cells τ(q+1) and σ(q)connec ed
by only one V-pa h and exchange he in eg al and di e en ial a ows in
his pa h. This can be seen as e e sing he di ec ion o he V-pa h. No e
ha , e en hough his ans o ma ion is exp essed in combina o ial e ms,
compu ing he numbe o V-pa hs is equi alen o compu e he associa ed
educ ion.
Ano he app oach o educing he numbe o c i ical cells is o compu e
he Mo se complex and o es ablish a new DGVF V′on i , which is use ul
when he e is no unique V-pa h be ween he c i ical cells. This is known
as i e a ed Mo se decomposi ion [42]. Rega ding he associa ed educ ion, e-
e sing he only V-pa h be ween wo c i ical cells is equi alen o adding an
in eg al a ow be ween hem in he Mo se complex. Figu e 3.2 illus a es
his.
Thus, e e sing a V-pa h can be seen as pushing an in eg al a ow om
he Mo se complex back o he o iginal one. Howe e , no all he in eg al
a ows on he Mo se complex a e equi alen o e e se a V-pa h: his is he
case when he e a e se e al V-pa hs be ween wo c i ical cells. Figu e 3.3
shows an example whe e he e a e h ee V-pa hs be ween wo c i ical cells.
Howe e , he 1-cell is a ace o he 2-cell in he associa ed Mo se complex,
so we can add an in eg al a ow which does no co espond o a unique
V-pa h. The mo i a ion o ou wo k was o push all he in eg al a ows in
he Mo se complex back o he o iginal one.
The e is a di e en (bu equi alen ) poin o iew which is mo e su p is-
ing. Finding an op imal DGVF, wi h he minimal numbe o c i ical cells, is
an NP p oblem. Canceling pai s o c i ical cells by e e sing V-pa hs could
3.4. Mo i a ion 29
FIGURE 3.3: The same DGVF depic ed in Figu e 3.1. Some
di e en ial a ows a e shown in pu ple.
seem o be a solu ion o his p oblem, bu we canno do i in gene al be-
cause o he condi ions in he de ini ion o a DGVF. Thus, one could hink
o emo ing one o hem:
1. I mus be a ma ching: i he e a e se e al V-pa hs be ween wo c i -
ical cells, we could hink o e e sing all o hem. Bo h c i ical cells
would disappea and no cycles would hus appea . Sadly enough,
his idea does no seem o gi e any homological in o ma ion. We
canno a i m ha his app oach is impossible, since ex a condi ions
could be added, bu we can show a e y discou aging example a Fig-
u e 3.4. On he le , he e is a DGVF wi h 3 V-pa hs be ween he wo
le mos c i ical cells o dimension 1 and 2. I we e e se all o hem,
he e is jus one V-pa h be ween he wo igh mos c i ical cells. I we
cancel hem, we would inish wi h jus one c i ical cell o dimension
0, while he complex has β1=β2= 1.
A mo e de ailed desc ip ion o his example would ake oo much
space, and we only wish o show ha his does no seem a good idea.
2. The e canno be closed V-pa hs: mi aculously, his has been a success-
ul idea. Only by adding one condi ion ha we in oduce in Sec-
ion 3.6, we ob ain a gene aliza ion o he DGVF. The me hods o
cons uc ing such an objec and he equa ions o compu ing i s asso-
cia ed educ ion a e alid o a s anda d DGVF. We call his kind o
DVF a homological disc e e ec o ield (HDVF).
In eg a ing all he in eg al a ows in he Hasse diag am o he o iginal
complex is no a simple challenge. None heless, i has al eady been no ed
ha a educ ion om a CW complex can bene i om i s geome ic ealiza-
ion and, in ou opinion, his is he eal ad an age o disc e e Mo se heo y.
Le us poin ou a ew examples suppo ing his a he in o mal a i ma ion:
30 Chap e 3. The Homological Disc e e Vec o Field
(A) (B)
FIGURE 3.4: (a) A DGVF. (b) The esul a e e e sing all
h ee V-pa hs be ween he wo le mos c i ical cells.
•We ha e some a p io i in o ma ion abou he bounda y ma ices o a
simplicial complex: he columns o he ma ix dqha e exac ly qnon-
ze o en ies. Mo eo e , he bounda y ma ix dqo a cubical complex
has 2qnon-ze o en ies in i s columns and less han o equal o 2(n−q)
in i s ows, whe e nis he dimension in which he cubical complex is
embedded.
•In [91, §6] a pa allel me hod o es ablishing a DGVF was in oduced
o cubical complexes. This me hod seems impossible o ex end o
o he kinds o CW complexes, so i is eally based on he geome y
o he complex. In e ms o he educ ion, i can be seen as doing a
pa ial pa allel diagonaliza ion o he bounda y ma ices. Ex ending
his app oach o gene al chain complexes is no a all clea .
•Gi en an n-dimensional cubical complex ( ha is, a cubical complex
embedded in Rn), i is no di icul o se a DGVF such ha he ho-
mology gene a o s o dimension n−1lie on he bounda y o he
complex. We can iden i y he (n−1)-holes o he complex by con-
side ing i s complemen . Choose a (n−1)-cell on he bounda y o he
complex nex o one o hose holes, and add in eg al a ows s a ing
om i s bounda y, co e ing all ha pa o he bounda y. Repea his
s ep o e e y hole and hen cancel he emaining c i ical cells wi hou
modi ying hese in eg al a ows.
This is no easily gene alizable o o he classes o CW complexes.
Such an idea, ha we could name as “modeling” o “shaping” he
homology gene a o s makes no sense when we es ablish a educ ion
om a gene al chain complex.
3.5. In oducing he HDVF 31
3.5 In oducing he HDVF
In he con ex o disc e e Mo se heo y, we always y o se a DGVF wi h
he maximum numbe o in eg al a ows (o equi alen ly, wi h he mini-
mum numbe o c i ical cells) in o de o ob ain he bes possible app oxi-
ma ion o he Be i numbe s. In he language o e ec i e homology heo y,
he induced educ ion g ea ly “ educes” he o iginal chain complex.
Gi en a DGVF, we can imp o e i by inc emen ing he numbe o in-
eg al a ows. I we ind wo c i ical cells σ < τ, such ha inse ing an
in eg al a ow be ween hem does no c ea e a cycle, adding his in eg al
a ow educes by wo he numbe o c i ical cells.
Mo e gene ally, i he e is only one V-pa h be ween one cell σ′belong-
ing o he bounda y o a c i ical cell τand ano he c i ical cell σ, we can
e e se i and add he a ow (σ′, τ). This means ha he in eg al and di -
e en ial a ows in he V-pa h a e exchanged. This can be conside ed as he
gene al me hod o imp o ing a DGVF (ac ually, in he p e ious case, he
V-pa h has leng h ze o so he e is no e e sing). Howe e , depending on
he o de in which we cancel he c i ical cells and on he CW complex i sel ,
we can c ea e se e al V-pa hs be ween he o he pai s o c i ical cells, so
ha we canno cancel hem anymo e. This gi es an in ui ion on why his
op imiza ion p oblem is NP [83].
In o de o a oid his si ua ion, we p opose o allow cycles in he DVF,
p o ided ha we c ea e hem “sma ly”, so a educ ion can s ill be de ined.
We cancel pai s o c i ical cells independen ly o he numbe o V-pa hs, bu
conside ing he in o ma ion gi en by he associa ed educ ion. This means
ha he educ ion mus be known a e e y s ep, bu do no panic: inding a
V-pa h amoun s also o compu e a educ ion.
We ecall ha a DVF induces a pa i ion K=P⊔S⊔Co a CW complex.
De ini ion 3.1. Ahomological disc e e ec o ield (HDVF) X= (P, S)on a
CW complex Kis a pa i ion K=P⊔S⊔Csuch ha d(Sq+1)|Pqis an in e ible
ma ix (in R) o e e y q≥0, whe e Pqand Sqdeno e he es ic ions o Pand S o
he q-cells and d(Sq+1)|Pqis he subma ix o he bounda y ma ix dq+1 consis ing
in he columns associa ed o he seconda y (q+ 1)-cells and he ows associa ed o
he p ima y q-cells.
No e ha he DVF is no explici in he de ini ion o he HDVF. When
Xis a DGVF, he e is a unique DVF inducing i s pa i ion, bu his is no
he case o a HDVF. Fo ins ance, Figu e 3.5 depic s h ee di e en DVFs
inducing he same HDVF, since he p ima y and seconda y cells in each
complex a e he same.
Deducing a DVF equi es o ind a pe ec ma ching in a bipa i e g aph.
The exis ence o his pe ec ma ching, when he pa i ion is a HDVF, ol-
lows om P oposi ion 3.8.
P oposi ion 3.8. Le Kbe a CW complex endowed wi h a HDVF X= (P, S).
Then he e exis s a disc e e ec o ield V ha induces he pa i ion K=P⊔S⊔C.
P oo . In his p oo we do no use he ac ha d(Sq+1)|Pqis in e ible, bu
ha de d(Sq+1)|Pq6= 0.
Le us ix a dimension q. By he Laplace expansion o mula, he e is a
pai o cells (σ, τ)such ha hd(τ), σi 6= 0 and de d(Sq+1 τ)|Pq σ6= 0.
Thus, he disc e e ec o ield Vcan be ound ecu si ely.
32 Chap e 3. The Homological Disc e e Vec o Field
FIGURE 3.5: Th ee di e en ma chings inducing he same
HDVF.
The DVF can be compu ed using he Hopc o -Ka p algo i hm [69] in
O(m√n) ime, whe e nand mdeno e he numbe o e ices and edges in
he Hasse diag am. I is in e es ing as i allows us o isualize he HDVF
and i s compu a ion.
Le us now p esen he educ ion induced by a HDVF. We showed in
Sec ion 3.3.4 a educ ion induced by a DGVF. Since a DGVF has no cycles,
he chain (1 −dV )is nilpo en and hence he sum Pk≥0V(1 −dV )kis well
de ined. This does no hold o he HDVF, and he e o e we mus conside
an app op ia e educ ion.
No e ha all he ope a o s o a educ ion a e linea , so hey can be ep-
esen ed by ma ices. An app op ia e choice o bases can p o ide nice ma-
ices and we ha e ound a e y good one: he basis B=hPq, Sq, Cqi o
e e y chain g oup Cq. In he ollowing we omi he subsc ip s o acili a e
eadabili y.
Theo em 3.9. Le Kbe a CW complex endowed wi h a HDVF X. Then Xinduces
he educ ion (h, , g) : (C, d)⇒(R[C], d′), whe e he ope a o s h, ,gand he
educed bounda y d′a e gi en by
H
0
0
0
0
0
0
00
PS C
P
S
h= =F0
PS
Ig=G
0
P
S
I
d′=D
C
C
C
C
C
C
C
whe e
H= (d(S)|P)−1
F=−d(S)|C·(d(S)|P)−1
G=−(d(S)|P)−1·d(C)|P
D=d(C)|C+F·d(C)|P=d(C)|C+d(S)|C·G
P oo . Le us see ha hese linea ope a o s sa is y he condi ions o a e-
duc ion. By de eloping he ma ix p oduc s by blocks, we can easily check
ha hh = 0, h = 0,hg = 0 and g = 1C. The es o he condi ions p ecise
mo e de ail.
3.5. In oducing he HDVF 33
g = 1C−dh −hd: By de eloping he ma ix p oduc , we ob ain
00 0
GF 0G
F0I
=
I−d(S)|PH0 0
−d(S)|SH−Hd(P)|PI−Hd(S)|P−Hd(C)|P
−d(S)|CH0I
All he equali ies can be deduced di ec ly om he de ini ion o H,Fand
G. The equali y GF =−d(S)|SH−Hd(P)|Pis mo e di icul o see. Le us
call
X=GF +d(S)|SH+Hd(P)|P
=Hd(C)|Pd(S)|CH+d(S)|SH+Hd(P)|P
Then,
d(S)|PXd(S)|P=d(S)|PHd(C)|Pd(S)|CHd(S)|P
+d(S)|Pd(S)|SHd(S)|P+d(S)|PHd(P)|Pd(S)|P
=d(C)|Pd(S)|C+d(S)|Pd(S)|S+d(P)|Pd(S)|P
Then, he eade can check ha d(S)|PXd(S)|P= (dd)(S)|P= 0, so X= 0.
We need now some p ope ies whose p oo is di ec by de eloping he
ma ix p oduc :
d′= dg = d
0
0
I
=00Idg (3.1)
=00I·(1C−dh)(3.2)
g= (1C−hd)·
0
0
I
(3.3)
d′ = d. Using (3.1) and (3.2),
d′ =0 0 Idg
=0 0 Id(1C−dh −hd)
=00I(1C−dh)d= d
34 Chap e 3. The Homological Disc e e Vec o Field
gd′=dg. Symme ically,
gd′=g d
0
0
I
= (1C−dh −hd)d
0
0
I
=d(1C−hd)
0
0
I
=dg
d′d′= 0. Using (3.2) and (3.3),
d′d′= ( dg)( dg) = dg(d′ )g= (dd)g g = 0
We say ha a HDVF is pe ec i i s associa ed educ ion is pe ec .
The p e ious heo em allows us o p o e he desi ed p ope y ha he
numbe o c i ical cells app oxima es he Be i numbe s also in he HDVF.
Theo em 3.10. Le Kbe a CW complex endowed wi h a HDVF X. Then, o
e e y q≥0, he numbe o q-c i ical cells is g ea e han i s q- h Be i numbe .
P oo . A HDVF induces a educ ion o a chain complex C′wi h isomo phic
homology g oups, whose ank in each dimension qis he numbe o c i ical
q-cells. This p o es he heo em.
Le us poin ou ha his educ ion is no di ec ly a gene aliza ion o
he educ ion in oduced in [91]. Though, i has a simila o m i we con-
side he educ ion ρ′= (h′, ′, g′) = (h, 1−dh −hd, ι)be ween (C, d)and
( ′(C), d).
Using he same language as disc e e Mo se heo y, his class ex ending
he DGVF allows us o ind he co ec numbe o c i ical cells in complexes
which do no admi a pe ec DGVF, such as he Bing’s house o he dunce
ha [3]. Ins ead o p o iding he explici (and eno mous) desc ip ion o each
complex and i s HDVF, we p e e o show illus a ions and o commen he
cons uc ion o hose HDVFs.
The cubical complex e sion o he Bing’s house has been c ea ed by
he au ho s. I con ains 60 0-cubes, 129 1-cubes and 70 2-cubes. The i s
DGVF de ined on i con ains 13 c i ical cubes (see Figu e 3.6-(a)): 1 0-cube,
6 1-cubes and 6 2-cubes. Le us commen ha i is no he bes DGVF pos-
sible. S a ing om his DGVF, and a e canceling pai s o c i ical cells by
e e sing V-pa hs, i emains only 1 c i ical 0-cube, which co esponds o
he Be i numbe s o he complex. Ob iously, hese V-pa hs we e chosen o
p ese e he HDVF s uc u e. Consequen ly, he Mo se g aph con ains wo
cycles.
Fo he dunce ha we used a simplicial complex om [64] consis ing
o 8 0-simplices, 24 1-simplices and 17 2-simplices. We can se a DGVF
3.6. Compu ing a HDVF 35
(A) (B)
FIGURE 3.6: (a) A DGVF o e he Bing’s house. (b) A pe -
ec HDVF ob ained on he Bing’s house. The e is only one
c i ical 0-cell (in blue).
con aining 3 c i ical cells (see Figu e 3.7-(a)): one o each dimension. A e
e e sing one V-pa h be ween he c i ical cells o dimension 1 and 2, we
ob ain a HDVF wi h only 1 c i ical 0-cell, which is in acco dance wi h he
Be i numbe s o he complex. The wo cycles c ea ed in he homological
DVF a e shown in g een.
(A) (B)
FIGURE 3.7: (a) A DGVF o e he dunce ha wi h h ee c i -
ical cells in blue. (b) The HDVF ob ained a e imp o ing
he DGVF. The only c i ical cell is he 0-cell deno ed by 1.
The wo cycles in he Mo se g aph a e displayed in g een.
3.6 Compu ing a HDVF
We explain in his sec ion how we can compu e a HDVF and i s educ ion
e icien ly. We do i in e ms o he pa i ion K=P⊔S⊔Cins ead o he
DVF V, bu we b ie ly desc ibe how o ob ain he DVF.
3.6.1 Compu ing he Reduced Complex
Ou i s p oposi ion s a es when we can add a pai o cells o a HDVF so
ha he ma ix d(S)|Pis s ill in e ible.
36 Chap e 3. The Homological Disc e e Vec o Field
P oposi ion 3.11. Le Kbe a CW complex endowed wi h a HDVF X= (P, S).
Le σ(q)and τ(q+1) be wo c i ical cells. I hd′(τ), σiis a uni hen X′= (P∪
{σ}, S ∪{τ})is a HDVF.
P oo . We only need o p o e ha he ma ix d(S′)|P′is in e ible, whe e
S′=S∪{τ}and P′=P∪{σ}. This ma ix has he o m
d(S′)|P′=d(S)|P
Sτ
P
σwu
whe e u=d(S)|σ, =d(τ)|Pand w=d(τ)|σ.
We know ha d(S)|Pis in e ible. Le us p o e ha w−u(d(S)|P)−1 is
also in e ible. By hypo hesis, hd′(τ), σi=±1. Since
D=d(C)|C−d(S)|C·(d(S)|P)−1·d(C)|P
hen, by Lemma 3.1 (wi hou speci ying he indices),
hd′(τ), σi=d(τ)|σ−d(S)|σ·(d(S)|P)−1·d(τ)|P
=w−u·(d(S)|P)−1·
Consequen ly, by he Schu de e minan o mula (c. . Lemma 3.3),
de (d(S′)|P′) = de (d(S′)|P′)·de (w−u(d(S)|P)−1 )
is a uni , so d(S)|Pis in e ible.
Once we ha e added wo c i ical cells o a HDVF, we do no need o
comu e a new DVF inducing he expanded HDVF. Ins ead o his, we can
deduce he co esponding DVF by in e ing one o he V-pa hs connec ing
bo h c i ical cells. The ollowing p oposi ion p o es ha such V-pa h exis s.
P oposi ion 3.12. Le Kbe a CW complex endowed wi h a HDVF X. Le σ(q)
and τ(q+1) be wo c i ical cells. I hd′(τ), σiis a uni hen he e is a V-pa h be ween
hem.
P oo . Le Vdeno e he ma ix associa ed wi h he DVF in oduced in Sec-
ion 3.3.4. Thus,
d′(C) = d(C)|C−d(S)|C·(d(S)|P)−1·d(C)|P
=d(C)|C−d(S)|C·V(P)|S·(V(P)|S)−1·(d(S)|P)−1·d(C)|P
=d(C)|C−dV (P)|C·(dV (P)|P)−1·d(C)|P
Hence hd′(τ), σi=d′(τ)|σ=−dV (P)|σ·(dV (P)|P)−1·d(τ)|P+d(τ)|σ. I σ < τ
hen i is ob ious. O he wise, hd′(τ), σi=−dV (P)|σ·(dV (P)|P)−1·d(τ)|P.
3.7. De o ming a HDVF 43
second ques ion has a posi i e answe , hen Algo i hm 1can ind a pe ec
HDVF, hough i may no ind i always.
We ha e al eady seen ha a CW complex whose homology g oups ha e
o sion coe icien s does no admi a pe ec HDVF. In addi ion, as a con-
sequence o P oposi ion 3.17, e e y CW complex admi s a pe ec HDVF
whene e Ris a ield. Ne e heless, we igno e wha happens when R=Z
and he homology g oups a e o sion- ee. In o de o ind a coun e exam-
ple, we execu ed Algo i hm 1 o all he o sion- ee simplicial complexes
in Benede i and Lu z’s lib a y o iangula ions [4] and we always ound
a pe ec HDVF. Mo eo e , he HDVFs e u ned o he simplicial com-
plexes wi h jus one o sion coe icien pe dimension (i.e., Hom_C5_K4,
RP4,RP4#K3_17,RP4#11S2xS2 and RP5_24) had hei educed bound-
a y ma ix al eady in SNF. Hence, e en i hey a e no pe ec HDVFs, he
homology g oups can be di ec ly ead om hem.
We poin ou ha he simplicial complex hype bolic_dodecahe-
d al_space p esen ed an in e es ing beha io . I s 1-dimensional homol-
ogy g oup is H1= (Z5)3. Due o i s small size (718 simplices), we ex-
ecu ed Algo i hm 1500 000 imes wi h andom choices o pai s o cells
and we only ound 72 HDVFs whose educed bounda y ma ices we e in
SNF. The o he simplicial complex wi h mo e han one o sion coe icien ,
PG128_PG128P7, is much la ge (13 462 simplices) and we s ill ha e no
ound any HDVF whose educed bounda y ma ix is in SNF.
3.6.4 Ano he algo i hm o compu ing a HDVF
Algo i hm 1consis s in i e a i ely adding a pai o c i ical cells o he HDVF.
Ne e heless, we can also add se e al pai s o cells o a HDVF a he same
ime.
Le Xbe a HDVF and Σ = {σ1, . . . , σ }and T={τ1, . . . , τ }be wo
se s o c i ical cells o codimension 1 ( ha is, dim(σi) = dim(τi)−1). I he
ma ix d′(T)|Σis in e ible in R hen X′= (P∪Σ, S ∪T)is a HDVF. The
p oo is simila o ha o P oposi ion 3.11.
As a consequence, Algo i hm 1is no he unique way o compu ing a
HDVF. Howe e , we p e e i o i s simplici y and we do no s udy in his
wo k he abo e al e na i e app oach.
Le us poin ou ha , i we can add se e al pai s o cells a he same
ime, hen he second ques ion o he p e ious sec ion is ue since we can
add all he pai s o cells in a HDVF a once.
3.7 De o ming a HDVF
In Sec ion 3.6 we desc ibed how he educ ion changes a e adding a pai o
c i ical cells o he HDVF. This can be seen as a basic ope a ion on a HDVF,
in which wo c i ical cells γand γ′a e ans o med in o a p ima y and a
seconda y cell espec i ely. In his sec ion we ex end his idea o de ine i e
basic ope a ions ha allow us o modi y a HDVF.
3.7.1 Basic Ope a ions
Le Kbe a CW complex endowed wi h a HDVF X= (P, S). Le σ∈P,
τ∈Sand γ, γ′∈C. Thus,
44 Chap e 3. The Homological Disc e e Vec o Field
•X′=A(X, γ, γ′) = (P∪{γ}, S ∪{γ′})is a HDVF iden ical o Xex-
cep o γ, which is a p ima y cell, and γ′, which is a seconda y cell
•X′=R(X, σ, τ) = (P {σ}, S {τ})is a HDVF iden ical o Xexcep
o σand τ, which a e c i ical cells
•X′=M(X, σ, γ) = ((P {σ})∪{γ}, S)is a HDVF iden ical o Xex-
cep o σ, which is a c i ical cell, and γ, which is a p ima y cell
•X′=W(X, τ, γ) = (P, (S {τ})∪{γ})is a HDVF iden ical o Xexcep
o τ, which is a c i ical cell, and γ, which is a seconda y cell
•X′=MW(X, σ, τ) = ((P {σ})∪{τ},(S {τ})∪{σ})is a HDVF iden-
ical o Xexcep o τ, which is a p ima y cell, and σ, which is a sec-
onda y cell
The ope a ion Ahas been la gely explained in Sec ion 3.6 and Rconsis s
in emo ing a pai o cells om he HDVF. Mexchanges a p ima y cell wi h
a c i ical one, while Wexchanges a seconda y cell wi h a c i ical one. MW is
like combining Mand Wexcep ha no c i ical cell is needed.
Le us see he condi ions unde which we can pe o m each ope a ion.
P oposi ion 3.19. Le Kbe a CW complex endowed wi h a HDVF X. Le σ∈P,
τ∈Sand γ, γ′∈C. Thus,
1. A(X, γ, γ′)is a HDVF i hd′(γ′), γiis a uni
2. R(X, σ, τ)is a HDVF i hh(σ), τiis a uni
3. M(X, σ, γ)is a HDVF i h (σ), γiis a uni
4. W(X, τ, γ)is a HDVF i hg(γ), τiis a uni
5. MW(X, σ, τ)is a HDVF i hdh(σ), τiand hhd(τ), σia e uni s
P oo . The i s s a emen only eph ases P oposi ion 3.11.
Fo he second s a emen we need o p o e ha dq(S′
q+1)|P′
qis in e ible
a e emo ing he wo cells. In he ollowing we omi he subsc ip s. We
w i e
d(S)|P=AB
C d(S′)|P′, M =10
C d(S′)|P′
whe e A=d(τ)|σ,B=d(S′)|σand C=d(τ)|P′. No e ha de (M) =
de d(S′)|P′. Then
de d(S′)|P′= de (M)
= de d(S)|P+1−A−B
0 0
= de d(S)|P+1
0·1−A−B
= de d(S)|P·1 + 1−A−B·H·1
0 (c . Lemma 3.7)
= de d(S)|P·1 + 10·H·1
0−AB·H·1
0
= de d(S)|P·(1 + H11 −1) = de d(S)|P·H11
3.7. De o ming a HDVF 45
whe e H11 deno es h(σ)|τ=hh(σ), τi.
The hi d s a emen is also p o ed using Lemma 3.7. We w i e
dq(S)|P=a
M, dq(S)|P′=b
M
whe e a=d(S)|σand b=d(S)|γ. We no e ha
F=−b
N·H
whe e N=d(S)|C γand hus
h (σ), γi=−b·h
whe e h=h(σ)|S. Then
de dq(S)|P′= de dq(S)|P+1
0·(b−a)
= de dq(S)|P′·1 + (b−a)·H·1
0
= de dq(S)|P′·(1 + (b−a)·h)
= de dq(S)|P′·(1 + b·h−a·h)
= de dq(S)|P′·(1 −h (σ), γi−1)
=−de dq(S)|P′·h (σ), γi
dq(S)|P′is hus in e ible.
We omi he p oo o he las wo s a emen s since hey a e simila o he
hi d one.
All hese ope a ions can be applied in e ms o he DVF by e e sing a
V-pa h be ween he wo cells conside ed. This V-pa h is no unique, bu
i s exis ence can be p o ed using he same a gumen p esen in P oposi-
ion 3.12. In he case o MW, he e a e wo V-pa hs o e e se. Figu e 3.8
illus a es he ope a ions M,Wand MW on a cubical complex.
Some o hese ope a ions we e in oduced in [91]. Namely, he a ow
e e sing is he ope a ion Mbe ween 0-cells, he edge o a ion is MW be ween
1-cells and he ace o a ion is MW be ween 2-cells. These h ee ope a ions
we e announced as local de o ma ions o a DGVF bu , since no condi ion
was gi en, his is in gene al alse: applying an edge o a ion o a ace o a ion
o a DGVF can p oduce a non-g adien disc e e ec o ield. Only he a ow
e e sing p ese ed he s uc u e o DGVF since, in dimension 0, he exis-
ence o a V-pa h be ween a p ima y cell σand a c i ical cell γimplies ha
h (σ), γiis a uni .
46 Chap e 3. The Homological Disc e e Vec o Field
M
WMW
FIGURE 3.8: A HDVF on a cubical complex and he esul
a e applying M,Wand MW. Blue cells a e hose which a e
exchanged.
3.7.2 Delinea ing (co)homology gene a o s
Gi en a pe ec HDVF, he ope a ions M,Wand MW a e in e es ing since hey
change he educ ion and hus he gene a o s o he homology and he co-
homology g oups. The nex p oposi ion speci ies how a gene a o changes
when he ope a ions Mo Wa ec i s associa ed c i ical cell.
P oposi ion 3.20. Le Kbe a CW complex endowed wi h a pe ec HDVF X=
(P, S)wi h R=Z2. Le σ∈P,τ∈Sand γ∈C. Then,
1. I h (σ), γiis a uni , he cohomology gene a o s associa ed o γin Xand σ
in M(X, σ, γ)a e he same.
2. I hg(γ), τiis a uni , he homology gene a o s associa ed o γin Xand τin
W(X, σ, γ)a e he same.
P oo . The p oo o hese s a emen s is qui e leng hy, bu i p o ides a pa -
ial desc ip ion o he educ ion a e pe u bing he HDVF.
Fo he i s s a emen we w i e
Hq=u
A−1
=: H1H2
Fq=−
B·Hq=− H1 H2
BH1BH2=: F11 F12
F21 F22
whe e u=d(S)|σ,A=d(S)|P σ, =d(S)|τand B=d(S)|C γ
3.7. De o ming a HDVF 47
Then,
H′=d(S)|P′−1
=d(S)P+1
0·( −u)−1
(c . Lemma 3.5)
=H+F−1
11 H·1
0·( −u)·H
=H·I−F−1
11 F11 F12
0 0 −F−1
11 10
0 0
=H·−F−1
11 −F−1
11 F12
0I
=−H1F−1
11 H2−H1F−1
11 F12
Consequen ly,
F′=−u
B·−H1F−1
11 H2−H1F−1
11 F12
=F−1
11 F−1
11 F12
F21F−1
11 F22 −F21F−1
11 F12
The p oo o he second s a emen is simila . We w i e
Hq=uA−1=: H1
H2
Gq+1 =−Hq· B=−H1 H1B
H2 H2B=: G11 G12
G21 G22
whe e u=d(τ)|P,A=d(S τ)|P, =d(γ)|Pand B=d(C γ)|P. Then i is
easy o p o e ha
H′=−G−1
11 H1
H2−G−1
11 G21H1
G′=G−1
11 G−1
11 G12
G−1
11 G21 G22 −G−1
11 G21G12
We can hus use hese ope a ions o change he shape o he gene a o s.
Figu e 3.9 shows a cubical complex endowed wi h a HDVF. We wan o
ha e a one-dimensional homology gene a o a ound he hole. Fo doing
his, i su ices ha all he 1-cells a e seconda y excep o one which is c i -
ical. Thus, we use Mon he op 1-cell o pu he e he c i ical cell. Then, o
he o he h ee 1-cells, we use MW o make hem seconda y. A he end, he
homology gene a o induced by he HDVF s ands a he desi ed loca ion.
I is unclea whe he his applica ion is compu a ionally easible. The
p oblem is: gi en a pe ec HDVF Xand a se o cycles S, can we ind a
pe ec HDVF X′whose homology gene a o s con ain his se ? We may
48 Chap e 3. The Homological Disc e e Vec o Field
FIGURE 3.9: Example o mul iple applica ions o he ope -
a ions on a cubical complex. Blue cells a e hose ha ha e
changed. The one-dimensional homology gene a o is de-
pic ed in g een a he beginning and a he end.
i s check ha he cycles a e linea ly independen . This can be done by
compu ing he ank o he ma ix (S). I he ank is maximal, hen he
cycles can be pa o a homology basis. Bu e en i he cycles a e linea ly in-
dependen , he HDVF X′does no exis in gene al, and Figu e 3.10 p o ides
a coun e example. Thus, his p oblem mus be s udied u he in o de o
ind condi ions unde which such HDVF exis s. A possible hin o ollow is
ha e e y cycle mus ha e a cell no included in any o he cycle, which is
he in ui ion ha led o ou coun e example.
Assuming ha he HDVF X′exis s, i is possible o ind a sequence
o ope a ions ha ans o m one HDVF in o he o he : i su ices o suc-
cessi ely apply R o X o emo ing all he pai ing in he DVF, and hen
build he o he HDVF using A( his is gua an eed i Ris a ield by P opo-
si ion 3.18). Thus, he in e es ing ques ion is o ind a minimal sequence o
ope a ions ha ans o m Xin o X′.
3.8. Rela ion wi h o he Me hods in Compu a ional Homology 49
FIGURE 3.10: The e exis s no HDVF on his simplicial com-
plex whose homology gene a o s a e he ou iangles con-
sis ing o h ee 1-simplices.
3.7.3 Connec i i y be ween HDVFs
The new de ini ions le us s a e ha Algo i hm 1can compu e any HDVF
which is he esul o applying only he ope a ion A o an emp y HDVF. We
explained in Sec ion 3.6.3 ha we igno e i e e y HDVF on a simplicial o
cubical complex can be ound h ough Algo i hm 1. Thus i is na u al o
wonde i any HDVF on a simplicial o cubical complex can be ob ained by
a sequence o ope a ions (no only A) on an emp y HDVF. This can also be
o mula ed as ollows: a e all he HDVF on a simplicial o cubical complex
connec ed ia a sequence o ope a ions? This is s ill an open ques ion.
3.8 Rela ion wi h o he Me hods in Compu a ional Ho-
mology
The e a e se e al me hods o compu ing homology in he li e a u e which
seem o be equi alen . The simple o mula ion o he HDVFs allows us o
clea ly see hese equi alences.
3.8.1 I e a ed Mo se decomposi ion
Fi s , le us p o e ha he HDVF gene alizes he no ion o DGVF.
P oposi ion 3.21. E e y DGVF is a HDVF.
P oo . We need o p o e ha he ma ices d(Sq+1)|Pqa e in e ible o each
q≥0. In he ollowing we omi he subsc ip s since he p oo is he same
o e e y dimension q.
Le V={(σi, τi)}m
i=1 be a DGVF. Conside he weigh ed dig aph whose
e ices a e he p ima y cells and whe e a ows connec wo e ices when-
e e he e is a V-pa h o leng h 1 be ween hem. Fo mally, (σi, σj)is an
a ow i hd(τi), σji 6= 0 and σi6=σj. I s weigh is he alue −hd(τi), σii ·
hd(τi), σji. I is immedia e o see ha he ma ix associa ed o his g aph
is I−d(S)|PV, whe e S={τi}m
i=1,P={σi}m
i=1 and he diagonal ma ix
V= ( i,j)is such ha o e e y i, i,i =hd(τi), σiiand ze o elsewhe e.
No e ha Vis in e ible. Since he e a e no closed V-pa hs in he DGVF,
he ma ix I−d(S)|PVis nilpo en , and hus d(S)|PVis in e ible. As Vis
in e ible, we deduce ha d(S)|Pis in e ible.
A DGVF is a limi ed ool o compu ing homology. A mo e elabo a e
ool is he i e a ed Mo se decomposi ion [42], which consis s in i e a i ely:
50 Chap e 3. The Homological Disc e e Vec o Field
(1) compu ing a DGVF and (2) conside ing he esul ing Mo se complex o
a nex DGVF. We p o e now ha e e y i e a ed Mo se decomposi ion is
also a HDVF.
P oposi ion 3.22. E e y i e a ed Mo se decomposi ion is a HDVF.
P oo . Fo cla i y, we assume ha he i e a ed Mo se decomposi ion con-
sis s o only wo DGVFs V1and V2. We ecall ha he second DGVF is
de ined on he chain complex consis ing o he c i ical cells o V1and he
bounda y ope a o
d′=d(C1)|C1−d(S1)|C1·H·d(C1)|P1.
I we w i e
d(S1∪S2)|P1∪P2=AB
C D
hen
d(S1)|P1=Aand d′(S2)|P2=D−CA−1B
Gi en he p e ious p oposi ion, hese wo ma ices a e in e ible. Thus, by
Lemma 3.3,
de d(S1∪S2)|P1∪P2= de d(S1)|P1·de d′(S2)|P2
which is a uni .
I is easy o see ha i a HDVF has been c ea ed using Algo i hm 1, hen
he lis o pai s o cells [(σi, τi)]m
i=1 is an i e a ed Mo se decomposi ion. As
we showed in Sec ion 3.6, i is no ue in gene al ha e e y HDVF can be
compu ed wi h Algo i hm 1, so we canno deduce ha e e y HDVF is an
i e a ed Mo se decomposi ion. Howe e , his does no mean ha i is alse.
This ques ion emains open.
3.8.2 The Smi h no mal o m
The classic algo i hm o compu ing homology g oups compu es he Smi h
no mal o m (SNF) [99]. We p o e in his sec ion ha he educed bound-
a y ma ices ob ained in Algo i hm 1a e simila o he diagonaliza ion pe -
o med o he compu a ion o he SNF.
Le Kbe a CW complex and Xa i ial HDVF (P=S=∅). Le us
choose some pi o in some bounda y ma ix Dq. Fo simplici y, we assume
ha he pi o is he elemen Dq(1,1) = hdq(τ), σiand we omi he subsc ip .
In o de o make all he o he en ies in i s ow and column in o ze os we
pe o m
∀j6= 1, D(·, j)←D(·, j)−D(1, j)D(1,1)−1D(·,1)
∀i6= 1, D(i, ·)←D(i, ·)−D(i, 1)D(1,1)−1D(i, ·)
3.9. Expe imen al Complexi y 51
Using he no a ion o P oposi ion 3.13, his is equi alen o
D′=D−D11
D21 D−1
11 0D12
D′′ =D′−0
D′
21 D−1
11 D′
11 D′
12
By de eloping bo h equa ions we ob ain ha he pseudo-diagonalized bound-
a y ma ix is D11 0
0D22 −D21D−1
11 D12 ,
whe e he bo om- igh block is he educed bounda y compu ed in Algo-
i hm 1a e inse ing he pai o cells (σ, τ).
P oposi ion 3.23. Le Kbe a CW complex. Then, Algo i hm 1pe o ms a pa ial
diagonaliza ion o he bounda y ma ices o K.
P oo . The p oo is di ec om he p e ious a gumen .
We ha e jus seen ha compu ing a HDVF is equi alen o compu e he
SNF o he bounda y ma ices using only he pi o ope a ion, ha is, gi en
an in e ible en y in he ma ix, we make all he en ies in i s ow and col-
umn in o ze os. Compu ing he SNF needs also ano he ype o ope a ion:
i he e is no en y di iding all he o he s, we make elemen a y ope a ions
on he ows and columns so such an en y appea s. Fo his eason, Algo-
i hm 1canno always e u n a pe ec HDVF i R=Z, since in he com-
pu a ion o he SNF we can a i e o a ma ix wi hou uni s e en i he SNF
con ains only uni s in i s diagonal (see Sec ion 3.6.3 o an example).
3.8.3 Pe sis en homology
P oposi ion 3.23 also implies ha pe sis en homology can be compu ed
wi h a a ia ion o Algo i hm 1. The classical algo i hm o pe sis en ho-
mology [119] is based on he Smi h no mal o m. The main di e ence wi h
a s anda d homology compu a ion is ha cells a e conside ed in he o de
gi en by he il a ion. The e o e, Algo i hm 2compu es he pe sis ence
in e als o a il a ion using he same calcula ions as Algo i hm 1.
Algo i hm 2is a me e ansla ion o he algo i hm desc ibed in [119]
in o he HDVF amewo k. The pu pose o doing so is o show ha we can
ob ain a educ ion o e e y s ep o he il a ion and ha we can apply he
conclusions o Sec ion 3.9 o he pe sis en homology heo y.
3.9 Expe imen al Complexi y
We ix in his sec ion R=Z2, so we a e su e ha we ob ain a pe ec HDVF
and hus we compu e he homology o he CW complex.
Compu ing he homology g oups o a CW complex is conside ed in gen-
e al a p oblem wi h O(n3) ime complexi y. Only [88] p o es ha i can be
compu ed in ma ix mul iplica ion ime, bu he e is no implemen a ion o
52 Chap e 3. The Homological Disc e e Vec o Field
Algo i hm 2: Compu e a HDVF associa ed o a il a ion
Inpu : A CW complex Kand a il a ion F=σjn
j=1
Ou pu : The pe sis ence in e als o F
o k= 0 o dim(K)do
Lk← ∅;
X←(∅,∅);
o j= 1 o ndo
i d′(σj)6= 0 hen
i←max nj′:hd′(σj), σj′i= 1o;
X←A(X, σi, σj)(and upda e he bounda y ma ices D);
Ldim(σj)←Ldim(σj)∪(deg σi,deg σj);
o j= 0 o ndo
i σjis c i ical hen
Ldim(σj)←Ldim(σj)∪(deg σj,∞);
his algo i hm. Ne e heless, i has been no iced ha in p ac ice he execu-
ion ime is linea o homology [39, §4] and pe sis en homology [119, §4].
We es ima ed in Theo em 3.15 he complexi y o ou algo i hm by bound-
ing he numbe on non-ze o en ies in ows and columns by n, ob aining
ha Algo i hm 1can ind a HDVF wi hin (n/2) ·n2=n3/2ope a ions o
(n/2) ·n2+n2+n2+n2= 2n3i we also wan o ob ain he associa ed
educ ion. Since hese bounds a e no igh , i should no be su p ising ha
he complexi y in p ac ice is lowe han cubic.
One ad an age o he HDVF amewo k is ha we can easily coun he
numbe o ope a ions ha we pe o m along i s compu a ion. A each s ep
o Algo i hm 1, upda ing he ma ices H, F, G and D equi es |F11||G11|,
|D21||F11|,|G11||D12|and |D21||D12|ope a ions espec i ely, whe e | |de-
no es he numbe o non-ze o en ies in he ec o . Thus, upda ing he
educed bounda y equi es
|D21||D12|
ope a ions (plus some ope a ions o emo e ows and columns). Mo eo e ,
upda ing all he educ ion equi es
|F11||G11|+|D21||F11|+|G11||D12|+|D21||D12|= (|F11|+|D12|)(|G11|+|D21|)
ope a ions.
Le us s udy now he a e age complexi y o wo andom models.
Random cubical complexes We in oduce a andom model o cons uc -
ing cubical complexes. We deno e i by K(p, m)and i is simila o he closed
aces model in oduced in [116]. Le m∈Z+and p∈R,0≤p≤1. A cubical
complex in K(p, m)is buil by adding each cubical cell σ∈[0, m]3(wi h i s
aces) o he complex wi h p obabili y p. No e ha each cell σbelongs o he
cubical complex wi h p obabili y 1−(1 −p)c, whe e cdeno es he numbe
o co aces (in he ull cubical complex [0, m]3) o σ, including i sel . Thus,
lowe -dimensional cells a e mo e equen .
59
Chap e 4
Fas Compu a ion o Be i
Numbe s on
Th ee-Dimensional Cubical
Complexes
THIS chap e is based on he con e ence pape [61], which was co-w i en
wi h Ma eusz Juda. We explain how o e icien ly compu e (only) he
Be i numbe s o a 3D cubical complex wi hou manipula ing any bounda y
ma ix.
4.1 In oduc ion
Compu ing homology usually needs algeb aic me hods. I seems ha hey
all a e based on he Smi h no mal o m as shown in Sec ion 3.8. Howe e ,
he e a e Be i numbe s ha a e easie han o he s.
Conside a simple shape in he eal plane R2. I is well known ha β0
is he numbe o connec ed componen s and β1is he numbe o bounded
connec ed componen s o he complemen .
Thus, i we can coun he connec ed componen s and de ec which ones
a e bounded, we can ob ain bo h Be i numbe s wi hou eso ing any alge-
b aic me hod. Le us men ion wo simple scena ios whe e his is possible:
1. A subcomplex o a simplicial complex iangula ing a ec angle. We can
compu e he numbe o connec ed componen s wi h he usual algo-
i hm on he connec i i y g aph o he subcomplex and i s comple-
men . The unbounded connec ed componen s o he complemen
co espond o hose connec ed componen s which con ain a simplex
om he bounda y o he ec angle.
Figu e 4.1 illus a es his. Two simplicial complex K⊂La e shown in
Figu e 4.1a, while he connec i i y g aphs o Kand L−Ka e depic ed
in Figu e 4.1b. No e ha L−Kis no a simplicial complex since some
simplices in L−Kdo no ha e hei aces in L−K. The e a e wo
connec ed componen s in he connec i i y g aph o K(in ed), so β0=
2. On he o he hand, he e a e ou connec ed componen s in he
connec i i y g aph o L−K(in g een), one o hem con aining all he
simplices in he bounda y o he squa e, so β1= 4 −1.
60 Chap e 4. Fas Comp. o Be i Numbe s on 3D Cubical Complexes
(A) (B)
FIGURE 4.1: Le : a simplicial complex L(in g ay) and a
subcomplex K(in blue). Righ : he connec i i y g aphs o
Kand L−K.
2. A 2D cubical complex. This case is pa icula ly simple because a cubi-
cal complex is always a subcomplex o a bigge cubical complex. The
same ideas apply o his se ing.
We now ocus only on he second scena io, since he i s one is e y
es ic i e.
Can we adap his idea o he h ee-dimensional space? Le Kbe a 3D
cubical complex. Then β0is s ill he numbe o connec ed componen s, bu
now β2is he numbe o bounded connec ed componen s o he comple-
men . Alexande duali y gene alizes his ac o any dimension and any
Be i numbe :
Theo em 4.1 (Alexande duali y).Le Kbe an nD cubical complex. Then
Hq(K)and Hn−1−q(Sn−K)a e isomo phic o educed homology and coho-
mology.
This is why homology s a s being in e es ing s a ing om h ee di-
mensions. The i s homology g oup H1desc ibes he handles and unnels
o an objec , which canno be easily deduced as connec ed componen s o
oids. Ne e heless, since β0and β2a e easy o compu e, we can compu e
β1 ia he simples opological in a ian : he Eule -Poinca é cha ac e is ic.
The Eule -Poinca é cha ac e is ic o a 3D cubical complex Kis he al e na ing
sum o i s cubes. Fo mally,
χ(K) = k0−k1+k2−k3,
whe e kqdeno es he numbe o cubes o dimension qin K.
Theo em 4.2 (Eule -Poinca é o mula).Le Kbe a 3D cubical complex. Then
χ(K) = β0(K)−β1(K) + β2(K).
The e o e, β1(K) = β0(K) + β2(K)−χ(K).
4.2. The I e a i e Algo i hm 61
Consequen ly, we can ob ain he Be i numbe s o a 3D cubical complex
only by coun ing connec ed componen s and compu ing he Eule -Poinca é
cha ac e is ic.
Del inado and Edelsb unne in oduced in [29] an algo i hm wi h al-
mos linea ime complexi y ha compu es he Be i numbe s o a il e ed
simplicial complex which is a subcomplex o a iangula ion o S3. They
also ske ched he cases whe e no il a ion is gi en o whe e he simplicial
complex is embedded jus in R3. This las algo i hm was de eloped u -
he by Dey and Guha in [32]. I s dis inc i e ea u e is ha β2is ound by
ecognizing closed su aces on he bounda y o he complex using a g aph
app oach, so he simplicial complex does no need o be a subcomplex o a
iangula ion o S3. The algo i hm is i s de ined o h ee-mani olds, and
i he simplicial complex is no a h ee-mani old, a echnique o con e ing
i is desc ibed. Sadly, he e is no a ailable implemen a ion o his b illian
algo i hm. Ou wo k sha es se e al ideas wi h hese a icles, hough we
ocus ou esea ch on cubical complexes and exploi hei s uc u e, which
p o ides a simple algo i hm. Juda and M ozek p esen ed in [75] an op i-
mal algo i hm which compu es Z2Be i numbe s and homology gene a o s
o a special class o pseudomani olds. This is an ex ension o Del inado
and Edelsb unne ’s wo k o cubical and simplicial complexes. Ou wo k
sha es se e al ideas wi h hese a icles, hough we ocus ou esea ch on
cubical complexes and exploi hei s uc u e, which p o ides a simple al-
go i hm.
4.2 The I e a i e Algo i hm
In he ollowing, Kdeno es a 3D cubical complex.
We i s p o e ha β0(K)can be compu ed by coun ing connec ed com-
ponen s. This is a well known ac , bu we include his p oo o in oduce
his kind o easoning which we also use in P oposi ion 4.5.
P oposi ion 4.3. Le Kbe a 3D cubical complex and G0(K) = (V, E)deno e he
g aph such ha
•V=K0, he 0-cells o K
•E={{u, } | uand ha e a common co ace}.
Thus, β0(K)is he numbe o connec ed componen s in he g aph G0(K).
P oo . Obse e ha Eco esponds o he 1-cells o K, which connec i s wo
aces.
Le Fbe a spanning o es o G0(K). Assume ha F={T1, . . . , T }
whe e each Tiis a connec ed componen . Fo each connec ed componen Ti
o F, choose a 0-cell ias oo and pu a ows on he o he 0-cells poin ing
o he co ace ollowing he ee owa ds i s oo . This p o ides a disc e e
ec o ield Von Kwhe e he only c i ical 0-cells a e 1, . . . , . We now
p o e ha i is a DGVF and ha he numbe o c i ical 0-cells is minimal, so
he s a emen o he p oposi ion ollows.
As he a ows o Va e induced by ees, i is clea ha he e a e no
closed V-pa hs. Hence, Vis a DGVF and hus a HDVF (see P oposi ion 3.21
).
62 Chap e 4. Fas Comp. o Be i Numbe s on 3D Cubical Complexes
The numbe o c i ical 0-cells is minimal i we canno cancel a c i ical
0-cell wi h a c i ical 1-cell. This is ue i d′(γ) = 0 o each γ∈C1, which
we p o e now. Following Theo em 3.9, we ecall ha d′= d and
F=−d(S)|CH
=−d(S)|C
H+I−d(S)−1
|P
|{z }
H
d(S)|P
=−d(S)|CI+H(I−d(S)|P)=−d(S)|C+F(I−d(S)|P)
Thus, i (σ, τ)∈ V, (σ) = −d|C(τ) + (σ−d|P(τ)). By induc ion, o a
p ima y 0-cell gi es he oo io i s connec ed componen . Conside any
γ∈C1. Since Fis a spanning o es , he wo aces o γmus be con ained
in he same connec ed componen o G0(since adding his edge o Fmus
c ea e a cycle). Thus,
d′(γ) = d(γ) = i− i= 0
Figu e 4.2 illus a es he cons uc ion done in his p oo . On he le
he e is a 2D cubical complex oge he wi h i s g aph G0(K). In he middle
he e is a spanning o es o G0(K)(in ed). On he igh we can app eci-
a e he induced DGVF a e choosing as oo he op le mos 0-cell o he
complex.
b b
bb
b b
b
b
(A)
b b
bb
b b
b
b
(B) (C)
FIGURE 4.2: Illus a ion o he cons uc ion done in he
p oo o P oposi ion 4.3
We now p esen a p oposi ion simila o Alexande duali y which ells
how he homology o a 3D cubical complex and i s complemen in an acyclic
supe complex a e linked.
Le Lbe a 3D cubical complex such ha K⊂Land β(L) = (1,0,0,0).
We ypically conside L= [0, m]3 o some m > 0, assuming ha he coo -
dina es o he cells o Ka e all posi i e.
P oposi ion 4.4. Le Kand Lbe wo 3D cubical complexes such ha K⊂Land
β(L) = (1,0,0,0). Then,
βq(K) = (β1(L−K) + 1 i q= 0
βq+1(L−K)else
4.2. The I e a i e Algo i hm 63
P oo . No e ha , since K⊂L, he bounda y ma ix ( o all dimensions
oge he ) o Lis o he o m
D=D1·
0D2
whe e D1=d(K)|Kand D2=d(L−K)|L−K. As D·D= 0 and D1·D1= 0,
D2·D2= 0 oo. Le X1= (P1, S1)and X2= (P2, S2)be wo pe ec HDVFs
o Kand L−K espec i ely. Le X12 = (P12, S12) := (P1∪P2, S1∪S2)be
hei union. I is a HDVF o L:
de (d(S12)|P12 ) = de A·
0B
= de (A)·de (B)∈R∗
Mo eo e , as Aand Ba e in e ible,
d(S12)−1
|P12 =A−1·
0B−1
Le Y= (P, S)be a pe ec HDVF o L ha ex ends X12. Thus
d(S)|P=
A·Y1·
0B0Y2
X1· · ·
0X20·
whe e he las wo columns ( esp. ows) a e T1and T2( esp. Σ1and Σ2), he
new seconda y ( esp. p ima y) cells belonging o Kand L−K espec i ely.
By he Schu de e minan o mula,
de (d(S)|P) = de A·
0B·
de ··
0·−X1·
0X2A−1·
0B−1Y1·
0Y2
so he igh mos de e minan mus be a uni . Howe e , de eloping he
equa ion we ob ain
··
0·−X1H1Y1·
0X2H2Y2=0·
0 0
since X1and X2a e pe ec HDVFs. Thus, Σ2and T1mus be emp y. This
means ha all he new couples o cells in Ya e om K o L−K.
Le q > 0. Since βq(L) = 0 and βq+1(L) = 0, all he c i ical q-cells o K
mus cancel wi h he c i ical (q+ 1)-cells o L−Kand ice e sa. Hence,
βq(K) = βq+1(L−K).
Fo q= 0, since β0(L) = 1 and β1(L) = 0, all he c i ical 1-cells o
L−Kmus cancel wi h all he c i ical 0-cells o Kbu one and ice e sa.
The e o e, β0(K) = β1(L−K) + 1.
Thus, in o de o compu e β2(K)we can compu e β3(L−K). The ollow-
ing p oposi ion ells ha his can be achie ed also ia coun ing connec ed
64 Chap e 4. Fas Comp. o Be i Numbe s on 3D Cubical Complexes
componen s
P oposi ion 4.5. Le K⊂Lbe wo 3D cubical complexes. Conside he g aph
G3(L−K) = (V, E)such ha
•V= (L−K)3∪{ǫ}, he 3-cells o L−Kplus an ex a (abs ac ) e ex
•E={{u, } | uand ha e a common ace}∪{{u, ǫ} | ucon ains a ee ace}.
Thus, β3(L−K)is he numbe o connec ed componen s in he g aph G3(L−K)
minus one.
P oo . Obse e ha Eco esponds o he 2-cells o L−K, which can ha e
wo co aces ( ype {u, }) o jus one ( ype {u, ǫ}).
Le Fbe a spanning o es o G3(L−K). Assume ha F={T1, . . . , T }
whe e each Tiis a connec ed componen and ǫ∈T1. Fix ǫas he oo o T1
and, o he o he connec ed componen s Tio F, choose a 3-cell ias oo .
Pu a ows on he 2-cells poin ing o he co ace in he opposi e di ec ion
owa ds i s oo . This p o ides a disc e e ec o ield Von Kwhe e he
only c i ical 3-cells a e 2, . . . , . We now p o e ha i is a DGVF and ha
he numbe o c i ical 3-cells is minimal.
As he a ows o Va e induced by ees, i is clea ha he e a e no
closed V-pa hs. Hence, Vis a DGVF and hus a HDVF.
The numbe o c i ical 3-cells is minimal i we canno cancel a c i ical
3-cell wi h a c i ical 2-cell. This is ue i d′(γ) = 0 o each γ∈C3, o
equi alen ly, i (d′)∗(γ) = 0 o each γ∈C2, whe e (d′)∗deno es he dual o
d′. We ecall ha d′=dg, so (d′)∗=g∗d∗and
G=−Hd(C)|P
=−
H+I−d(S)|Pd(S)−1
|P
|{z }
H
d(C)|P
=−I+ (I−d(S)|P)Hd(C)|P=−d(C)|P+ (I−d(S)|P)G
Thus, i (σ, τ)∈V,g∗(τ) = d∗
|C(σ) + g∗(τ−d∗
|P(σ)). By induc ion, g∗o a
seconda y 2-cell gi es he oo io i s connec ed componen (i i6= 1) o
he emp y chain (i i= 1). Conside any γ∈C2.
1. I γhas wo co aces, hey mus be con ained in he same connec ed
componen o G3. Thus, (d′)∗(γ) = g∗d∗(γ) = i− i= 0
2. I γhas only one co ace hen i belongs o T1. Thus (d′)∗(γ) = g∗d∗(γ) =
0
The e o e, Vcon ains −1c i ical 3-cells and his numbe is minimal, which
comple es he p oo .
Once again, Figu e 4.3 illus a es he cons uc ion done in his p oo
in he wo-dimensional space. On he le he e is a 2D cubical complex
wi h he cells o L−Kcolo ed in ligh blue, wi h he g aph G2(L−K)
supe imposed. In he middle he e is a spanning o es o G2(L−K)(in
ed). On he igh we can app ecia e he induced DGVF a e choosing as
oo he op le mos 2-cell o he complex.
4.2. The I e a i e Algo i hm 65
b
b b
b
(A)
b
b b
b
(B) (C)
FIGURE 4.3: Illus a ion o he cons uc ion done in he
p oo o P oposi ion 4.5
The p e ious p oposi ions can di ec ly be ex ended o highe dimen-
sions. Also, Ldoes no need o be a 3D cubical complex o he o m [0, m]3.
We ha e conside ed he bounding box o K, bu any acyclic supe complex
can be used. We ecall ha hese s a emen s a e ue o simplicial com-
plexes, bu ob aining an acyclic supe complex o a simplicial complex o
he same dimension does no seem o be a i ial ask.
We can coun connec ed componen s using b ead h i s sea ch. Algo-
i hm 3explici ly illus a es his.
Algo i hm 3: Coun connec ed componen s in a g aph wi h BFS
Inpu : A g aph G= (V, E)
Ou pu : Numbe o connec ed componen s o G
n←0;
o each u∈Vdo
i uno ma ked hen
Q.push(u); ma k u;
while Qno emp y do
u←Q.pop();
o each such ha {u, } ∈ Edo
Q.push( ); ma k ;
n←n+ 1;
e u n n
We ac ually do no need o build he g aphs G0(K)no G3(L−K) o
coun i s connec ed componen s, since hey a e included in Kand L−K.
Algo i hm 3has complexi y O(|V|+|E|). In G0(K),|V|( esp. |E|) is he
numbe o 0-cubes ( esp. 1-cube) o K. Also, in G3(L−K)|V|( esp. |E|) is
he numbe o 3-cubes ( esp. 2-cube) o L−K. In addi ion, compu ing χ(K)
only needs coun ing he cubes o Kwi h he app op ia e sign. Hence, Al-
go i hm 4—called Vi eBe i om he F ench wo d “ i e” ( as )—compu es
he Be i numbe s o a 3D cubical complex in O(n) ime, whe e ndeno es
he numbe o cubes in L.
66 Chap e 4. Fas Comp. o Be i Numbe s on 3D Cubical Complexes
Algo i hm 4: Vi eBe i
Inpu : A 3D cubical complex K
Ou pu : I s Be i numbe s: β0,β1,β2
χ←χ(K);
β0←numbe o connec ed componen s o G0(K);
β2←numbe o connec ed componen s o G3(L−K)−1;
β1←β0+β2−χ;
e u n β0,β1,β2
4.3 The Recu si e Algo i hm
We showed in he p e ious sec ion ha he compu a ion o he Be i num-
be s o a 3D cubical complex educes o (1) compu e he Eule -Poinca é
cha ac e is ic and (2) o ind he numbe o connec ed componen s o wo
g aphs. We p esen in his sec ion a way o pa allelize Algo i hm 4wi h a
di ide-and-conque app oach.
Compu ing he Eule -Poinca é cha ac e is ic can be achie ed in O(log(n))
ime on a pa allel machine. Assuming ha he 3D cubical complex Kis en-
coded as a bina y 3D a ay AK(called CubeMap in [115]), i su ices o spli
he a ay in o wo pa s, ecu si ely sum bo h o hem and hen sum he wo
alues. The ecu sion s ops whene e only wo elemen s emain, in which
case we sum hem wi h hei co esponding signs. The ecu sion dep h o
his me hod is ⌈log2(n)⌉, so he p oblem can be sol ed in O(log(n)) wi h n/2
p ocesso s. A simple me hod consis s in di iding he bina y a ay in o p
pa s, summing each o hem in pa allel and hen summing all he pa ial
esul s. This app oach needs O(n/p +p)s eps, so i can be done in O(√n)
ime wi h p=√np ocesso s.
The e has been an ex ensi e esea ch abou compu ing connec ed com-
ponen s in pa allel, see [68,107,114] o some examples. We p esen he e
a simple ecu si e me hod ha wo ks well o commodi y compu e s wi h
ew p ocesso s.
Algo i hm 3desc ibed how o coun connec ed componen s by a e s-
ing he g aph. This app oach is no sui ed o pa alleliza ion since i uses a
queue da a s uc u e. Ano he well known app oach o compu e connec ed
componen s is o use he disjoin -se da a s uc u e (see [20, Chap. 21]). This
da a s uc u e main ains a collec ion S={S1, . . . , Sk}o disjoin se s. Each
se in Sis iden i ied by a ep esen a i e, which is a membe o he se . The
ollowing ope a ions can be pe o med on a disjoin -se da a s uc u e:
•MakeSe (u)- c ea es a new se whose only membe (and hus ep-
esen a i e) is u.
•Find(u)- e u ns a poin e o he ep esen a i e o he (unique) se
con aining u.
•Union(u, )- me ges he se s con aining uand in o a new se which
is he union o hese wo se s.
4.3. The Recu si e Algo i hm 67
To compu e connec ed componen s o a g aph i is enough o call Union(u, )
o each pai (u, )o adjacen e ices. A pa allel e sion o such algo-
i hm equi es synch oniza ion, so in p ac ice i canno be implemen ed
e icien ly. Howe e , he egula s uc u e o he cubical complex allows
us o p opose a di e en app oach whe e synch oniza ion is no needed.
The idea is o ecu si ely cu he g aph in wo hal es, ind he connec ed
componen s in each hal and hen me ge hem.
We ecall ha bo h G0(K)and G3(L−K)(wi hou he special e ex ǫ)
a e g id g aphs and ha hei e ices a e iden i ied o poin s o Z3 ia he
Khalimsky coo dina es. We de ine he le slice, igh slice and middle slice o
a subse o e ices Win dimension dby x espec i ely as
S(W, x−, d) := {u∈W|u= (u1, u2, u3), ud< x}
S(W, x+, d) := {u∈W|u= (u1, u2, u3), x ≤ud}
S(W, x0, d) := {u∈W|u= (u1, u2, u3), x −1≤ud≤x}.
These h ee ope a ions allow us o di ide a se o e ices in o wo pa s
( he le and he igh slice) plus a small subse ha in e sec s bo h.
Algo i hm 5 ecu si ely compu es he connec ed componen s o a g id
g aph. Obse e ha , a each s ep o he ecu sion, he se Wis di ided
in o wo pa s. Each o hem can be ea ed independen ly since he e a e
no edges be ween bo h se s. We hen conside he middle slice o combine
bo h pa s, which is no subdi ided (since ǫ=∞).
Algo i hm 5: Recu si eCC
Inpu : G= (V, E)a g id g aph, ǫ > 0
S←disjoin -se da a s uc u e;
Recu si eCC(V, 0, ǫ);
e u n |S|;
P ocedu e Recu si eCC(W, d, ǫ)
Inpu : W⊂V,d∈Z,ǫ > 0
1i |W|> ǫ hen
2d←((d+ 1) mod 3) + 1;
x←middle poin among he d h Khalimsky coo dina es o W;
3Recu si eCC(S(W, x−, d), d, ǫ);
4Recu si eCC(S(W, x+, d), d, ǫ);
5Recu si eCC(S(W, x0, d), d, ∞);
6else
7 o each u∈Wdo
8MakeSe (u)
9 o each u∈Wdo
10 o each ∈Winciden o udo
11 Union(u, );
A he end o Algo i hm 5all he edges ha e been ea ed, so he disjoin -
se da a s uc u e Scon ains he connec ed componen s o he g aph. In o -
de o use his me hod o coun ing connec ed componen s in Algo i hm 4
we need o cla i y wha happens wi h he e ex ǫo G3(L−K). Ins ead
o di ec ly coun ing he connec ed componen s o G3(L−K), we do i o
68 Chap e 4. Fas Comp. o Be i Numbe s on 3D Cubical Complexes
he induced subg aph wi hou ǫ, which is a g id g aph. Then, by me ging
all he se s in Scon aining a e ex inciden o ǫin G3(L−K), we ob ain
he numbe o connec ed componen s o G3(L−K). Howe e , i is mo e
con enien o add a lag o he se s con aining such e ices (a line 8) and
hen conside only one o hose se s when coun ing |S|.
4.4 Resul s
We compa e in his sec ion ou algo i hm wi h he lib a y CAPD::RedHom
[77], specialized in Be i numbe s compu a ion on cubical complexes. We
ha e used he de aul se ings, which execu es sha ing, co educ ion algo-
i hm, disc e e Mo se heo y educ ion and inally algeb aic educ ions.
Th ee e sions o ou algo i hm a e es ed: VB-i o he i e a i e e sion
in oduced in Sec ion 4.2,VB- o he ecu si e e sion desc ibed in Sec-
ion 4.3 and VB- p o he same algo i hm using pa allel compu ing.
Ou algo i hms a e implemen ed in C++ and compiled by he GNU
compile g++ ( e sion 5.2.1) wi h op ion -O3. The pa allel algo i hm VB-
p uses he Th eading Building Blocks (TBB) lib a y [70] ( e sion 4.4).
We ha e es ed he algo i hm wi h andom 3D cubical complexes. A
(2·m+1)3cubical complex consis s in a cube o m33-cubes wi h hei aces.
Each cubical cell (and i s aces) is added wi h a ixed p obabili y p(see he
andom model K(p, m)in Sec ion 3.9). We ha e made 10 andom cubical
complexes o size 513,1013,2013,3013,4013and 5013and p obabili y 0.25,
0.5and 0.75. We use ǫ= 105as h eshold o VB- and VB- p, which seems
o be he bes one o his implemen a ion. We compu ed hese 180 cubical
complexes on a Dell PC wi h 3.70GHz ×8 In el Xeon E5-1630 3 CPU and
31.3 GB RAM. The expe imen al esul s a e ob ained by a e aging he ex-
ecu ion ime o he algo i hms, while he eading ime (which exceeds he
execu ion ime o he bigge complexes) is omi ed. Table 4.1 shows he
esul s ob ained. The Be i numbe s calcula ed by each o he algo i hms
a e ob iously he same.
Size RedHom VB-i VB- VB- p
5130.1842 0.0026 0.0026 0.0023
10131.268 0.0142 0.0148 0.0091
201310.78 0.1309 0.1232 0.0552
301340.89 0.4303 0.4176 0.1583
4013101.26 1.436 0.983 0.3092
5013— 3.609 1.977 0.5494
TABLE 4.1: Execu ion ime (in seconds) e sus he size o
he cubical complex.
We can app ecia e ha ou algo i hm clea ly imp o es he execu ion
ime o RedHom. Mo eo e , RedHom uses a memo y consuming da a
s uc u e o i s compu a ion which does no allow us o p ocess complexes
bigge han 4013, which can be achie ed by Vi eBe i.
The ecu si e e sion o ou algo i hm, VB- , is clea ly as e han VB-i.
The TBB lib a y au oma ically chooses he numbe o pa allel h eads, bu
we can app ecia e ha VB- p is mo e han h ee imes as e han VB- o
cubical complexes o size bigge han 4013.
5.2. The measu es 75
Ou measu es a e only de ined o disc e e objec s and canno conside
indi idual homology classes, bu hey can be compu ed as e ( he e is no
op imiza ion p oblem) and hey ha e e y good geome ic p ope ies as i
will be shown in his chap e .
Le O⊂Zdbe a disc e e objec (see Sec ion 2.4). We ix d= 3 o simplic-
i y, bu he gene aliza ion o any dimension is di ec . We ha e wo ways o
building he cubical complex Kassocia ed o Odepending on which con-
nec i i y ela ion we choose: he 6 o he 26-connec i i y ela ion.
The dis ance ans o m d Oo Ois he map ha sends e e y oxel x∈O
o
d O(x) = d(x, O) = min {d(x, y)|y /∈O}
whe e
d(x, y) =
u
u
3
X
i=1
(xi−yi)2
is he Euclidean dis ance. Howe e , we can also conside o he dis ances
such as he Manha an dis ance (L1), he chessboa d dis ance (L∞), dis-
ances based on cham e masks [92,9] o sequences o cham e masks [97,
101].
The signed dis ance ans o m sd Oo Ois he map sd O:Z3→Rde ined
as ollows:
sd O(x) = (−d O(x) = −min {d(x, y)|y /∈O}i x∈O
d Z3 O(x) = min {d(x, y)|y∈O}i x /∈O
Le us poin ou some simple p ope ies abou he suble el se s L−
(sd O) :=
sd −1
O(]−∞, ]) o he signed dis ance ans o m.
1. O=sd −1
O(]−∞,0])
2. Z3=sd −1
O(]−∞,∞[)
3. sd −1
O(]−∞, a]) ⊂sd −1
O(]−∞, b]) whene e a < b
Figu e 5.5 shows i e suble el se s a di e en alues. Obse e ha he
sequence o objec s sd −1
O(]−∞, [)0
=−∞ looks like an e osion o O, while
sd −1
O(]−∞, [)∞
=0 seems a dila ion.
We now de ine he il a ion associa ed o he signed dis ance ans o m.
A simple o mula ion o his il a ion is
F=K[L−
(sd O)] ∈R
whe e K[Y]deno es he p imal o he dual associa ed cubical complex o
Y.
PDq(F)⊂R2deno es he pe sis ence diag am in dimension qo his
il a ion. We deno e TBq={(x, y)∈PDq(F)|x < 0, y > 0}. I is ob ious
ha TBqcon ains βq(K)pai s, ha is, he e a e as many pai s in TBqas
q-holes in O.
De ini ion 5.1. Le O⊂Z3be a disc e e objec . Le us ix a dis ance unc ion
d:Z3×Z3→Rand a connec i i y ela ion. Le q≥0,
76 Chap e 5. Measu ing Holes
FIGURE 5.5: Suble el se s o he signed dis ance ans o m
a alues -10 ( op-le ), -5 ( op- igh ), 0 (middle), 5 (bo om-
igh ) and 10 (bo om- igh )
•The hickness o he q-holes o Oa e he alues {−x|(x, y)∈TBq}
•The b ead h o he q-holes o Oa e he alues {y|(x, y)∈TBq}
Obse e ha he hickness and he b ead h o he holes appea in pai s.
We can hus ep esen hem as poin s in R2in he hickness-b ead h diag am,
jus like he pe sis ence diag ams. We call hese poin s hickness-b ead h
pai s. The in e p e a ion o he hickness-b ead h diag am is simila o ha
o he pe sis ence diag am: poin s close o he axes a e holes wi h one small
measu e which may be o igina ed by he p esence o noise in he disc e e
objec . Sec ion 5.3 con ains many examples o hickness-b ead h diag ams.
We speak abou measu es o he holes since we ob ain as many alues
as holes in he objec . Howe e , we canno measu e a gi en hole ( ha is,
a cycle xsuch ha [x]6= 0). This is why we ha e p e e ed o alk abou
measu es o he homology g oups in [59], which seems a mo e co ec o mu-
la ion. Ne e heless, we hink ha speaking abou measu es o he holes
sounds clea e .
5.2. The measu es 77
5.2.1 On he compu a ion o he measu es
In his sec ion we gi e a mo e de ailed desc ip ion o how he measu es a e
compu ed.
Le us assume ha he disc e e objec is con ained in a bounding box
BB := [0, w1]×[0, w2]×[0, w3]⊂Z3. The signed dis ance ans o m
can be ob ained by compu ing he dis ance ans o m o Oand BB O
in O(w1w2w3)[74].
Nex , he il a ion induced by sd Odepends on he associa ed cubical
complex ha we conside .
•P imal associa ed cubical complex: le K:= Kp[BB]be he p imal
cubical complex associa ed o he bounding box BB. We de ine he
il a ion induced by sd Oin e ms o a unc ion Ode ined on K.
Recall ha each 3-cube is iden i ied wi h a oxel o BB. Thus, o
e e y 3-cube σ∈K, O(σ) akes he alue o sd Oon i s associa ed
oxel. Fo he es o he cubes, he alue o Ois assigned so i s
suble el se s a e complexes. Namely, O(σ) = min O(τ(3))|τ > σ.
In o he wo ds, Omaps each cube σ∈K o he i s alue such ha
σ∈Kp[L−
(sd O)].
•Dual associa ed cubical complex: he desc ip ion is simila . Le K:=
Kd[BB]be he dual cubical complex associa ed o he bounding box
BB. Since e e y 0-cube is iden i ied wi h a oxel o BB, O(σ) akes
he alue o sd Oon i s associa ed oxel o each 0-cube σ∈K. Fo
he es o he cubes, O(σ) = max O(τ(0))|τ < σ.
Le a0< a1<··· <−1<1<··· < anbe he di e en alues o Oo e
K. Thus, we can conside he il a ion F:
K0= −1
O(]−∞, a0]) ⊂ ··· ⊂ K[O]⊂ ··· ⊂ Kn= −1
O(]−∞, an]) = K
Pe sis en homology is a e y ac i e ield o esea ch. The compu a ion
o he pe sis ence in e als o a il a ion has cubical wo s -case complexi y.
An algo i hm in ma ix mul iplica ion ime was in oduced in [88]. How-
e e , he mos ecen algo i hms [10,7] a e obse ed o ha e nea linea
complexi y. An algo i hm adap ed o cubical complexes was de eloped in
[115].
Algo i hms o pe sis en homology conside a kind o elemen a y il-
a ion whe e each s ep consis s in adding only one cell o he p e ious
complex. Thus, we need o decompose he il a ion F. Some heu is ics a e
gi en in [7] o his decomposi ion in o de o accele a e he compu a ion
o he pe sis ence in e als. We hus ob ain some se s Pqo pai s o cells
(σ(q), τ(q)) o q≥0. The q-dimensional pe sis ence diag am is
PDq( ) = {( (σ), (τ)) |(σ, τ)∈Pq}∪{( (γ),∞)|γno pai ed}
Obse e ha his se does no depend on how he il a ion Fis e ined.
Howe e , he pai o cells associa ed wi h each poin does depend. This is
ele an o he ollowing sec ions. The e a e ypically many poin s o he
o m (x, x)in he pe sis ence diag am which a e usually igno ed.
78 Chap e 5. Measu ing Holes
Rega ding he hickness-b ead h diag am, he e exis s only one poin
(x, ∞)co esponding o he i s connec ed componen ha appea s in he
il a ion. This poin can be plo ed as (x, −1).
5.2.2 The obus ness o he measu es
We p o e in his sec ion he obus ness o he measu es. The idea is ha i
we sligh ly de o m an objec , i s measu es su e small changes.
The celeb a ed a icle [19] in oduced a heo em o he s abili y o he
pe sis ence diag ams. We ecall ha ||x||∞= max {|x1|,|x2|} o x∈R2and
|| ||∞= max {| (a)| | a∈A} o a unc ion :A→R. We can compa e wo
pe sis ence diag ams ia he Hausdo dis ance.
Le X, Y be wo mul ise s (se s wi h epe i ions) o poin s in R2. Thei
Hausdo dis ance is
dH(X, Y ) = max max
xmin
y||x−y||∞,max
ymin
x||x−y||∞
whe e x∈Xand y∈Y. Thus, i dH(X, Y ) = ǫ hen o e e y x∈X he e
is a y∈Ysuch ha ||x−y||∞≤ǫand ice e sa.
Le us adap one o he heo ems o [19] o ou con ex . Le and gbe
wo unc ions on a cubical complex de ining a il a ion, ha is, hei sub-
le el se s a e cubical complexes (each cube con ains all i s aces in he sub-
le el se ). Le PD( )and PD(g)be hei espec i e pe sis ence diag ams
(all dimensions aken oge he ). The e o e,
dH(PD( ), PD(g)) ≤ || −g||∞
Consequen ly, i he wo unc ions a e simila , hei associa ed pe sis ence
diag ams a e also simila .
Le now Xand Ybe wo disc e e objec s. We call Xand Y he il a ion
unc ions induced by sd Xand sd Y espec i ely.
Lemma 5.1. Le x, y ∈Z3be wo 26-neighbo s and A⊂Z3. Then
|sd A(x)−sd A(y)| ≤ 2√3
P oo . We ecall ha , as xand ya e 26-neighbo s, |x−y|:= ||x−y||2≤√3.
We ha e o conside ou cases:
•x, y /∈A. Le us call px, py∈A hei closes poin s in A. Thus
sd A(x) = |x−px| ≤ |x−py|
≤ |x−y|+|y−py|=|x−y|+sd A(y)
Thus,
sd A(x)−sd A(y)≤ |x−y|
By symme y,
|sd A(x)−sd A(y)| ≤ |x−y| ≤ √3≤2√3
5.2. The measu es 79
•x /∈A, y ∈A. Then
sd A(x)≤ |x−y|
−sd A(y)≤ |y−x|
Thus,
sd A(x)−sd A(y)≤2·|x−y| ≤ 2√3
By symme y,
|sd A(x)−sd A(y)| ≤ 2√3
•The o he wo cases ollow he same a gumen s.
Theo em 5.2. Le Xand Ybe wo disc e e objec s in Z3. Le us call
δ=dH(X, Y ) + dH(Z3 X, Z3 Y) + 2√3.
Then, o e e y hickness-b ead h pai pX= (x, y)o Xsuch ha x, y > δ, he e
exis s ano he hickness-b ead h pai pY= (x′, y′)o Ysuch ha
||pX−pY||∞≤δ
P oo . Le σbe an elemen a y cube. Le us conside he wo possible cubical
complexes associa ed o he disc e e objec s.
•P imal associa ed cubical complex: X(σ) = X(τX) o a 3-dimensional
co ace τX. Simila ly, Y(σ) = Y(τY). Le qXand qYdeno e he oxels
associa ed o he 3-cubes τXand τY espec i ely.
•Dual associa ed cubical complex: X(σ) = X(τX) o a 0-dimensional
ace τX. Simila ly, Y(σ) = Y(τY). Le qXand qYdeno e he oxels
associa ed o he 0-cubes τXand τY espec i ely.
In bo h cases qXand qYa e 26-neighbo s, so ||qX−qY|| ≤ √3. The e o e,
| X(σ)− Y(σ)|=| X(τX)− Y(τY)|
=|sd X(qX)−sd Y(qY)|
≤ |sd X(qX)−sd Y(qX)|+|sd Y(qX)−sd Y(qY)|
By Theo em 2 o [81],
||sd X−sd Y||∞≤dH(X, Y ) + dH(Z3 X, Z3 Y)
Thus,
| X(σ)− Y(σ)| ≤ |sd X(qX)−sd Y(qX)|+|sd Y(qX)−sd Y(qY)|
≤dH(X, Y ) + dH(Z3 X, Z3 Y) + 2√3
Consequen ly,
dH(PD( X), PD( Y)) ≤ || X− Y||∞≤δ
80 Chap e 5. Measu ing Holes
As he hickness-b ead h diag am is he in e sec ion o he pe sis ence dia-
g am wi h he quad an {(x, y)∈R2:x, y ≥0}, he heo em ollows om
his.
Obse e ha , i a hickness-b ead h pai is close o he axes, a small
pe u ba ion in he dic e e objec can make i disappea . In o he wo ds,
a hole being no hick o b oad enough can easily disappea a e a small
pe u ba ion. Hence, in o de o compa e he hickness-b ead h pai s o
wo disc e e objec s, hey mus be a enough om he axes. This is why we
ask hei alues o be bigge han δin Theo em 5.2.
Thus, we can bound he dis ance be ween wo hickness-b ead h dia-
g ams ia he Hausdo dis ance o he wo objec s and hei complemen s.
5.3 Thickness and b ead h balls
In he p e ious sec ion we ep esen ed he hickness and he b ead h o he
holes as poin s in he hickness-b ead h diag am. The e is an al e na i e
way, in e ms o balls.
Each hickness-b ead h pai ( , b)has an associa ed pai o cubes (σ, τ).
The e o e,
•i s hickness ball is he ball cen e ed a he ba ycen e o σwi h adius
;
•i s b ead h ball is he ball cen e ed a he ba ycen e o τwi h adius b.
Obse e ha he hickness balls a e con ained in he objec , while he b ead h
balls a e ou side. No e howe e ha he cubes σand τa e no unique since
hey depend on how we decompose he il a ion induced by he signed
dis ance ans o m.
The hickness and b ead h balls allow us o ep esen bo h measu es
di ec ly on he objec . Mo eo e , he i s imp ession we ha e when we
encoun e he b ead h balls is ha hey a e in he cen e o he holes.
I is well accep ed o isualize holes as ep esen a i es o a se o ho-
mology gene a o s. Fo each ep esen a i e, which is a chain, we ma k
hose cells wi h a non-nega i e coe icien . Ne e heless, hese ep esen a-
i es can be isually unpleasan . In o de o be e o malize his aspec ,
some au ho s sugges ha he bes ep esen a i es a e hose which a e min-
imal in e ms o hei leng h, a ea, olume, e c [47,17,31].
B ead h balls eme ge as an in e es ing al e na i e o he ep esen a ion
o holes in e ms o homology gene a o s. Symme ically, hickness balls
look like cohomology gene a o s.
In he ollowing we show se e al examples o hickness-b ead h dia-
g ams and balls. We ha e conside ed se e al meshes om he AimA Shape
eposi o y1(excep o Buddha2) and we ha e con e ed hem o bina y ol-
umes using he so wa e bin ox3. The hickness-diag am and balls we e
compu ed wi h a speci ic so wa e which does no ake ad an age on he
1h p:// isionai .ge.ima i.cn .i /
2Cou esy o he S an o d Compu e G aphics Labo a o y
3h p://www.pa ickmin.com/bin ox/
5.4. Small gene a o s 81
la es esul s in pe sis en homology compu a ion [10,7], so we ha e omi -
ed he ime spen in hese calcula ions.
Figu e 5.6 illus a es a oxelized e sion o Buddha. The hickness balls
a e shown in ed, while he b ead h balls a e in g een. We only display he
balls o he 1-holes, since he o he ones a e less isually in e es ing. The
hickness-b ead h diag am shows he 0-holes ( ed ci cle), 1-holes (g een i-
angles) and 2-holes (blue squa e). Obse e ha he hickness o he only
connec ed componen s, which is ∞, is ep esen ed as −1. Also, he small
(in bo h hickness and b ead h) 2-hole is due o an e o in he oxeliza ion
p ocess o he mesh. Figu es 5.7–5.16 show o he models.
5.4 Small gene a o s
In his sec ion we in oduce a heu is ic o ob aining well-shaped gene a-
o s o he homology and cohomology g oups based on he hickness and
b ead h balls.
In he p e ious sec ion we claimed ha he hickness and b ead h balls
seem o be a good al e na i e o localizing holes, ins ead o displaying he
homology gene a o s. The e o e, i is a na u al ques ion o wonde i we
can use hese balls o ind well-shaped homology gene a o s. Mo eo e ,
he duali y hickness/b ead h o he measu es p o ides also esul s o he
cohomology g oups.
The localiza ion p oblem [18] consis s in inding he smalles ep esen a-
i e cycle o a homology class wi h ega d o a geome ic measu e. I seems
na u al ha such cycles a e good ep esen a i es o he holes. We explain
some o hese measu es in a nu shell. Le Kbe a CW complex endowed
wi h a weigh unc ion on i s cells (i s q-dimensional olume o jus a con-
s an ). Some measu es a e:
Volume The olume o a chain is he sum o he weigh s o i s cells.
Diame e The diame e o a chain is he maximal disc e e geodesic dis ance
(see Sec ion 5.2) be ween he 0-dimensional aces o he cells in he
chain. I Kis embedded in a me ic space we can also conside he
maximal dis ance be ween he 0-dimensional aces.
Radius The adius o a chain is he adius o he smalles geodesic ball
con aining he chain. Again, i Kis embedded in a me ic space we
can conside he adius o he smalles ball con aining he chain.
Chen and F eedman [18] p o ed ha inding a cycle minimizing he ol-
ume is an NP-ha d p oblem, e en i we look o an app oxima ion. Con-
side ing he diame e is also an NP-ha d p oblem, bu we can compu e a
2-app oxima ion conside ing he adius, o which he e is a polynomial
ime algo i hm. Sadly, hey also showed ha conside ing he diame e o
he adius does no always p o ide isually pleasan gene a o s as hey can
wiggle.
Ou heu is ic p o ides a cycle and a cocycle associa ed o each hickness-
b ead h pai o a disc e e objec . The in ui ion is ha a minimal homology
gene a o mus be a ound a b ead h ball, while a minimal cohomology gen-
e a o mus a e se a hickness ball. Howe e , gi en he complexi y esul s
exposed p e iously, we canno expec o p o e ha hese gene a o s a e op-
imal o he olume.
82 Chap e 5. Measu ing Holes
FIGURE 5.6: Buddha: hickness balls (in ed), b ead h balls
(g een) and hickness-b ead h diag am.
5.4. Small gene a o s 83
FIGURE 5.7: Cas ing: he e a e wo ypes o 1-holes acco d-
ing o he b ead h. We also obse e ha he na ow (less
b oad) holes do no ha e he same hickness, as hey a e no
equally close o he bo de .
84 Chap e 5. Measu ing Holes
FIGURE 5.8: Dancing: he b ead h balls clea ly localize he
1-holes o he objec .
5.4. Small gene a o s 91
FIGURE 5.15: Nep une: he e a e h ee no able holes in his
objec . The es , loca ed in he bea d and in he hand, can be
conside ed as noise.
92 Chap e 5. Measu ing Holes
FIGURE 5.16: Pegasus: he e a e i e signi ican holes and a
small one nea he igh on paw (see i s hickness ball).
5.4. Small gene a o s 93
5.4.1 Homology gene a o s
Le Obe a disc e e objec o which we ha e compu ed he hickness and he
b ead h o i s holes. Le (σ, τ)be a pai o cubes associa ed o a hickness-
b ead h pai and le ρ−= (h, , g)be he educ ion associa ed o he pe -
sis en homology compu a ion pe o med o ob aining he measu es o O
be o e adding he cells wi h posi i e signed dis ance ans o m. No e ha
ρ−is a educ ion o K[O]. Ac ually, we only need he chain ∗(σ). Algo-
i hm 6p o ides a cycle associa ed o he homology gene a o g(σ).
Algo i hm 6: Homology gene a o
Inpu : A disc e e objec O, i s educ ion ρ−, a pai o cubes (σ, τ)
associa ed o a hickness-b ead h pai
Ou pu : A cycle xsuch ha h (x), σi 6= 0
~p ←some oxel associa ed o τ;
F← il a ion induced by d~p :O→R;
Compu e he pe sis en homology on F. When a cycle xis ound,
check i h (x), σi 6= 0. I ue, e u n his cycle;
Le ~p be a oxel associa ed o τ: a 3-dimensional co ace i we conside ed
he p imal associa ed cubical complex o a 0-dimensional ace i we consid-
e ed he dual associa ed cubical complex. I is no unique, so we choose
one a bi a ily. Le d~p :O→Rbe he unc ion ha maps e e y oxel o O
o i s dis ance o ~p. Conside he il a ion Fassocia ed o his unc ion (as
we did o he signed dis ance ans o m in Sec ion 5.2). When we compu e
he pe sis en homology o his il a ion we ind a bounda y associa ed o
a nega i e cell o a cycle xassocia ed o a posi i e cell. Among hese cycles,
we ake he i s one o which h (x), σi 6= 0.
The condi ion h (x), σi 6= 0 means ha i we w i e he class [x]in e ms
o he homology base g(C)associa ed o ρ−, he coe icien o he gene a o
g(σ)is no ze o. This is necessa y o cap u e he hole we wan . Figu e 5.17
shows a bina y image wi h wo holes and i s b ead h balls (in blue). While
sea ching o a small homology gene a o o he b oade hole, Algo i hm 6
inds he small cycle xin he middle be o e he bigge cycle yon he igh .
The condi ion h (x), σi 6= 0 a oids o e u n x, which does no co espond
o he hole we chose.
FIGURE 5.17: Le : a bina y image wi h i s b ea h balls in
blue. Cen e and igh : wo cycles ound du ing he com-
pu a ion o Algo i hm 6.
I seems ha we could ob ain an app oxima ion o a minimal homology
base by compu ing he chains associa ed o each hickness-b ead h pai , bu
his is unclea since we could ob ain a se which is no linea ly independen .
94 Chap e 5. Measu ing Holes
5.4.2 Cohomology gene a o s
Rep esen ing holes by he gene a o s o he cohomology g oups seems an
unused app oach. This is possibly due o he ac ha hey a e no mani old-
like (as homology gene a o s) since hey a e cocycles ins ead o cycles. Ne -
e heless, hey can be isually in e es ing i we do no only display he cells
in he cohomology gene a o s bu also all i s co aces. No e ha when we
display he homology gene a o s we also display hei aces, which is he
dual s a emen o he p e ious sen ence. We a e in e es ed in compu ing
small cohomology gene a o s since hey display holes as hickness balls do.
The heu is ic o ob aining a cochain associa ed o a hickness-b ead h
pai is e y simila . Algo i hm 7p o ides a cocycle associa ed o he coho-
mology gene a o ∗(σ).
Algo i hm 7: Cohomology gene a o
Inpu : A disc e e objec O, i s educ ion ρ−, a pai (σ, τ)o cubes
associa ed o a hickness-b ead h pai
Ou pu : A cocycle xsuch ha hg∗(x), σi 6= 0
~p ←some oxel associa ed o σ;
F←co il a ion induced by d~p :O→R;
Compu e he pe sis en cohomology on F. When a cocycle xis
ound, check i hg∗(x), σi 6= 0. I ue, e u n his cocycle;
The inpu is he same, unless we only need he cochain g(σ). The main
di e ence is ha we do no conside a il a ion bu a co il a ion. In Algo-
i hm 6we compu e he pe sis en homology o he il a ion induced by
d~p because we wan o conside all he cycles ha appea in his il a ion.
Using he algo i hm o pe sis en homology a oids o conside cycles ha
a e bounda ies, bu we ac ually do no need he pe sis ence in e als o
his il a ion. In his con ex we wan o ind cocycles, so we ake a dual
app oach.
Le Kbe a cubical complex. L⊂Kis a sub-cocomplex i o each cube o
L, all i s co aces in Ka e also included in L. A co il a ion o Kis a sequence
o nes ed sub-cocomplexes ∅=K0⊂ ··· ⊂ Km=K. Thus, a cube en e s
he co il a ion be o e i s aces. We can adap he pe sis en homology al-
go i hm by conside ing cobounda ies ins ead o bounda ies, which gi es a
cobounda y o a cocycle o each cube. As in Algo i hm 6, we ake he i s
cocycle such ha hg∗(x), σi 6= 0.
Le us p esen a ew esul s o hese wo algo i hms. Figu e 5.18 depic s
a hickened wi e- ame cube. We can app ecia e i s homology gene a o s
(in g een) and cohomology gene a o s (in ed) o dimension 1. Obse e
ha wo o i s cohomology gene a o s a e oo close o be dis inguished. A
double o us is shown in Figu e 5.19, whose gene a o s a e igh . The objec
in Figu e 5.20 does no ha e ou holes, bu h ee. They a e loca ed by he
gene a o s. Le us poin ou ha he gene a o s ob ained o hese h ee
objec s a e linea ly independen and hence hey con o m a (co)homology
base. Howe e , as men ioned abo e, his is no gua an eed o ou wo
algo i hms.
5.5. Opening o closing holes 95
FIGURE 5.18: An objec wi h i s homology gene a o s ( op,
in g een) and homology gene a o s (bo om, in ed).
5.5 Opening o closing holes
I [x]is a non- i ial homology class, i means ha xis a cycle, bu i is no
a bounda y. Thus, i we add a “co ace” so xbecomes a bounda y, i will be
a i ial class. This means ha a homology gene a o s is he bounda y o a
chain ha is missing. Hence, in o de o emo e a hole, we can add such
chain.
Le us see now why his easoning does no wo k o cohomology. A
non- i ial cohomology class [x]is a cocycle ha i is no a cobounda y.
Thus, i we wan i o become a cobounda y, we mus add a “ ace” whose
cobounda y is x. Howe e , his does no make sense since a complex al-
eady con ains all i s aces.
We de ine now wha is o open and o close a homology class. Gi en
96 Chap e 5. Measu ing Holes
FIGURE 5.19: A double o us. Model om he AimA Shape
eposi o y.
wo cubical complexes K⊂L, he inclusion map ι:K→Linduces a chain
map ι#:C(K)→C(L)be ween hei co esponding chain g oups. Hence,
ι#induces a homomo phism ι∗:H(K)→H(L)be ween hei homology
g oups, ha is, ι∗([x]) is he homology class o he chain xin H(L).
De ini ion 5.2. Le Kbe a cubical complex, xa cycle and Sa se o cubes. Then,
•Sopens he chain xi K−Sis a cubical complex, ι∗:H(K−S)→H(K)
is injec i e and [x]/∈im(ι∗). We say ha Sis an opening se o x.
•Scloses he chain xi K∪Sis a cubical complex, ι∗:H(K)→H(K∪S)
is su jec i e and [x]∈ke (ι∗). We say ha Sis a closing se o x.
Le [x]be a non- i ial homology class o H(K). The injec i i y o ι∗
means ha K−Sdoes no con ain new holes, and [x]/∈im(ι∗)implies ha
we ha e emo ed he hole [x]. A simila in e p e a ion ollows om he de -
ini ion o closing a chain. No e ha , by closing a q-hole, se e al o he holes
may disappea . Fo ins ance, closing a 1-hole can me ge wo connec ed
componen s ( hink o wo chained ci cles) and closing he 2-hole o a o us
5.5. Opening o closing holes 97
FIGURE 5.20: An objec wi h h ee 1-holes. Model om he
AimA Shape eposi o y.
emo es one o i s 1-holes. Also, opening a 0-hole emo es all he highe -
dimensional holes in he connec ed componen and opening a 1-hole in a
o us emo es i s 2-hole.
The e ms open and close a e inspi ed by he wo k o Ak ou e al. [1].
They in oduced he concep o opological hull o a h ee-dimensional dis-
c e e objec O: i is a minimal ( o inclusion) supe se TH ⊃Owhich has
no holes o ca i ies in he sense o digi al opology [79]. La e , Janaszewski
e al. [71] made he dis inc ion be ween closing a hole (adding a minimal
se o oxels o emo e he hole) and illing a hole ( he se is no minimal
since i ies o i he local geome y o he objec ). Obse e, howe e , ha
hese no ions a e de ined o disc e e homo opy and no o homology.
These de ini ions e oke he ollowing p oblem: wha is he minimal
opening/closing se (unde any geome ic c i e ion) o a gi en chain, o
mo e gene ally, wha is he minimal se ha opens/closes all he holes o
98 Chap e 5. Measu ing Holes
a cubical complex? This seems o be a ha d p oblem. In ui i ely, he in-
e sec ion o a minimal closing ( esp. opening) se wi h he objec gi es a
small homology ( esp. cohomology) gene a o . Thus, we can e en expec
his p oblem o be NP. Consequen ly, as in Sec ion 5.4, we only p o ide
algo i hms ha seem o wo k well, wi hou any p oo o op imali y.
5.5.1 Opening a hole
The p e ious sec ion, whe e se e al cohomology gene a o s we e shown,
should ha e sugges ed an idea: emo ing a cohomology gene a o e ases a
hole. We canno p o e his ac because i is no ue in gene al. Figu e 5.21
illus a es a coun e -example. I shows a small simplicial complex wi h one
1-hole. I has a cohomology gene a o in ol ing h ee 1-simplices (ma ked
in ed). A e emo ing hem, and hei co aces, he e is s ill a 1-hole in he
complex. No e ha we could ha e emo ed o he cohomology gene a o s
which do open he hole.
FIGURE 5.21: Le : a simplicial complex Kwi h a cohomol-
ogy gene a o x(in ed). Righ : a e emo ing x(and i s
co aces) om K, he e is s ill a 1-hole.
Le Kbe a cubical complex endowed wi h a pe ec HDVF X= (PX, SX)
whose c i ical cells a e CX={γ1, . . . , γ }. I we ha e a subcomplex L⊂K
endowed wi h a pe ec HDVF Y= (PY, SY)such ha PY⊂PX,SY⊂SX
and CY⊂CX−{γ1}, hen we ha e opened he homology gene a o gX(γ1)
associa ed o he c i ical cell γ1in K:
•Lis a cubical complex
•Since bo h HDVFs a e pe ec , [gX(γ1)] = XgX(γ1) = γ1, which does
no belong o CY, so [gX(γ1)] /∈im(ι∗)
•CY⊂CXimplies ha ι∗is injec i e.
We can ob ain such cubical complex by emo ing a c i ical cell and pai s
o cells un il we ob ain a cubical complex. Algo i hm 8desc ibes his p o-
cedu e.
A he end we ob ain a pe ec HDVF o he subcomplex K−Owhich
does no con ain γ. Thus, K−Ohas a leas one hole less, and no holes a e
c ea ed. Be o e p o ing i , we need a lemma ha ensu es ha we can ind
he cells τand σa lines 6and 9 espec i ely.
5.5. Opening o closing holes 99
Algo i hm 8: Hole opening
Inpu : A CW complex Kendowed wi h a pe ec HDVF X= (P, S),
a c i ical cell γ
Ou pu : An opening se O o he homology gene a o g(γ)
1Q.push(d∗(γ));
2O← {γ};
3while Qno emp y do
4a←Q.pop();
5i a∈P hen
6choose τ > a s . hh(a), τi 6= 0;X←R(X, a, τ);
7O←O∪{a};Q.push(d∗(a));
8else i a∈S hen
9choose σ < a s . hh(σ), ai 6= 0;X←R(X, σ, a);
10 O←O∪{σ};Q.push(d∗(σ));
11 else i a∈C hen
12 O←O∪{a};Q.push(d∗(a));
13 e u n O
Lemma 5.3. Le Kbe a CW complex endowed wi h a pe ec HDVF X= (P, S).
Then,
•I σ∈P hen he e exis s τ∈S,τ > σ such ha hh(σ), τi 6= 0.
•I τ∈S hen he e exis s σ∈P,σ < τ such ha hh(σ), τi 6= 0.
P oo . Le σ∈Kbe a p ima y cell. Since d(S)|P·H=I, hen d(S)|σ·h(σ)|S=
1. Thus, he e exis some τ∈Ssuch ha
hd(τ), σi 6= 0 and hh(σ), τi 6= 0
The second s a emen ollows om H·d(S)|P=I.
Nex , we need ye ano he lemma.
Lemma 5.4. Le K⊂Lbe wo CW complexes endowed wi h wo HDVFs X⊂Y
espec i ely. I Yis pe ec hen Xis pe ec oo.
P oo . The bounda y ma ix o Lis o he o m
D=D1·
0D2
whe e D1=d(K)|Kand D2=d(L−K)|L−K. Thus,
d(S)P·H=u
0w·xy
z =I0
0I
and
H·d(S)P=xy
z ·u
0w·=I0
0I
100 Chap e 5. Measu ing Holes
No e ha uis in e ible (since Xis a HDVF). Hence,
xu +y0 = I⇒x=u−1
zu + 0 = 0 ⇒z= 0
The e o e,
H=u−1·
0·
Consequen ly, as Yis pe ec ,
d(C)|C= 0 ⇒A·
0·=B·
0··u−1·
0··D·
0·
so A=Bu−1Dand hus Xis pe ec .
We can now p o e he co ec ness o Algo i hm 8.
P oposi ion 5.5. Algo i hm 8 e u ns an opening se o he chain g(γ).
P oo . Le Kbe a CW complex endowed wi h a pe ec HDVF X. Le γbe
a c i ical cell. We ha e o p o e ha Oopens he chain g(γ).
Fi s , le us p o e ha K−Ois a cubical complex. This is equi alen o
p o e ha o any cube in O, i s co aces (in K) a e also included in O. Indeed,
whene e we add a cell o O, we add i s co aces o he queue Q. Le abe
one o hose co aces. I ais p ima y o c i ical, i will be added o Owhen i
is aken om Q. I i is seconda y, i will become c i ical and will be added
again o Q, so i will e en ually be added o O.
We deno e by X′ he esul ing HDVF a he end o he algo i hm. Le us
p o e now ha X′on K−Ois pe ec . By cons uc ion, X′is a HDVF o
K−Oand, since Xis pe ec o K, he esul ollows om Lemma 5.4.
As γdoes no belong o K−Oand he e a e no new c i ical cells, i
ollows ha Oopens he chain g(γ).
Thus, gi en a disc e e objec Oand a hickness-b ead h pai (σ, τ), we
can emo e he homology gene a o associa ed o σusing Algo i hm 8wi h
he HDVF on K[O]ob ained while compu ing he measu es. Howe e , in
p ac ice, i seems ha i su ices o emo e he cohomology gene a o as-
socia ed o σin he HDVF and i s co aces. We ha e pe o med se e al ex-
pe imen s on objec s wi h complex geome y and we ha e ne e ound an
example as Figu e 5.21. No e ha , in ha example, he e a e o he coho-
mology gene a o s which do open he hole. We a e no able o p o e why
his wo ks, o in wha cases i does.
5.5.2 Closing a hole
Closing a hole has also an in ui i e answe which is alse. Le xbe a ho-
mology gene a o in a complex K. I we add a se o cells such ha i s
bounda y is x, hen i becomes a i ial class in he homology g oup. How-
e e , his does no necessa ily close he hole. Le Kbe he bounda y o a
Möbius s ip, which is homo opy equi alen o S1, and x he chain wi h all
i s 1-cells. By adding he in e io o he s ip, xbecomes a bounda y bu
he e is s ill a 1-hole. This is illus a ed in Figu e 5.22.
5.6. Conclusion and u u e wo ks 107
he space (o a leas he con ex hull o he complex) and assign he
signed dis ance ans o m alues o he simplices. The main di icul y
is hus how o de ine/compu e a iangula ion To he space wi h a
pa ame e , as we a e going o compu e an app oxima ion o he mea-
su es in he con inuous space.
109
Chap e 6
Conclusion
APART om he indi idual conclusions in each chap e , we summa ize
he e he main esul s o his essay and, mo e impo an ly, we discuss
he u u e pe spec i es o his wo k. La e we desc ibe wo wo ks ha ha e
no been de eloped in his disse a ion.
6.1 Gene al conclusion
The main goal o his hesis is o s udy disc e e objec s— ha is, bina y im-
ages, olumes o hei equi alen no ions in highe dimensions— om a
homological poin o iew. The ini ial objec i e was o ex end he wo k on
he homological spanning o es de eloped by H. Molina-Ab il and P. Real
[14,91,90], conside ing geome ic ea u es o he disc e e objec s such as
he cu a u e o he medial axis. We will now conside he his o y o each
chap e and he ela ion be ween hem.
6.1.1 Homological Disc e e Vec o Field
The homological spanning o es na u ally led o he concep o he homolog-
ical disc e e ec o ield (HDVF), which has a iche s uc u e and be e
p ope ies. Howe e , inding he co ec de ini ion was a om being a
i ial ask.
When s udying he homological spanning o es we we e disappoin ed
ha i did no wo k well o classical examples in disc e e Mo se heo y
such as he Bing’s house o he dunce ha . The homological disc e e ec o
ield was bo n while s udying he o me . One canno ind a pe ec DGVF
on i since a some poin we ind h ee V-pa hs (ins ead o one) be ween wo
c i ical cells ha should be pai ed and we canno e e se any o hem since
his would c ea e a closed V-pa h in he DGVF. Despi e his, we decided
o e e se one. The ope a o hin a educ ion is he mos impo an since
he o he s a e de ined h ough i . In he educ ion associa ed o a DGVF,
his de ined ecu si ely and hus i is no well de ined i he e a e closed
V-pa hs. We hough ha we could compu e hin e ms o he chains h(σ)
whe e σis a con luence cell, ha is a cell whe e wo o mo e closed V-pa hs
me ge. Hence we ob ain a sys em o linea equa ions, which we ound ha
always had a solu ion. This app oach was published in [57], bu we did no
unde s and why his wo ks and we could no p o e i . We la e ound he
co ec de ini ion inspi ed by he o mula
1 + x+x2+··· =1
1−x
110 Chap e 6. Conclusion
The classical de ini ion o he ope a o his simila o he le side o he
o mula. As in ou case he geome ic sequence ne e anishes, we mus
use he igh side o he o mula. Thus, we need some hing (ac ually a
subma ix o he bounda y ma ices) o be in e ible. We also changed he
o mulas o he educ ion in o de o ha e a clean de ini ion. This is he
o malism we used in [60].
Gi en a CW complex K, a homological disc e e ec o ield is a pai o
disjoin subse s (P, S)o he cells o Ksuch ha he bounda y ma ix o
K es ic ed o hese se s is in e ible. Gi en his p ope y, we can de ine
a educ ion on he chain complex associa ed o K, so we can compu e i s
homology g oups. This de ini ion gene alizes se e al concep s such as he
disc e e g adien ec o ield, he i e a ed disc e e g adien ec o ield and
he educ ion induced by he Smi h no mal o m.
This s uc u e e eals an idea which is no e iden in o he me hods
o compu ing homology. The e a e many possible di e en HDVFs o he
same CW complex. They a e ac ually no comple ely independen , since we
can de ine basic ela ions be ween hem. Thus, a global s uc u e con aining
all he possible HDVFs o a CW complex appea s, which has no been
comple ely unde s ood.
The e is a na u al algo i hm o building a HDVF. We ha e s udied how
o e icien ly compu e he associa ed educ ion and we ha e es ima ed i s
complexi y bo h in heo y and in p ac ice, by conside ing andom cubical
complexes. The esul s show ha he wo s -case complexi y o building a
HDVF is O(n3)bu signi ican ly less in p ac ice.
Open ques ions We ecall ha a HDVF is pe ec i i s associa ed educ-
ion is pe ec , ha is, i i educes he chain complex associa ed o he CW
complex o i s homology g oups.
We do no know i a pe ec HDVF exis s o e e y CW complex. We
ha e ound chain complexes (ac ually jus ma ices) o which his is alse,
so we hink ha he e may be excep ions. Ne e heless, he bounda y ma-
ices o simplicial, cubical o egula CW complex ha e ce ain p ope ies
ha may gua an ee he exis ence o a pe ec HDVF. We ha e ied o ind
a coun e -example by b u e- o ce and we ha e no succeeded. Obse e,
howe e , ha his p oblem is sol ed i he ing o coe icien s is a ield.
The p e ious p oblem assumes ha he conside ed CW complexes ha e
o sion- ee homology g oups, because he e exis s no pe ec educ ion
(and hus, HDVF) o he wise. Howe e , we ha e ound ha he e exis
HDVFs whose educed bounda y ma ix is al eady in he Smi h no mal
o m. Le us call such kind o HDVF a pseudo-pe ec HDVF. Thus, like in
he p e ious pa ag aph, we canno conclude ha any CW complex admi s
a pseudo-pe ec HDVF.
Gi en he ope a ions in oduced in Sec ion 3.7, we could de ine a kind
o edi dis ance [20, § 15] be ween HDVFs. Gi en wo HDVFs, hei dis-
ance can be he minimal numbe o ope a ions A,R,M,W,MW (o a subse
o hem) needed o ans o m one in o he o he . I is no clea ha such
a numbe exis s, since one HDVF may be impossible o ans o m in o an-
o he , so we should conside an ex ended me ic (wi h in ini e alue o
non-connec ed HDVFs). We ind his p oblem ascina ing, hough we can-
no see any p ac ical applica ion o his.
6.1. Gene al conclusion 111
Possibly, he mos use ul pe spec i e o his wo k is o compu e zigzag
pe sis ence homology wi h he HDVF amewo k. We ha e explained in
Sec ion 3.8 how o compu e (s anda d) pe sis en homology wi h HDVFs,
which gi es a e y clea idea o wha pe sis en homology ep esen s. Zigzag
pe sis en homology [13] is a mo e ecen and complex heo y which lacks
a clea in ui ion. We a e wo king on an algo i hm o compu ing zigzag
pe sis en homology using HDVFs and hei ope a ions. The ad an age o
doing his, a he han educing i s complexi y, is o make his heo y clea e
and easie o unde s and.
6.1.2 Fas Compu a ion o Be i Numbe s on Th ee-Dimensional
Cubical Complexes
In o de o compu e he homology g oups o disc e e objec s, one needs o
i s ans o m hem in o cubical complexes. The algo i hm in oduced in
his chap e compu es (only) he Be i numbe s o 3D cubical complexes.
We hus can compu e he Be i numbe s o a disc e e objec in linea ime
wi h ega d o he size o he bounding box.
This algo i hm educes he p oblem o compu ing he Be i numbe s o
coun connec ed componen s in wo g aphs de ined on he cubical complex.
This is p o ed using he HDVF amewo k. The ad an age o he cubical
complex is no only ha we know i s complemen (which is used), bu ha
i s egula s uc u e allows us o easily subdi ide he g aphs in o subg aphs
wi h a easonable numbe o edges be ween hem.
Th ee e sions o his algo i hm ha e been implemen ed depending on
how we coun he numbe o connec ed componen s. E en he slowes one
( he sequen ial e sion) ou pe o ms he lib a y RedHom, specialized in
homological ope a ions on cubical complexes.
Open ques ions Del inado and Edelsb unne ske ched an algo i hm in
[29] o compu ing he Be i numbe s o a simplicial complex embedded in
R3which is no necessa ily a subcomplex o a iangula ion o S3, hough
i is no clea ly p o ed. La e , Dey and Guha p o ed in [32] his algo i hm,
hough complexes no being a h ee-mani old equi e a p e-p ocessing s ep.
The idea is simila o ou algo i hm, excep ha β2is ob ained by ecogniz-
ing closed su aces on he bounda y o he complex. We a e ying o ind
a simple algo i hm and p oo using he HDVF amewo k o bo h simpli-
cial and cubical complexes.
We also aim a compu ing he Be i numbe s di ec ly on a 3D disc e e
objec o he 6 and he 26-connec i i y ela ion. We can do his by building
he associa ed p imal (o dual) cubical complex and using ou algo i hm,
bu i seems easy o do his di ec ly on he disc e e objec . Fo ins ance,
gi en a disc e e objec Xwi h he 6-connec i i y ela ion, β0is he num-
be o connec ed componen s o X,β2is he numbe o connec ed compo-
nen s in i s complemen wi h he 26-connec i i y ela ion (minus he un-
bounded componen ) and he Eule cha ac e is ic can be compu ed locally
in each oxel o X. This idea is al eady p esen in [100], bu he heo e i-
cal ounda ions o his wo k a e no clea . In o de o assign a opological
space o a disc e e objec , we can use he p imal associa ed cubical complex
112 Chap e 6. Conclusion
o he 6-connec i i y and he dual associa ed cubical complex o he 26-
connec i i y. As hese complexes a e locally buil , i is easy o ans e he
calcula ions o ou algo i hm in he cubical complex o he o iginal objec .
Finally, we wan o explo e o he me hods o coun ing connec ed com-
ponen s. In he image p ocessing li e a u e, connec ed componen s labeling
is gene ally pe o med by a e sing he olume in as e scan o de ( i s
inc emen ing he i s coo dina e, hen he second and la e he hi d one)
and making an equi alence able be ween he oxels ha a e adjacen . This
s a egy a oids accessing he oxels in a andom o de (such as while pe -
o ming a b ead h i s sea ch), which p o okes page aul s. We in end o
y hese o he me hods o make ou algo i hm un as e , and also o ea
huge complexes (bigge han 10013) which can be ead by slices in o de o
i in he i ual memo y.
6.1.3 Measu ing Holes
I ook us a long ime o combine digi al geome y and homology. Mo i-
a ed by a p oblem in geos a is ics [23], whe e he Be i numbe s do no
gi e any in o ma ion abou he shape o size o he holes, we de eloped a
simple de ini ion o he size o he holes using he signed dis ance ans o m
and pe sis en homology. I was a g ea su p ise o ind ha holes do no
ha e one na u al measu e bu wo, since we can e ase hem by c acking o
illing hem. Fo una ely, hese measu es a e s able unde small pe u ba-
ions, which makes hem sui able o applica ions whe e objec s come om
acquisi ion de ices o compu e simula ions.
Su p isingly, he compu a ion o hese measu es p o ides a no el ep e-
sen a ion o holes in e ms o balls (ins ead o homology gene a o s) which
we show o be use ul h ough examples. We also include some ecen e-
sea ch abou ob aining homology and cohomology gene a o s and abou
opening and closing holes using hese measu es.
Open ques ions We wan o emphasize h ee pe spec i es abou his e-
sea ch.
The de ini ion o he b ead h and he hickness is no only alid o cu-
bical complexes, bu o any subspace o Rn. We wan o compu e he mea-
su es o simplicial complexes embedded in R3. The challenge is how o
iangula e— e ahed ize, ac ually— he space acco ding o he signed dis-
ance ans o m. We hink ha we can only compu e an app oxima ion o
he measu es, since we can only compu e he signed dis ance ans o m in
a ini e numbe o poin s. We a e con inced ha compu ing small gene a-
o s o (co)homology and opening o closing holes in his con ex will gi e
be e esul s since he ou pu is no es ic ed o i in he g id.
While he p oblem o inding small homology gene a o s has been la gely
s udied om a compu a ional poin o iew, ha o closing and opening
holes seems o be o e looked. We do no aim a p o ing ha inding a
minimal closing o opening se is a NP p oblem, bu we belie e i is.
E en hough he measu es we e concei ed o sol e a p ac ical p oblem
(s udying he holes o di e en ypes o soils), we eally do no ha e any
applica ion o hem. Speci ic needs may gi e new ideas, such as using
di e en dis ances. In pa icula , some ecen wo ks [108,109,113] s udy
6.2. O he wo ks 113
he shape o he uni e se h ough pe sis en homology, and we hink ha
he b ead h and he hickness may be use ul o his.
6.2 O he wo ks
We p esen he e wo wo ks ha a e no desc ibed in his hesis o di e en
easons.
6.2.1 Cellula skele ons
One o he main heo ems in disc e e Mo se heo y s a es ha a simplicial
complex endowed wi h a DGVF is homo opy equi alen o a CW complex
wi h exac ly one q-cell o each c i ical q-simplex. F om a opological poin
o iew, he skele on o a disc e e objec is a subse which is homo opy equi -
alen . Thus, i is clea ha a DGVF—mo eo e , a educ ion—p o ides a
kind o skele on o a disc e e objec .
In [58] we in oduced he concep o cellula skele on. Gi en a educ ion
om he p imal (o dual) associa ed cubical complex o a disc e e objec , i
is he se o chains g(C). Taking Z2as ing o coe icien s, each chain is a
se o cells comp ehending a mani old-like pa o he skele on. Thus, his
is no jus a subse o oxels bu a chain complex.
FIGURE 6.1: Cellula skele on o Fe ili y.
These skele ons we e compu ed using known algo i hms o homo opy
hinning o cubical complexes such as [84,41,16,21,22]. Then we used a
cell clus e ing algo i hm o educe he numbe o cells wi hou changing he
shape o he skele on. Figu e 6.1 shows an example o he isualiza ion o a
cellula skele on.
The cellula skele on has se e al ad an ages. On one hand, he esul -
ing skele on p ese es he opology o he o iginal objec since i is de ined
h ough a educ ion. On he o he hand, since he p e iously men ioned
algo i hms gi e (hope ully) cen e ed skele ons, hus a subsequen homol-
ogy compu a ion on he cellula skele on should gi e cen e ed homology
gene a o s which, hough no minimal, a e isually pleasan .
The cell clus e ing algo i hm was no ully unde s ood in [58]. I akes a
3D cubical complex as inpu and i e u ns a educ ion. We la e concei ed
a gene al e sion o any dimension and we p o ed ha e e y maximal
114 Chap e 6. Conclusion
(wi hou co aces) cell o he complex belongs o one and only one chain
g(γ). This implies ha he shape o he skele on does no change. On he
o he hand, he esul ing skele on is no unique (since he e a e mul iple
choices in he algo i hm) and i does no always e u n a minimal (in he
numbe o cells) skele on. These esul s ha e no been published, bu hey
seem o be equi alen o he wo ks o Damiand e al. [25,24] in he con ex
o gene alized maps.
Sadly, we did no ad ance mo e in his di ec ion due o he lack o p ac-
ical applica ions o his heo y.
6.2.2 Opening holes in disc e e objec s
The e is a simple way o closing he holes o a disc e e objec . Le Xbe a 3D
disc e e objec wi h he 26-connec i i y. Conside an acyclic olume Y⊃X
con aining i (i s bounding box, o ins ance) and emo e simple poin s—
ha is, oxels ha can be emo ed wi hou changing he homo opy ype o
he objec —in Y−Xun il idempo ency. The inal olume con ains Xand
has no holes since i is homo opy equi alen o Y, so i closes he holes o
X. Gi ing p io i y o oxels which a e u he om he objec usually gi es
minimal illings. This has been s udied in [1,71,72].
Inspi ed by he duali y in he measu es (see Chap e 5), we would like
o open holes in disc e e objec s. A simple algo i hm consis s in conside ing
a poin xinside he objec and hen adding simple poin s in he objec un il
idempo ency. The objec ob ained is a subse o he o iginal objec wi hou
holes. Again, conside ing he dis ance ans o m o he o de in which he
poin s a e added should gi e a minimal esul .
Simple examples in 2D such as hose in Figu e 6.2 show ha his na u al
app oach does no gi e op imal ac u es. Ins ead o ob aining he minimal
cu s opening he holes, he ac u es seem o ollow some angles.
FIGURE 6.2: Resul o he same image wi h di e en eso-
lu ion. The cu s in he igu e on he igh ha e been hick-
ened o isibili y.
This idea is e y ecen and we ha e no had ime enough o de elop i .
We decided o include i he e o i s simplici y and possible u u e pe spec-
i es. We plan o explo e mo e ad anced echniques o opening holes ha
con e ge o he minimal cu s.
115
Bibliog aphy
[1] Zouina Ak ou , Gilles Be and, and Lau en Pe o on. A h ee-
dimensional holes closing algo i hm. Pa e n Recogn. Le ., 23(5):523–
531, Ma ch 2002.
[2] Madjid Allili and Da id Co i eau. Topological analysis o shapes
using Mo se heo y. Compu e Vision and Image Unde s anding,
105(3):188–199, 2007.
[3] Ra ael Ayala, Desampa ados Fe nández-Te ne o, and José An onio
Vilches. Pe ec disc e e Mo se unc ions on 2-complexes. Pa e n
Recogn. Le ., 33(11):1495–1500, Augus 2012.
[4] B uno Benede i and F ank H. Lu z. Random disc e e Mo se he-
o y and a new lib a y o iangula ions. Expe imen al Ma hema ics,
23(1):66–94, 2014.
[5] Ainhoa Be ciano, Helena Molina-Ab il, and Ped o Real. Sea ching
high o de in a ian s in compu e image y. Appl. Algeb a Eng. Com-
mun. Compu ., 23(1-2):17–28, 2012.
[6] R. H. Bing. Some aspec s o he opology o 3-mani olds ela ed o he
Poinca é conjec u e. Lec u es on Mode n Ma hema ics, 2, 1964.
[7] Jean-Daniel Boissonna , Tamal K. Dey, and Clémen Ma ia. The com-
p essed anno a ion ma ix: An e icien da a s uc u e o compu ing
pe sis en cohomology. Algo i hmica, 73(3):607–619, 2015.
[8] Dob ina Bol che a, Sa a Me ino Acei unos, Jean-Claude Léon, and
F anck Hé oy. Cons uc i e Maye -Vie o is algo i hm: Compu ing
he homology o unions o simplicial complexes. Resea ch Repo
RR-7471, INRIA, Decembe 2010.
[9] Gunilla Bo ge o s. Dis ance ans o ma ions in a bi a y dimensions.
Compu e Vision, G aphics, and Image P ocessing, 27(3):321–345, 1984.
[10] Pee -Timo B eme , Ing id Ho z, Vale io Pascucci, and Ronald Peik-
e , edi o s. Topological Me hods in Da a Analysis and Visualiza ion III,
Theo y, Algo i hms, and Applica ions. Sp inge , 2014.
[11] Pio B endel, Paweł Dło ko, G aham Ellis, Ma eusz Juda, and Ma -
ian M ozek. Compu ing undamen al g oups om poin clouds.
Applicable Algeb a in Enginee ing, Communica ion and Compu ing,
26(1):27–48, 2015.
[12] Kenne h S. B own and Ross Geoghegan. An in ini e-dimensional
o sion- ee FP∞g oup. In en iones ma hema icae, 77(2):367–381, 1984.
[13] Gunna Ca lsson and Vin Sil a. Zigzag pe sis ence. Founda ions o
Compu a ional Ma hema ics, 10(4):367–405, 2010.
116 BIBLIOGRAPHY
[14] Ja ie Ca ne o, Helena Molina-Ab il, and Ped o Real. T iangle mesh
comp ession and homological spanning o es s. In Compu a ional
Topology in Image Con ex - 4 h In e na ional Wo kshop, CTIC 2012, Be i-
no o, I aly, May 28-30, 2012. P oceedings, pages 108–116, 2012.
[15] Manoj K. Cha i. On disc e e Mo se unc ions and combina o ial de-
composi ions. Disc e e Ma hema ics, 217(1–3):101–113, 2000.
[16] John Chaussa d and Michel Coup ie. Su ace hinning in 3D cubi-
cal complexes. In Pe a Wiede hold and Rene a P. Ba ne a, edi o s,
Combina o ial Image Analysis, olume 5852 o Lec u e No es in Compu e
Science, pages 135–148. Sp inge Be lin Heidelbe g, 2009.
[17] Chao Chen and Daniel F eedman. Measu ing and compu ing na u al
gene a o s o homology g oups. Compu . Geom., 43(2):169–181, 2010.
[18] Chao Chen and Daniel F eedman. Ha dness esul s o homology
localiza ion. Disc e e & Compu a ional Geome y, 45(3):425–448, 2011.
[19] Da id Cohen-S eine , He be Edelsb unne , and John Ha e . S a-
bili y o pe sis ence diag ams. Disc e e & Compu a ional Geome y,
37(1):103–120, 2006.
[20] Thomas H. Co men, Cli o d S ein, Ronald L. Ri es , and Cha les E.
Leise son. In oduc ion o Algo i hms. McG aw-Hill Highe Educa ion,
2nd edi ion, 2001.
[21] Michel Coup ie. Hie a chic Euclidean skele ons in cubical com-
plexes. In Disc e e Geome y o Compu e Image y - 16 h IAPR In e -
na ional Con e ence, DGCI 2011, Nancy, F ance, Ap il 6-8, 2011. P oceed-
ings, pages 141–152. 2011.
[22] Michel Coup ie. Topological maps and obus hie a chical Euclidean
skele ons in cubical complexes. Compu e Vision and Image Unde -
s anding, 117(4):355–369, 2013.
[23] Asmae Dah abou, Sophie Viseu , Aldo Gonzalez-Lo enzo, Je emy
Rohme , Alexand a Bac, Ped o Real, Jean-Luc Ma i, and Pascal Audi-
gane. Topological compa isons o lu ial ese oi ock olumes us-
ing Be i numbe s: Applica ion o CO2s o age unce ain y analysis.
In 6 h In e na ional Wo kshop on Compu a ional Topology in Image Con-
ex (CTIC 2016), Lec u e No es in Compu e Science (LNCS 9667), pages
101–112. Sp inge In e na ional Publishing, 2016. DOI:10.1007/978-
3-319-39441-1_10.
[24] Guillaume Damiand, Rocío González-Díaz, and Samuel Pel ie . Re-
mo al ope a ions in nD gene alized maps o e icien homology
compu a ion. In Compu a ional Topology in Image Con ex - 4 h In e -
na ional Wo kshop, CTIC 2012, Be ino o, I aly, May 28-30, 2012. P o-
ceedings, pages 20–29, 2012.
[25] Guillaume Damiand, Samuel Pel ie , and Lau en Fuchs. Compu ing
homology gene a o s o olumes using minimal gene alized maps.
In Combina o ial Image Analysis, 12 h In e na ional Wo kshop, IWCIA
2008, Bu alo, NY, USA, Ap il 7-9, 2008. P oceedings, pages 63–74, 2008.
BIBLIOGRAPHY 123
[110] J. R. S allings. Lec u es on polyhed al opology. Ta a Ins i u e o Fun-
damen al Resea ch, Bombay, 1968.
[111] A ne S o johann. Nea op imal algo i hms o compu ing Smi h no -
mal o ms o in ege ma ices. In P oceedings o he 1996 In e na ional
Symposium on Symbolic and Algeb aic Compu a ion, ISSAC ’96, pages
267–274, New Yo k, NY, USA, 1996. ACM.
[112] Takashi Te amo o and Yasumasa Nishiu a. Mo phological cha ac e -
iza ion o he diblock copolyme p oblem wi h opological compu a-
ion. Japan Jou nal o Indus ial and Applied Ma hema ics, 27(2):175–190,
2010.
[113] Rien an de Weygae , Ge Veg e , He be Edelsb unne , Be na d
J. T. Jones, P a yush P ana , Changbom Pa k, Wojciech A. Hellwing,
Bob Elde ing, Nico K ui ho , E. G. P. (Pa ick) Bos, Johan Hidding, Job
Feldb ugge, Eline en Ha e, Ma i an Engelen, Manuel Ca oli, and
Monique Teillaud. T ansac ions on compu a ional science XIV. chap-
e Alpha, Be i and he Megapa sec Uni e se: On he Topology o
he Cosmic Web, pages 60–101. Sp inge -Ve lag, Be lin, Heidelbe g,
2011.
[114] Uzi Vishkin. An op imal pa allel connec i i y algo i hm. Disc e e
Applied Ma hema ics, 9(2):197–207, 1984.
[115] Hube Wagne , Chao Chen, and E ald Vuçini. E icien compu a ion
o pe sis en homology o cubical da a. In Ronald Peike , Helwig
Hause , Hamish Ca , and Raphael Fuchs, edi o s, Topological Me hods
in Da a Analysis and Visualiza ion II, Ma hema ics and Visualiza ion,
pages 91–106. Sp inge Be lin Heidelbe g, 2012.
[116] Michael We man and Ma hew L. W igh . In insic olumes o an-
dom cubical complexes. Disc e e & Compu a ional Geome y, 56(1):93–
113, 2016.
[117] E.C. Zeeman. On he dunce ha . Topology, 2(4):341–358, 1963.
[118] A a Zomo odian and Gunna Ca lsson. Localized homology. Com-
pu . Geom. Theo y Appl., 41(3):126–148, No embe 2008.
[119] A a Zomo odian and Gunna E. Ca lsson. Compu ing pe sis en ho-
mology. Disc e e & Compu a ional Geome y, 33(2):249–274, 2005.
