Towa ds Op imali y in Disc e e Mo se Theo y h ough
Chain Homo opies ∗
Ped o Real, Helena Molina-Ab il
Uni e si y o Se illa, Depa men o Applied Ma hema ics, Se illa, Spain.
[email p o ec ed], [email p o ec ed]
Abs ac Once a disc e e Mo se unc ion has been de ined on a ini e cell complex, in o -
ma ion abou i s homology can be deduced om i s c i ical elemen s. The main objec i e o
his pape is o de ine op imal disc e e g adien ec o ields on gene al ini e cell complexes,
whe e op imali y en ails ha ing he leas numbe o c i ical elemen s. Ou app oach is o
conside his p oblem as a homology compu a ion ques ion o chain complexes endowed
wi h ex a algeb aic nilpo en ope a o .
Keywo ds: Disc e e Mo se Theo y, cell complex, in eg al-chain complex, chain homo opy, g aph,
homology, g adien ec o ield.
1 In oduc ion
Mo se heo y has been conside ed a powe ul ool in i s applica ions o compu a ional opology,
compu e g aphics and geome ic modeling. In [5] Fo man o mula es a e sion o his heo y o
disc e e s uc u es such as cell complexes. The aim o Disc e e Mo se Theo y is o ind simplicial
collapses ha ans o m K o a smalle complex. This heo y elies ei he on admissible unc ions
on a cell complex, called disc e e Mo se unc ions, o equi alen ly hei g adien ec o ield.
Fo man p o ed ha he opology o a cell complex can be pa ly ead ou o he c i ical cells
o a disc e e g adien ec o ield de ined on i . A g adien ec o ield is op imal i i has he
minimum possible numbe o c i ical cells. The opological in o ma ion o he ini ial cell complex
will be concise i he disc e e g adien ec o ield has ew c i ical cells.
In [10] he au ho s de eloped a heu is ic o compu ing op imal Mo se ma chings. This heu is ic
compu es op imal g adien ec o ields o combina o ial 2–mani olds. Howe e , o gene al cell
complexes his p oblem has no been sol ed ye .
In his pape we eco e all he algeb aic machine y unde lying in Disc e e Mo se Theo y,
es ablishing a new amewo k o dealing wi h special chain complexes associa ed o ini e cell
complexes.
This can be done using an essen ially algeb aic amewo k in which “homological o es s” (see
[11]) de ined on he ini ial cell complex a e con enien ools in o de o ob ain he minimum
numbe o c i ical cells, ha is, he minimal homological exp ession o he ini ial complex. The
idea he e is o classi y chain homo opies as g adien ec o ields on a ini e cell complex.
The pape is o ganized as ollows: In Sec ion 2 some basic de ini ions a e in oduced. The
heo e ical undamen s o ou wo k is de ailed in Sec ion 3. In Sec ion 4 he ela ion be ween his
algeb aic machine y and he op imali y in Disc e e Mo se Theo y a e s ablished. We inish he
pape wi h some conclusions.
.
∗This wo k has been pa ially suppo ed by ”Compu a ional Topology and Applied Ma hema ics” PAICYT
esea ch p ojec FQM-296, ”Andalusian esea ch p ojec PO6-TIC-02268 and Spanish MEC p ojec MTM2006-
03722
33
2 P eliminai es
In his sec ion, we in oduce some basic de ini ions in o de o unde s and ou algeb aic– opological
app oach.
Fi s , we es ablish a no ion o (combina o ial) cell complex in a ini e–dimensional Euclidean
space wi h he cell bounda y in o ma ion desc ibed in algeb aic e ms. This objec can be iden i ied
wi h he chain complex canonically associa ed o a cell complex such ha he homology o i
coincides wi h he singula homology o he cell complex. In ac , he geome ic ealiza ion o such
cell complex in a ini e–dimensional Euclidean space has a ep esen a ion in e ms o a pa icula
ype o egula cell complex (see [9] o a deep s udy o cell-complexes). Simplicial, cubical and
polyhed al complexes a e, pa icula cases o cell complexes.
The ollowing de ini ions a e necessa y in o de o classi y chain homo opies as g adien ec o
ields on a ini e cell complex.
The ing o coe icien s Λis a commu a i e ield ( o example, a ini e ield, he a ional
numbe s, he eal numbe s,...). Le {x1,x
2, ..., xn}be a ini e se o symbols. We deno e by
Λ[x1, . . . , xn] he module o o mal linea combina ions λ1x1+λ2x2+. . . λnxn, wi h λi∈Λ.
Le "be a posi i e in ege . Le B!={x∈E!s. . |x|≤1) be he closed uni ball in he
"-dimensional Euclidean space E!. The bounda y o B!is he uni ("−1)-sphe e S(!−1) and he
in e io o B!, deno ed by In B!, is he open uni "-dimensional ball In B!={x∈E!s. . |x|<1}.
Ap-cell in E!(wi h 0 <p≤") is a subse o E!which is homeomo phic o he open uni ball
In Bp( ha is, o Rp).
A 0–cell is a a opological space homeomo phic o a poin o a ini e-dimensional Euclidean
space. The dimension o a p-cell σis |σ|=pand he no a ion σ(p)will indica e ha σis a cell
o dimension p. The union as poin se o a se o cells Kin E!is called he ca ie o Kand i is
deno ed by |K|. Le us de ine he bounda y o a p-cell σas ∂σ =σ σ, whe e σis he closu e o
σ. To indica e ela ionships be ween cells, we w i e τ>σ(o σ<τ) and we say ha σis a ace
o τi σ%=τand σ⊂¯τ, whe e ¯τis he closu e o τ. We w i e τ≥σi ei he τ=σo τ>σ. The
s a o a cell σconsis s o all cells ha ing σas a ace, including σi sel , and he link consis s o all
aces o cells in he s a ha a e disjoin om σ.
S σ={τ∈K|σ<τ}
Lk σ={ ∈K| <τ∈S σ, ∩σ=∅}.
Acell complex K={Ki}!
i=0 embedded in E!is a ini e collec ion o cells {σ( )i=1,...n
i∈K }o
di e en dimensions 0 ≤ ≤"such ha :
(i)
|K|=
n
!
i=1
σi=|K0|∪|K1|∪. . . ∪|K!|
. The se K consis s o all he -cells o K, o 0 ≤ ≤". I is possible ha Ki=∅ o
some 0 <i≤".
(ii)
σi∩σj=∅(i%=j);
(iii) I dim(σi)=p(wi h 0 ≤p≤"), hen ∂σi⊂"p−1
i=1 Ki,
The p-skele on K(p) o Kis he se o all k-cells wi h 0 ≤k≤p. The dimension o he cell
complex is he smalles na u al numbe such ha he condi ion K( )=K( +1) is sa is ied. I all
he cells o Ka e con ex se s o E!, hen Kis called con ex cell complex. Simplicial, Cubical and
some polyhed al complexes a e special cases o con ex cell complexes. A cell complex is speci ied
by he “ ace pose ”, he pa ial o de de e mined by he cells and i s bounda y ela ions.
Roughly speaking, he idea o homology is o analyze he deg ee o connec i i y o cell com-
plexes using o mal sums o cells. A di e en ial ope a o o a cell complex Kwi h coe icien s in
34
Λis a linea map d:Λ[K]→Λ[K], such ha he image o a p-cell σis a linea combina ion o
some (p−1)-cells o he bounda y ∂(σ) and d◦d= 0. Taking in o accoun ha ou cell complex
Kis embedded in E!, i s geome ic ealiza ion |K|is a egula iangulable cell complex and he e
can be always de ined a di e e en ial ope a o ∂, called bounda y ope a o , wi h coe icien s in he
ield Λ, ha comple ely de e mines he singula homology o |K|.
The chain complex canonically associa ed o he cell complex Kis he g aded di e en ial ec o
space (C∗(K),∂), whe e Cp(K)=Λ[Kp], o all p=0,1,... , and ∂:C∗(K)→C∗−1(K) is he
p e ious bounda y ope a o o he cell complex K. Fo ins ance, o ind a bounda y ope a o ∂
o a simplicial complex is s aigh o wa d, bu i is no , in gene al, an easy ask o o he s cell
complexes. The ollowing is one o he undamen al esul s in he heo y o CW-complexes.
Theo em 1 (Fo man).Le Ka ini e cell complex. The e a e algeb aic bounda y maps ∂p:
Cp(K, Λ)→Cp−1(K, Λ), o each p, so ha ∂p−1◦∂p=0and such ha he esul ing di e en-
ial complex {Cp(K, Λ),∂p}
p=0 calcula es he homology o K. Tha is, i we de ine Hp(C, ∂)=
Ke (∂p)/∂p+1(C). In o he wo ds, Hp(C, ∂)∼
=Hp(|K|,Λ).
F om now on, a ini e cell complex Kwill be deno ed by (K, ∂), whe e ∂:C∗(K)→C∗−1(K)
is he bounda y ope a o o K.
3 Algeb aic Disc e e Mo se Theo y
The aim o Disc e e Mo se Theo y is o ind simplicial collapses ha ans o m a complex K o a
smalle one. This can be done using an essen ially algeb aic amewo k in which disc e e Mo se
unc ions a e con enien ools o keep ack o he collapses, and in which o de hey a e done.
Now, we eco e all he algeb aic machine y unde lying in Disc e e Mo se Theo y, es ablishing
a new amewo k o dealing wi h special chain complexes associa ed o ini e cell complexes and
we show ha a con enien combina o ial ool o sol ing he homological compu a ion p oblem in
his a ea is ha o a ee.
De ini ion 1. An in eg al chain complex (C, d, φ)is a g aded module C={Cp}n
p=0 endowed wi h
wo linea maps: a di e en ial ope a o d:C∗→C∗−1, and an in eg al ope a o (also called
algeb aic g adien ec o ield [5] o chain homo opy ope a o [4]) φ:C∗→C∗+1, sa is ying
he global nilpo ency p ope ies d◦d=0and φ◦φ=0. An in eg al chain complex (C, d, φ)is
d-pu e ( esp. φ-pu e) i he condi ion d=d◦φ◦d, called homology condi ion ( esp. he condi ion
φ=φ◦d◦φ, called s ong de o ma ion e ac condi ion) is sa is ied. An in eg al chain complex
(C, d, φ) ha is bo h, d-pu e and φ-pu e, is called homology in eg al chain complex.
De ini ion 2. Gi en wo in eg al chain complexes (C, d, φ)and (C#,d
#,φ#),amap o in eg al chain
complexes ( , g):(C, d, φ)⇒(C#,d
#,φ#)is a couple o linea maps :C→C#and g:C#→C
such ha ◦d=d#◦ ,g◦d#=d◦g, ◦φ=φ#◦ ,g◦φ#=φ◦g.(C, d, φ)and (C#,d
#,φ#)
a e in eg al chain equi alen i he e exis s a map o in eg al chain complexes ( , g), such ha
id C− ◦g=π(d#,φ#)and idC!−g◦ =π(d, φ). The homology H∗(C, d, φ)o an in eg al
chain complex (C, d, φ)is he g aded abelian g oup H∗(C), such ha (H∗(C),0,0) is in eg al chain
equi alen o (C, d, φ). The di e en ial ( esp. in eg al) homology o an in eg al chain complex
(C, d, φ)is he homology o (C, d, 0) ( esp. he homology o (C, 0,φ)). I (C, d, φ)is a homology
in eg al-chain complex, hen H∗(C, d, φ)∼H∗(C, d, 0) ∼H∗(C, 0,φ).
The se o in eg al chain complexes ( esp. he se o pu e in eg al chain complexes) and hei
co esponding maps o m a ca ego y. In ac , he in eg al chain equi alence ela ion can be seen
as he na u al ex ension o he classical chain homo opy equi alence be ween chain complexes o
he in eg al case (see, o example, [4]).
E ec i e Homology [13] is a heo y in which he homology compu a ion p oblem is de e mined
in e ms o an explici chain homo opy equi alence be ween a chain complex (C, d) and i s ho-
mology. In ac , using ou e minology he e ec i e homology o he chain complex (C, d, 0) can
35
be desc ibed as an algeb aic in eg al ope a o φ, such ha (C, d, φ) is in eg al-chain equi alen o
(C, d, 0).
On he o he hand, Disc e e Mo se Theo y (DMT, o sho ) gi es a posi i e answe o he
p oblem o inding combina o ial chain homo opy ope a o s φ o chain complexes (C∗(K),d) o
ini e cell complexes, such ha he in eg al homology o (C∗(K), d, φ) is a “good” app oxima ion
(measu ed in e ms o c i ical cells) o i s di e en ial homology. The minimum numbe o c i ical
cells in each deg ee is de e mined by he Be i numbe s (weak Mo se inequali ies).
The compu a ion o he homology o a chain complex (C, d) is speci ied in e ms o inding an
in eg al ope a o φ:C∗→C∗+1, sa is ying he S ong De o ma ion Re ac (SDR o sho ) and
homology condi ions wi h ega ds, o he di e en ial ope a o d([7, 8]).
The no ion o pu e in eg al chain complex (C, d, φ) is unde lying in he wo k o Se ge ae [13],
Fo man [5, 6] and ha o Theo y o Disc e e Di e en ial Fo ms [2].
P oposi ion 1. Le (C, d, φ)an in eg al chain complex. Le π:C∗→C∗be he linea map,
(called low o (C, dφ)), de ined by π=idC−d◦φ−φ◦dand le ∆:(C∗,d)→C∗be he linea
map, called Laplacian o (C, dφ), de ined by ∆=d◦φ+φ◦d. Then, he ollowing p ope ies holds:
(a) d◦π=d−d◦φ◦d=π◦dand φ◦π=φ−φ◦d◦φ=π◦φ. In he case o a homology
in eg al chain complex, d◦π= 0 = π◦dand φ◦π= 0 = π◦φ.
(b) d◦∆=d◦φ◦d=∆◦dand φ◦∆=φ◦d◦φ=∆◦φ. In he case o a homology in eg al
chain complex, d◦∆=d=∆◦dand φ◦∆=φ=∆◦φ.
(c) Gi en a p-chain a, we ha e he ollowing equali y a=π(a)+∆(a).
(d) π2=π−φ(d−d◦φ◦d)−(d−d◦φ◦d)◦φ=π−d(φ−φ◦d◦φ)−(φ−φ◦d◦φ)d. The
in eg al chain complex π(C, d, φ) = (π(C),d|π(C),φπ(C))is he ha monic complex associa ed
o (C, d, φ). I (C, d, φ) is a d-pu e o a φ-pu e in eg al chain complex, hen π2=π◦π=π
and π(C)={x∈C|x=π(x)}. In o he wo ds, he ha monic complex (π(C),d|π(C),0)
associa ed o a pu e in eg al chain complex (C, d, φ) is o med by he π-equi a ian s chains
o C. I (C, d, φ) is a homology in eg al chain complex, i s ha monic complex is o he kind
(π(C),0,0) and he chain map πdesc ibes o each p-chain a ep esen a i e cycle o he
di e en ial ( esp. in eg al) homology class associa ed o his p-chain.
(e) ∆2=(d+φ)∆(d+φ). The in eg al chain complex ∆(C, d, φ)=(∆(C),d|∆(C),φ|∆(C)) is he
Laplacian complex associa ed o (C, d, φ). I (C, d, φ) is a d-pu e o φ-pu e in eg al chain
complex, hen ∆◦∆=∆and ∆(C)={x∈C|x=∆(x)}. In o he wo ds, he Laplacian
complex ∆(C, d, φ) associa ed o a pu e in eg al chain complex (C, d, φ) is o med by all he
∆-equi a ian s chains.
( ) π◦∆=(d−d◦φ◦d)◦φ+φ◦(d−d◦φ◦d)=d(φ−φ◦d◦φ)+(φ−φ◦d◦φ)d=∆π.
P oposi ion 2. I (C, d, φ)is a (di e en ial o in eg al) pu e in eg al-chain complex, we can
de i e he ollowing p ope ies:
(p1) π◦∆= 0 = ∆◦π.
(p2) (C, d, φ)=π(C, d, φ)⊕∆(C, d, φ)as in eg al-chain complexes. In pa icula , Ke ∆=π(C)
and ∆(C) = Ke π.
(p3) ∆(C)=φ(C)⊕d◦φ)(C)as g aded modules.
In o de o emphasize he dependency o πand ∆wi h ega ds dand φ, we will deno e hese
maps by π(d,φ)and ∆(d,φ), espec i ely.
The ollowing p oposi ion will be undamen al in de eloping an in eg al-chain amewo k o
Disc e e Mo se Theo y. In ac , i shows ha o use pu e in eg al ope a o s as chain homo opies
decomposing a ini ely gene a ed chain complexes is a key poin :
36
P oposi ion 3. I (C, d, φ)is a (di e en ial o in eg al) pu e in eg al-chain complex, we ha e ha
Ke φ∼
=π(C)⊕φ(C)∼
=Ke ∆(C)⊕φ(C)
as g aded modules.
In pa icula , a map o in eg al-chain complexes ( , g) sa is y ha ◦π(d,φ)=π(d!,φ!) ,g◦
π(d!,φ!)=π(d,φ)◦g, ◦∆(d,φ)=∆(d!,φ!)◦ and g◦∆(d!,φ!)=∆(d,φ)◦g. Tha is, and ga e
compa ible wi h ega ds o he espec i e lows and Laplacians.
In spi e o i s simplici y, he ollowing esul is essen ial o de eloping ou homological heo y
o in eg al-chain complexes:
Lemma 1. [In eg al-Chain Lemma] An in eg al chain complex (C, d, φ)is in eg al-chain equi -
alen o i s ha monic complex π(C, d, φ). This las ha monic complex π(C, d, φ)is o he o m
(π(C),d
π,φπ)whe e dπ(π(x)) = (d−d◦φ◦d)(x)and φπ(π(x)) = (φ−φ◦d◦φ)(x).
P oo . Le :C→π(C) be he linea map de ined by (x)=π(x), ∀x∈C∗. Le g:π(C)→C
be he linea map de ined by g(x)=x,∀x∈π(C). Then, i is a simple exe cice o show ha ( , g)
is a couple o maps o in eg al chain complexes which induces he in eg al-chain equi alence. The
es o asse ions can be di ec ly deduced om P oposi ion 1 (a).
!
Co olla y 1. The ha monic complex π(C, d, φ)associa ed o a d-pu e ( esp. φ-pu e) in eg al-chain
complex (C, d, φ)is o he o m (π(C),0,φπ)( esp. (π(C),d
π,0)), whe e φπ(π(x)) = (φ−φ◦φ◦)(x)
( esp. dπ(π(x)) = (d−d◦φ◦d)(x)).
Now, we gi e some de ini ions ela ed o in eg al-chain pe u ba ion o complexes.
De ini ion 3. An in eg al chain complex (C, d, φ)is called di e en ial ( esp. in eg al poin wise
nilpo en ) i o any a∈C he e is some n(a)∈Nwi h d(1 −d◦φ−φ◦d)n(a)=0( esp. wi h
φ(1 −d◦φ−φ◦d)n(a)=0). The smalles alue o n(a)is e e ed o as he deg ee o di e en ial
( esp. in eg al) nilpo ency o a.
P oposi ion 4 (Fo man).Gi en an in eg al ( esp. di e en ial) poin wise nilpo en in eg al chain
complex (C, d, φ)is in eg al chain equi alen o a φ-pu e ( esp. d-pu e) in eg al chain complex
(C, d, ˜
φ)( esp. (C, ˜
d, φ)).
P oo . We only p o e he exis ence o he φ-pu e in eg al chain complex (C, d, ˜
φ). The o he
esul can be de i ed di ec ly om he ac ha (C, φ,d) is also a poin wise nilpo en in eg al-
chain complex. De ine ˜
φ:C∗→C∗+1 by ˜
φ=#k≥0φ◦(1−d◦φ)k. This is well de ined due o he
poin wise nilpo ency o (C, d, φ), since all bu ini ely many e ms anish on he igh hand side.
The map ˜
φis 2-nilpo en (˜
φ◦˜
φ= 0) and sa is ies he SDR p ope y ˜
φ◦d◦˜
φ=˜
φ. The couple o
maps (π(d, ˜
φ),idC) es ablish he in eg al chain equi alence be ween (C, d, φ) and (C, d, ˜
φ). !
Finally, we de ine he composi ion o an in eg al-chain complex.
De ini ion 4. Gi en a d-pu e ( esp. wo φ-pu e) in eg al-chain complexes (C, d, φ)and a di e -
en ial ope a o d#sa is ying he homology condi ion ( esp. an in eg al ope a o φ#sa is ying he
s ong de o ma ion e ac condi ion) o π(d,φ)(C), a new d-pu e ( esp. φ-pu e) in eg al chain
complex (C, d +d#◦π(d,φ),φ)( esp. (C, d, φ+φ#◦π(d,φ))) can be cons uc ed. This new in eg al
chain complex is called composi ion o (C, d, φ)by φ#.Ad-pu e in eg al chain complex (C, d, φ)
can su e composi ion wi h ega ds o he own di e en ial ope a o d( esp. wi h ega d o he own
in eg al ope a o φ) es ic ed o π(d,φ)(C).
F om now on, all he in eg al chain complexes we conside in he pape will be in eg al poin wise
nilpo en s. Analogous esul s can be de e mined o di e en ial poin wise nilpo en .
In he nex sec ion, we de ine some no ions in o de o do he link wi h he algeb aic wo k
unde lying in Disc e e Mo se Theo y.
37

4 Disc e e Mo se Theo y and op imali y
Disc e e Mo se Theo y gi es a posi i e answe o he p oblem o inding combina o ial chain
homo opy ope a o s φ o chain complexes (C∗(K),d) o ini e cell complexes, such ha i s in eg al
homology H(C, 0,φ) is a “good” app oxima ion o i s di e en ial one H(C, d, 0). Using Pe sis en
Homology [3] Be i numbe s can be g adually de e mined om a il e ed chain complex.
We will show he e ha Homological Pe u ba ion Theo y can be used as a ool o eaching
in e es ing combina o ial esul s in DMT ( o example, abou g adien pa hs). Mo e p ecisely, he
homology o a chain complex (C, d) can be speci ied in DMT in e ms o inding a combina o ial
in eg al ope a o φ:C∗→C∗+1 de i ed om disc e e Mo se unc ions and sa is ying he SDR
condi ion wi h ega ds, o he di e en ial ope a o d.
De ini ion 5. Le (K, ∂)a ini e cell complex. An ope a o :C∗(K)→C∗± (K)is said o be
combina o ial i ∀p-cell σ(p), (σ(p))=λβ
(p± ), whe e λ∈Zand βis a (p± )−cell.
Tha is, in DMT we sea ch o a combina o ial ope a o φsuch ha (C(K), d, φ) is a φ-pu e
in eg al-chain complex.
Gi en a cell complex K, he in eg al-chain complex canonically associa ed o Kis (C(K),∂,)),
whe e ∂is he bounda y o di e en ial ope a o o C∗(K) and ):C∗(K)→C∗+1(K) is he
cobounda y ope a o de ined by )(α(p))=Σ<∂β,α>β, whe e he sum is aken o all he cells
β(p+1), such ha a∈∂(β) (i.e. apa icipa es in a non-null manne in he linea combina ion
∂(β)). In DMT, we sea ch o a combina o ial ope a o φwhich can be de i ed (choosing one
summand in he o mula o ) o each cell) such ha he numbe o c i ical cells in (C(K),∂,φ)
is minimal.
Now, we gi e some basic no ions o DMT wi h some sligh ly modi ica ions and wi hou using,
in p inciple, disc e e Mo se unc ions.
De ini ion 6. [5, 6] A combina o ial in eg al ope a o Vde ined on a cell complex Kis a collec ion
o disjoin pai s o (non-necesa ly inciden ) cells {α(p)<β(p+1)}. I he pai s a e cons i u ed by
inciden cells hen, Vis called combina o ial ec o ield. We will ep esen a combina o ial ec o
ield by an a ow om he cell o lowe dimension o i s pai ed cell o highe dimension. A
combina o ial ec o ield can be seen as a pa ial ma ching in he Hasse diag am o K.AV-pa h
o g adien pa h γis an al e na ing sequence o cells a(p)
0,b
(p±1)
0,a
(p)
1,b
(p±1)
1,a
(p)
2, . . ., such ha o
each pai o consecu i e simplices, one is a maximal ace o he o he , and he ollowing condi ion
is sa is ied: one o he couples {a(p)
i<b
(p±1)
i}o {b(p±1)
i<a
(p)
i+1}belongs o V,∀i≥0. I he inal
cell in he g adien pa h γabo e is α(p)
, hen we say ha γhas leng h . I i ends wi h β(p±1)
hen we say ha γhas leng h 1
2. I he cells bio he g adien pa h γa e o dimension p+1 and
i has leng h 1
2, he g adien pa h γis called uppe V- pa h o uppe g adien pa h. Fo any cells
aand b, le Γ(a, b)deno e he se o g adien pa hs om a o b(o any leng h), i.e., such ha he
i s cell in he sequence is aand he las cell in he sequence is b.AV-pa h is non i ial and
closed i ≥1and he i s and las cells in he sequence a e he same. A closed V-pa h is jus an
o ien ed ci cui in he Hasse diag am. A cell αis a c i ical cell o Vi i is no pai ed wi h any
o he cell in V.
The numbe o c i ical cell depends on he disc e e g adien ec o ield conside ed. Fo man
p o ed [5, 6] ha he opology o a disc e e mani old is ela ed o he c i ical elemen s o a disc e e
unc ion de ined on i , micmicking he esul s o Mo se in he smoo h case. In [10], he p oblem
o he op imali y (minimizing he numbe o c i ical cells o combina o ial ec o ields) on a
2-mani old is analyzed using Hasse diag am and hype g aph ools. The e o e, a disc e e g adien
ec o ield is a special kind o combina o ial in eg al ope a o .
Fi s , he combina o ial in eg al ope a o s de i ed om combina o ial ec o ields a e φ-
poin wise nilpo en .
P oposi ion 5. A combina o ial ec o ield Vgi es ise o a φ-poin wise nilpo en in eg al-chain
complex (C(K), d, V ).
38
Le us emphasize ha wo pai s {a, b}and {a#,b
#}o Vha e no elemen s in common. The
combina o ial ec o iel Vgi es ise o a linea map V:C∗(K)→C∗+1(K), de ined by V(a)=b
i {a, b}∈Vand V(a) = 0, in he es o cells. I is clea ha V◦V= 0. The map Vis an
in eg al ope a o o C∗(K). To p o e ha (C(K), d, V ) is φ-poin wise in eg al-chain complex is
s aigh o wa d. !
Combining P op. 1, P op. 2 and P op. 3, we asse he ollowing esul which is he key o
ein e p e ing DMT in in eg al-chain e ms:
P oposi ion 6. I (C, d, φ)is a φ-poin wise nilpo en in eg al-chain complex being φa combina-
o ial ec o ield, hen he e is an in eg al-chain equi alen φ-pu e complex (C, d, ˜
φ), such ha
i s ha monic complex π(C, d, ˜
φ) = ( Ke ˜
φ ˜
φ(C),d
π,0). This las in eg al-chain complex is con-
s i u ed by ini e linea combina ions o he di e en c i ical cells o φand dπcan be seen as he
bounda y ope a o o he co esponding cell complex de e mined by he c i ical cells, also called
ha monic Mo se cell complex M(C, d, φ)associa ed o (C, d, φ). Analogously, he Laplacian com-
plex ∆(C, d, ˜
φ)can be seen as he acyclic chain complex o he cell complex M(C, d, φ), also called
Laplacian Mo se complex associa ed o (C, d, φ). Mo eo e , i s bounda y ope a o ∂Mis de e -
mined by ∂M(∆(σ(p))) = d◦˜
φ◦d(σ(p)),∀σ(p)∈C.
P oo . Due o P op. 3 and P op. 1 and de ining ˜
φ:C∗→C∗+1 by ˜
φ=#
k=0 φ◦(1 −d◦φ)k=
#
k=0(1 −φ◦d)kφ, we ha e ha
( , g) : Ke ˜
φ ˜
φ(C)∼
=π(C, d, ˜
φ)
is an isomo phism o chain complexes, wi h : Ke ˜
φ ˜
φ(C)→π(C, d, ˜
φ) and g:π(C, d, ˜
φ)→
Ke ˜
φ ˜
φ(C) espec i ely de ined by (σ)=π(d, ˜
φ)(σ)=σ−˜
φ◦d(σ), ∀σ∈: Ke ˜
φ ˜
φ(C) and
g(π(d, ˜
φ))(β)) = β−d◦˜
φ(β), ∀β∈C.
Now, le us p o e ha Ke ˜
φ= Ke φand ˜
φ(C)=φ(C).
I is clea ha Ke φ⊂Ke ˜
φ. Le x∈Ke ˜
φbe an elemen such ha x/∈Ke φ. Tha
means ha #
k=0 π(d, φ)k(x)∈Ke φ. Tha implies ha φ(1 −π +1)(x)=φ(d◦φ+φ◦d)◦
$#
k=0 π(d, φ)k%(x) = 0 and, hen φ(x)=φπ +1(x) = 0. In a simila manne , i is possible o
deduce ha ˜
φ(C)=φ(C) and ha i also admi s a combina o ial basis.
Le us now p o e ha he chain complex (˜
φ(C)⊕(d◦˜
φ)(C),d) is acyclic. We ha e ha
d(˜
φ(C)) ⊂(d◦˜
φ)(C) and d((d◦˜
φ))(C) = 0. Now, le us suppose ha he e is a chain x=
x#+x## ∈˜
φ(C)⊕(d◦˜
φ)(C) such ha d(x) = 0. This means ha d(x#) = 0. Since x#=˜
φ(z), hen
(d◦˜
φ)(z) = 0. Due o he ac ha he in eg al ope a o sa is y he SDR condi ion ˜
φ◦d◦˜
φ=˜
φ,
we conclude ha x#= 0.
Finally, he bounda y ope a o o M(C, d, φ) is he di e en ial ope a o d es ic ed o i and
i s acyclici y can be p o ed using P op. 3.
!
Le us no e ha H∗(M(C, d, φ)) ∼
=H∗(K, Λ). Mo eo e , he bounda y ope a o dπo he
Mo se cell complex M(C, d, φ) ha e a clea in e p e a ion in e ms o g adien pa hs o ˜
φ.
P oposi ion 7. In he condi ions o P op. 6, and gi en a p-cell α,˜
φ(α)is an uppe g adien
φ-pa h.
In [12, 1], a homology in eg al ope a o φis de e mined om a il e ed cell complex using
an inc emen al echnique. The homology in eg al ope a o φgi es ise in a na u al way o a
combina o ial in eg al unc ion on K. Using spanning homological o es s echniques [11] and
cancella ion–like heo ems [6] in ol ing g adien pa hs, we can conclude ha ob aining a combi-
na o ial ec o ield on Kis s aigh o wa d.
39
5 Conclusions
In his pape “homological o es s” a e p esen ed as an use ul ool owa ds he op imalli y o a
combina o ial g adien ec o ield de ined o e a ini e cell complex. Rela ions be ween E ec i e
Homology echniques and Disc e e Mo se Theo y ha e been es ablished, and a common dic iona y
o e ms has been de ined. This algeb aic amewo k allows us o ensu e he “ educ ion” o he
ini ial complex o i s minimal homological exp ession. The in oduced s uc u e allows a di ec
ansi ion om he in eg al ope a o compu ed o e a cell complex, o a minimal combina o ial
g adien ec o ield.
Re e ences
[1] A. Be ciano, H. Molina-Ab il, A. Pacheco, P. Pila czyk, and P. Real. Decomposing ca i ies in
digi al olumes in o p oduc s o cycles. In S ecko B lek, Ch is ophe Reu enaue , and Xa ie
P o en¸cal, edi o s, DGCI, olume 5810 o Lec u e No es in Compu e Science, pages 263–274.
Sp inge , 2009.
[2] M. Desb un, E. Kanso, and Y. Tong. Disc e e di e en ial o ms o compu a ional modeling.
In SIGGRAPH ’06: ACM SIGGRAPH 2006 Cou ses, pages 39–54, New Yo k, NY, USA,
2006. ACM.
[3] H. Edelsb unne , D. Le sche , and A. Zomo odian. Topological pe sis ence and simpli ica ion.
Disc e e Compu . Geom., 28:511–533, 2002.
[4] S. Eilenbe g and S. Mac Lane. On he g oups h(π,n), i, ii, iii. Annals o Ma h, 58, 60,
60:55–106,48–139, 513–557, 1953,1954.
[5] R. Fo man. A Disc e e Mo se Theo y o Cell Complexes. Topology and Physics o Raoul
Bo , S.T. Yau, ed., In e na ional P ess., 1995.
[6] R. Fo man. Mo se heo y o cell complexes. Ad . In Ma h., 134:90–145, 1998.
[7] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. S ashe . Pe u ba ion heo y in di e en ial
homological algeb a. Illinois J. Ma h, 33:357–373, 1989.
[8] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. S ashe . Pe u ba ion heo y in di e en ial
homological algeb a. ii. Illinois J. Ma h., 35(3):357–373, 1991.
[9] R. Kle e. Cell complexes h ough ime. Communica ion and In o ma ion Technology Re-
sea ch Technical Repo , 60, 2000.
[10] T. Lewine , H. Lopes, G. Ta a es, and L. Ma m´ıdia. Towa ds op imali y in disc e e Mo se
heo y. Expe imen al Ma hema ics, 12:2003, 2003.
[11] H. Molina-Ab il and P. Real. Homological compu a ion using spanning ees. In Edua do
Bay o-Co ochano and Jan-Olo Eklundh, edi o s, CIARP, olume 5856 o Lec u e No es in
Compu e Science, pages 272–278. Sp inge , 2009.
[12] P. Real, H. Molina-Ab il, and W.G. K opa sch. Homological ee-based s a egies o image
analysis. In Xiaoyi Jiang and Nicolai Pe ko , edi o s, CAIP, olume 5702 o Lec u e No es
in Compu e Science, pages 326–333. Sp inge , 2009.
[13] F. Se ge ae . The compu abili y p oblem in algeb aic opology. Ad ances in Ma hema ics,
104:1–29, 1994.
40