Jou nées du G oupe de a ail de géomé ie disc è e, Reims Image 2014
Ex ac ion d’in o ma ion homologique des obje s disc e s
s’appuyan su des g aphes o ien és
Aldo Gonzalez-Lo enzo1,2, Alexand a Bac1, Jean-Luc Ma i1e Ped o Real2
1Aix-Ma seille Uni e si é, CNRS, LSIS UMR 7296 (F ance)
2Uni e si é de Sé ille, Ins i u de Ma héma iques IMUS (Espagne)
Résumé
Tou obje disc e n-dimensionnel peu ê e ans o mé en complexe cubique, don on peu é udie les g oupes
d’homologie pou mieux comp end e l’obje o iginal. Une app oche classique consis e à calcule la Fo me
No male de Smi h de ma ices encodan le complexe cubique. Un ce ain nomb e de a aux dé eloppen des
mé hodes pe me an de édui e la aille de ces ma ices.
Dans ce a icle, nous p oposons une nou elle app oche, ini ialemen ondée su la héo ie disc è e de Mo se,
calculan l’in o ma ion homologique (nomb es de Be i e cycles ep ésen a i s) sans u ilise la Fo me No male
de Smi h. No e app oche s’applique en dimension quelconque e peu ê e u ilisée pou n’impo e quel ype de
complexe cellulai e égulie .
n-dimensional disc e e objec s can be in e p e ed as cubical complexes which a e sui able o he s udy o hei
homology g oups in o de o unde s and he o iginal disc e e objec . The classic app oach consis s in compu ing
he No mal Smi h Fo m o some ma ices ha encode he cubical complex. Fu he app oaches deal mainly wi h
a p e-p ocessing o hese ma ices in o de o educe hei size.
In his pape we p opose a new app oach, ini ially based on Disc e e Mo se Theo y, which compu es some
homological in o ma ion (Be i numbe s and ep esen a i e cycles) wi hou calcula ing he No mal Smi h Fo m.
I wo ks on any dimension, and i can also be applied o any kind o egula cell complex.
Mo s clé : obje disc e , complexe cubique, homologie,
héo ie de l’homologie e ec i e, héo ie disc è e de Mo se.
1. In oduc ion
L’homologie s’es é élée comme un ès bon ou il pou
la classi ica ion e la comp éhension des obje s disc e s, no-
ammen quand ils on plus de ois dimensions. Elle ou ni
une classe de desc ip eu s qui syn hé isen la s uc u e ba-
sique de la o me considé ée.
L’homologie o malise la no ion de « ou » dans un ob-
je . On peu classi ie les « ous » pa leu dimension : les
0- ous son les composan es connexes; les 1- ous, les un-
nels e les 2- ous, les ca i és. Le calcul de l’in o ma ion ho-
mologique a pou bu , en e au es, de dé e mine le nomb e
de ces ous (nomb e de Be i) e un ep ésen an de chacun
(cycle ep ésen a i ou géné a eu d’homologie). Cela es e
in ui i jusqu’à ois dimensions, mais en dimension qua e,
on peu ou e des coe icien s de o sion dans les g oupes
d’homologie, ce qui n’a pas une in e p é a ion in ui i e mais
pe me cependan une classi ica ion des obje s. Le calcul de
l’homologie nécessi e le choix p éalable d’un anneau de co-
e icien s; a in de nous place dans le cas le plus géné al e
de pou oi ob eni ces coe icien s de o sion, nous a ons
choisi l’anneau des en ie s.
Ce a ail s’appuie su deux app oches an é ieu es : la
héo ie de l’homologie e ec i e [Se 92] e la héo ie disc è e
de Mo se [Fo 02]. La p emiè e explici e le lien en e l’ob-
je o iginal e ses g oupes d’homologie (mais s’a è e d’une
complexi é éle ée, puisque basée su des ma ices ypique-
men géan es de aille O(n2)où nes le nomb e de cellules
du complexe). La deuxième app oche es en e anche ès
simple e de complexi é beaucoup plus aible, mais ne pe -
me pas oujou s de calcule l’homologie exac e.
Dans ce a icle, nous p oposons une app oche qui com-
bine ces deux héo ies, en en conse an les a an ages ou
en dépassan leu s limi a ions espec i es. Nous cons uisons
un obje qui géné alise le champ de ec eu s g adien disc e
(ou il p incipal de la héo ie disc è e de Mo se) en au o i-
san les cycles, ce qui pe me de calcule l’homologie exac e
(e pas seulemen une app oxima ion). Tenan comp e de ces
cycles, on ob ien la éduc ion (ou il p incipal de la héo ie
de l’homologie e ec i e) elian le complexe cubique e ses
c
GéoDis 2014, G oupe de T a ail de Géomé ie Disc è e (h p://www.gd -im. )
Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és
g oupes d’homologie. Ce e éduc ion donne les géné a eu s
de l’homologie.
Ce e mé hode s’applique en dimension quelconque e à
n’impo e quel ype de complexe cellulai e égulie .
Pou plus de dé ails su l’é a de l’a e le con ex e an de
la héo ie des complexes cellulai es que de l’homologie, le
lec eu pou a se epo e à no e a icle [GLBMR].
2. P éliminai es
Dans ce e sec ion nous in oduisons les concep s néces-
sai es.
Un obje disc e de dimension nes un ensemble de cubes
n-dimensionnels don le cen e a des coo données en iè es.
Les complexes cubiques son p ésen és de maniè e dé-
aillée dans [KMM04]. Un complexe cubique es un ype de
complexe cellulai e don les cellules son des poin s (dimen-
sion 0), des a ê es (dimension 1), des ca és (dimension 2),
des cubes (dimension 3), e c. Le bo d d’une cellule de di-
mension q(q-cellule) es l’ensemble de (q−1)-cellules de
sa on iè e.
Un complexe cubique peu ê e dé ini pa son diag amme
de Hasse. C’es un g aphe o ien é où les somme s son les
cellules du complexe, e les a cs on d’une cellule e s les
cellules de son bo d.
La açon la plus simple de dé ini un complexe cubique
à pa i d’un obje disc e consis e à emplace chaque cube
de l’obje pa une n-cellule a ec ses sous-cellules de dimen-
sion in é ieu e. Une cons uc ion duale consis e à emplace
chaque cube pa un poin (0-cellule) e ajou e des cellules de
dimension supé ieu e selon la ela ion d’adjacence en e les
cubes. Ce e de niè e cons uc ion u ilise moins de cellules,
ce qui end les mé hodes de calcul de l’homologie plus pe -
o man es. La igu e 1 mon e ces deux cons uc ions à pa i
d’un même obje disc e .
Un complexe de chaînes (C∗,d∗)es une séquence de
g oupes C0,C1,... (appelés g oupes de chaînes) e d’ho-
momo phismes d1:C1→C0,d2:C2→C1,... (appe-
lés opé a eu s di é en iels ou de bo d) elle que dq−1dq=
0,∀q>0. On peu cons ui e une complexe de chaînes à pa -
i d’un complexe cubique : les g oupes de chaînes son les
g oupes lib es engend és pa les cellules de chaque dimen-
sion ; l’opé a eu de bo d su une cellule donne une combi-
naison linéai e des cellules de son bo d. La o mule exac e
es explici ée dans [KMM04].
Le q-ème g oupe d’homologie du complexe de chaînes
(C∗,d∗)es le g oupe quo ien H(C)q=ke (dq)/im(dq+1).
Ce g oupe es isomo phe à
Zβq×Z/λ1Z×Z/λ2Z×... ×Z/λ Z,
où chaque λidi ise λi+1.βqes le q-ème nomb e de Be i
e λ1,...,λ son appelés coe icien s de o sion. Rappelons
que si le complexe cubique es de dimension 3, il n’y a pas
de coe icien s de o sion.
La héo ie de l’homologie e ec i e in odui la no ion de
éduc ion : é an donné deux complexes de chaînes (C∗,d∗)
e (C0
∗,d0
∗), une éduc ion es un iple d’homomo phismes
(h∗, ∗,g∗) el que :
—hq:Cq→Cq+1pou chaque q≥0
— q:Cq→C0
qes un mo phisme de chaînes ( d =d0 )
—gq:C0
q→Cqes aussi un mo phisme de chaînes
(gd0=dg)
—g =1−dh −hd
— g =1C0
—hh =h =hg =0
Une éduc ion es une so e de simpli ica ion d’un complexe
de chaînes (le deuxième complexe con ien no malemen des
g oupes don les bases son plus pe i es) p ése an l’in o -
ma ion homologique e ou nissan un lien en e le complexe
ini ial e le complexe simpli ié. Quand le deuxième com-
plexe es su isammen simple pou ne plus con eni que les
g oupes d’homologie, il ou ni alo s les géné a eu s d’ho-
mologie du complexe ini ial.
Dans la sui e de ce e pa ie, nous p ésen ons b iè emen
les no ions de base de la héo ie disc è e de Mo se. Pou
une in oduc ion plus igou euse, le lec eu pou a consul-
e [Fo 02].
Un champ de ec eu s disc e (disc e e ec o ield, DVF)
su un complexe cubique es un couplage su son diag amme
de Hasse, c’es -à-di e un sous-g aphe de ce de nie don au-
cune des a ê es ne pa age un même somme . É an donné
un champ de ec eu s disc e V, le g aphe de Mo se es
cons ui à pa i du diag amme de Hasse, en en e san les
lèches du sous-g aphe V. Les lèches issues de Vson alo s
appelées in ég ales, les au es, lèches di é en ielles. Un V-
chemin es un chemin su le g aphe de Mo se qui al e ne des
lèches in ég ales e di é en ielles. Ainsi, un champ de ec-
eu s disc e qui ne con ien pas de V-chemins e més es un
champ de ec eu s g adien disc e (disc e e g adien ec o
ield, DGVF). Une cellule c i ique es une cellule non cou-
plée dans le champ de ec eu s g adien disc e .
L’un des ésul a s ondamen aux de la héo ie disc è e de
Mo se es que le nomb e de q-cellules c i iques es supé-
ieu ou égal au q-ème nomb e de Be i. Quand les nomb es
de Be i coïnciden a ec le nomb e de cellules c i iques, on
di que le champ de ec eu s g adien disc e es pa ai .
Malheu eusemen , pou ce ains complexes cellulai es, un
el DGVF n’exis e pas; on appelle alo s op imal un DGVF
con enan un nomb e minimal de cellules c i iques (qui peu
donc ê e supé ieu au nomb e de Be i).
A pa i d’un champ de ec eu s g adien disc e , on peu
calcule une éduc ion associée. On dé ini ou d’abo d
l’opé a eu linéai e sui an :
V(σ) = (hd(τ),σi· τ,(σ,τ)es dans le couplage
0,sinon
où hd(τ),σies le coe icien de la cellule σdans la chaîne
d(τ). On pose alo s :
h(σ) = ∑k≥0V(1−dV)k(σ) = V(σ)+ h(1−dV)(σ)
(σ) = (1−dh −hd)(σ) = (1−dV)(σ)
g(σ) = σ
(1)
3. No e app oche
No e objec i es de dépasse les limi a ions de la héo ie
disc è e de Mo se en ob enan l’in o ma ion homologique
c
GéoDis 2014.
Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és
Figu e 1: Un obje disc e de dimension 3 e ses deux complexes cubiques associés. No ons que dans le deuxième il y a deux
composan es connexes.
exac e à pa i d’un champ de ec eu s g adien disc e ; c’es
une app oche pu emen combina oi e (pa opposi ion aux
app oches algéb iques) qui, de plus, encode une éduc ion
sous o me de g aphe. Cependan , il a é é p ou é que dé e -
mine un DGVF op imal dans le cas géné al es un p oblème
NP [LLT03] e que pou ce ains complexes, il n’exis e pas
de DGVF pa ai (pa exemple, la maison de Bing e le
« dunce ha », oi [AFTV12]). Pou ésoud e ce p oblème,
no e app oche epose su l’en ichissemen des DGVF pa
des cycles (soigneusemen choisis e con ôlés). Nous appel-
le ons ce ype de champ de ec eu s disc e un champ de
ec eu s disc e homologique (homological disc e e ec o
ield, HDVF).
Sans en e dans les dé ails, no e app oche es la sui-
an e : é an donné un obje disc e , nous cons uisons son
complexe cubique associé e é ablissons un p emie champ
de ec eu s g adien disc e quelconque. Puis, no e algo-
i hme es basé su la co ec ion i é a i e de ce g aphe.
Chaque co ec ion élimine deux cellules c i iques en en e -
san un V-chemin en e elles, ce qui peu c ée des V-chemins
e més. On peu à ou momen calcule la éduc ion asso-
ciée au champ de ec eu s disc e homologique en u ilisan
les o mules écu si es (1).
Ob eni l’image pa hou d’une cellule σpa ce e o -
mule écu si e e ien à ai e un pa cou s du g aphe de
Mo se à pa i de σ. Puisque no e HDVF peu con eni des
cycles, il es nécessai e d’a ê e le pa cou s au bon mo-
men . Nous in oduisons la no ion de somme de con luence
(somme où deux cycles o ien és se ejoignen ) pou é-
soud e ce p oblème. No e pa cou s s’a ê e donc aux som-
me s de con luence, p oduisan un sys ème d’équa ions li-
néai es (illus é dans l’exemple sui an ), que nous ésol ons
pou ob eni la aleu de hou en σ.
À i e d’exemple, considé ons le complexe de la igu e 2.
On peu no e qu’il y a ois V-chemins (en o ange) en e les
deux cellules c i iques de dimension 1 e 2.
Lo squ’on calcule d su la 2-cellule c i ique, on e-
ou e la 1-cellule c i ique; s’il n’y a ai qu’un V-chemin
en e elles, on pou ai donc les annule (comme en héo-
ie disc è e de Mo se), c’es -à-di e, en e se ce V-chemin
a in qu’elles ne soien plus c i iques. Cependan , dans ce
exemple, il y a ois V-chemins en e elles. Il es donc néces-
Figu e 2: Champ de ec eu s g adien disc e (en ouge) su
un complexe cubique. Il y a ois cellules c i iques en bleu,
une de chaque dimension.
sai e d’en choisi un (ici, nous p enons le plus cou ), ce qui
c ée deux cycles o ien és.
Si l’on souhai e, à pa i de ce g aphe, calcule l’opé a eu
h(ou ) on doi d’abo d dé e mine sa aleu su le somme
de con luence (nommé c, ma qué en iole dans la igu e 3).
On ob ien alo s une équa ion du ype :
h(c) = 2·h(c)+ x⇒h(c) = −x(2)
où xes la chaîne ob enue du an le pa cou s (non explici ée
ici). Pa simple ésolu ion de ce e équa ion, on ob ien alo s
la aleu de h(c), qu’on u ilise ensui e pou le calcul de hen
ou e cellule σ(le pa cou s depuis σes a ê é au somme de
con luence ce la aleu de h(c)es alo s subs i uée dans la
o mule écu si e).
Dans le cas géné al on ob ien une équa ion pou chaque
somme de con luence, p oduisan ainsi un sys ème d’équa-
ions linéai es. Une ois ce p ocessus de co ec ion e miné,
le nomb e de cellules c i iques dans chaque dimension coïn-
cide a ec les nomb es de Be i s’il n’y a pas de coe icien s
c
GéoDis 2014.
Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és
Figu e 3: Le champ de ec eu s disc e (homologique) ap ès
le en e semen du V-chemin. Le somme de con luence es
ma qué pa un poin iole .
de o sion. Le cas où il y a des coe icien s de o sion e-
quie des explica ions plus p écises, mais n’appo e pas de
di icul és supplémen ai es. En in, on peu ob eni les géné-
a eu s d’homologie en appliquan =1−dh −hd su les
cellules c i iques.
Les igu es 4 e 5 mon en deux exemples classiques où
nous calculons un champ de ec eu s disc e homologique.
Le complexe (simplicial) pou le « dunce ha » a é é ob enu
de [Hac]. No e algo i hme a é é implémen é en C++ a ec
les lib ai ies DG al [DG ] e Eigen [Eig].
Figu e 4: Hau : un DGVF su la maison de Bing. Bas : le
HDVF ap ès la co ec ion du DGVF p écéden . Il y a une
seule cellule c i ique (en bleu).
Figu e 5: Hau : DGVF su le « dunce ha » a ec ois cel-
lules c i iques. Bas : le HDVF ap ès la co ec ion du DGVF
p écéden . L’unique cellule c i ique es 1. Les deux cycles
o ien és du g aphe de Mo se son a ichés en iole .
4. Conclusion
Nous p ésen ons une géné alisa ion du champ de ec-
eu s g adien disc e pou laquelle nous in oduisons un al-
go i hme pe me an d’ob eni les nomb es de Be i ainsi
que des géné a eu s d’homologie. No e ésul a n’es pas
seulemen héo ique, mais une mé hode e icace de calcul
de l’in o ma ion homologique. Dans les deux exemples bien
connus de la maison de Bing e du « dunce ha », no e algo-
i hme abou i à un nomb e co ec de cellules c i iques dans
chaque dimension (co espondan aux nomb es de Be i).
c
GéoDis 2014.
Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és
Ré é ences
[AFTV12] AYALA R., FERNÁNDEZ-TERNERO D.,
VILCHES J. A. : Pe ec disc e e Mo se unc ions on
2-complexes. Pa e n Recogn. Le .. Vol. 33, Num. 11
(aoû 2012), 1495–1500.
[DG ] DG al : Digi al geome y ools and algo i hms li-
b a y. h p://dg al.o g.
[Eig] Eigen. h p://eigen. ux amily.o g.
[Fo 02] FORMAN R. : A use ’s guide o disc e e Mo se
heo y. Séminai e Lo ha ingien de Combina oi e. Vol. 48
(2002), B48c.
[GLBMR] GONZALEZ-LORENZO A., BAC A., MARI J.-
L., REAL P. : Compu ing homological in o ma ion based
on di ec ed g aphs wi hin disc e e objec s.
[Hac] HACHIMORI M. : Simplicial complex li-
b a y. h p://in oshako.sk. sukuba.ac.jp/
~hachi/ma h/lib a y/index _eng.h ml.
[KMM04] KACZYNSKI T., MISCHAIKOW K., MROZEK
M. : Compu a ional Homology, ol. 157. Sp inge , 2004,
ch. 2, 7, pp. 255–258.
[LLT03] LEWINER T., LOPES H., TAVARES G. : Towa d
op imali y in disc e e Mo se heo y. Expe imen al Ma he-
ma ics. Vol. 12, Num. 3 (2003), 271–285.
[Se 92] SERGERAERT F. : E ec i e homology, a su -
ey. h p://www- ou ie .uj -g enoble. /
~se ge a /Pape s/Su ey.pd , 1992.
c
GéoDis 2014.