P oc. o he 5 h In . Wo kshop on Disc e e Geome y o Compu e Image y DGCI95.
Cle mon –Fe and, F ance, Sep embe 1995. 1
ON SURFACES IN DIGITAL TOPOLOGY
R. Ayala∗, E. Dom´ınguez∗∗, A.R. F anc´es∗∗, A. Quin e o∗, J. Rubio∗∗
∗Dep . de Algeb a, Compu aci´on, Geome ´ıa y Topolog´ıa. Uni e sidad de Se illa.
Facul ad de Ma em´a icas. Apa ado de Co eos: 1160. E-41080 Se illa (SPAIN)
e-mail: [email p o ec ed]
∗∗Dep . de In o m´a ica e Ingenie ´ıa de Sis emas. Uni e sidad de Za agoza.
Facul ad de Ciencias. Edi icio de Ma em´a icas. E-50009 Za agoza (SPAIN)
e-mail: [email p o ec ed] , [email p o ec ed]
Abs ac : In [Ayala∞] a new amewo k o digi al opology has been p oposed.
This amewo k o e s he possibili y o ans e ing, in an easy way, de ini ions,
s a emen s and p oo s om con inuous opology o digi al opology (see de ails
in §2). In pa icula , i p o ides a s aigh o wa d de ini ion o n-dimensional
digi al mani old.
In his pape we p o e ha he class o digi al 2-mani olds wi hou bounda y
in he g id ZZ3ag ees wi h he class o (26,6)-su aces de ined by Kong-Roscoe
and o he au ho s ([Mo gen hale 81],[Reed84],[Kong85]). As a consequence, he
sepa a ion heo em o digi al su aces s a ed in [Mo gen hale 81] and [Reed84]
is ob ained.
Keywo ds: digi al opology, digi al su aces
1 In oduc ion
In [Ayala∞] a new amewo k o digi al opology has been p oposed. In his
amewo k, he pixels on a compu e sc een a e ep esen ed by means o a
polyhed al complex. Associa ed o his polyhed al complex, h ee di e en
models ( he logical, concep ual and con inuous models) a e de ined and hese
models allow us o ans e , in an easy way, de ini ions, s a emen s and p oo s
om con inuous opology o digi al opology (see de ails in §2). In pa icula ,
his amewo k p o ides a s aigh o wa d de ini ion o n-dimensional digi al
mani old in such a way ha closed digi al 1-mani olds in he g id ZZ2co espond
o he well-known digi al Jo dan cu es in Rosen eld’s sense ([Rosen eld79]). In
his pape we p o e ha he class o digi al 2-mani olds wi hou bounda y
in he g id ZZ3ag ees wi h he class o (26,6)-su aces de ined by Kong-Roscoe
and o he au ho s ([Mo gen hale 81],[Reed84],[Kong85]). As a consequence, he
sepa a ion heo em o digi al su aces s a ed in [Mo gen hale 81] and [Reed84]
is ob ained.
I mus be poin ed ou ha Kong and Roscoe ac ually de ine (α, β)-su aces
o α, β ∈ {6,18,26}. O hese su aces, howe e , all excep (18,6), (6,18),
(26,6), and (6,26) a e usually disca ded on he g ounds ha hei es ic ions
on he g id ZZ2×{0} ⊂ ZZ3p oduce he pa adoxical 8 o 4-adjacency ela ions
2 On Su aces in Digi al Topology
o ZZ2. Ou cha ac e iza ion sugges s ha , among he non-pa adoxical (α, β)-
su aces, he (26,6)-su aces a e mo e likely o p o ide a heo y o ZZ3which
as nea ly as possible eplica es ha o IR3.
2 Digi al Topology and polyhed al complexes
In his pape Kwill deno e a locally ini e and homogeneously n-dimensional
polyhed al complex. Namely, Kis a complex o con ex cells (poly opes) such
ha each poly ope is ace o a ini e numbe (non-ze o) o n-poly opes. I
σ∈K, he bounda y o he poly ope σis he se ∂σ union o i s aces. The
in e io o σis he se ◦
σ=σ−∂σ.
I |K|deno es he unde lying polyhed on o K, a cen oid-map is a map
c:K→ |K|such ha c(σ)∈◦
σ. The poin c(σ) is called cen oid o σand he
pai (K, c) is called de ice model. Gi en (K, c), we de ine an undi ec ed g aph
L(K,c)(o simply LK) whose e ices a e he cen oids o n-poly opes in Kand
wo e ices a e adjacen s in LKi hei co esponding n-poly opes in e sec .
The g aph LKis called he logical model o K.
The dig aph CK, called concep ual model o K, is de ined as ollows. I s
e ices a e hose o LKand, in addi ion, he cen oids c(σ) such ha σis he
in e sec ion o wo o mo e n-poly opes o K. The di ec ed edges a e pai s
(c(τ), c(σ)) wi h τ ace o σ. I no con usion a ises, we iden i y each cen oid
c(σ) wi h he co esponding poly ope σ, and he de ice model (K, c) wi h he
polyhed al complex K.
Adigi al objec in a de ice model Kis a subse Oo he se o cen oids o
n-poly opes o K. F om he subg aph o LKgene a ed by O, deno ed i(O), we
de ine he subg ah pi(O) o CKgene a ed by he e ices o i(O) oge he wi h
he cen oids o poly opes which a e he in e sec ion o wo o mo e n-poly opes
associa ed o e ices o i(O).
Example 1 In his pape we shall deal wi h he s anda d cubical decomposi ion
o IRn,Kn. Tha is, he de ice model de e mined by he collec ion o uni n-
cubes in IRnwhose edges a e pa allel o he coo dina e axes and whose cen e s
a e he poin s o ZZn⊂IRn. The cen oid-map associa es o each cube σi s
cen e c(σ). Thus a digi al objec in Knco esponds o a subse o ZZn.
A subse C⊂Ois called a componen o he digi al objec Oi i(C) is a
connec ed componen o i(O). On he o he hand, i Ocdeno es he complemen
o Oin he se o n-poly opes o K, a subse D⊂Ocis called a DIG-componen
o Oci Dis he se o cen oids o Ocwhich belong o a connec ed componen
o CK−pi(O).
The con inuous analogue |AO|o a digi al objec Ois he unde lying poly-
hed on o he o de complex AOassocia ed o he g aph pi(O). Tha is,
hx0, x1, . . . , xmiis a m-simplex o AOi x0x1. . . xmis a di ec ed pa h in he
dig aph pi(O). This simplicial complex admi s a polyhed al inme sion in K
and hus |AO|can be conside ed a subpolyhed on o |K|. I is easy o e i y
ha he e exis s a bijec i e map be ween he se o DIG-componen s o he
complemen Ocand he se o connec ed componen s o he opological space
Ayala e al. 3
|AK| − |AO|. In ac , each DIG-componen D⊂Ocis de e mined by he
n-poly opes in pi(Oc)∩A, whe e Ais a connec ed componen o |AK|−|AO|.
A digi al objec Ois a digi al mani old i |AO|is a combina o ial mani old.
I |AO|only is a opological mani old hen Ois called a weak digi al mani-
old. In he s anda d cubical decomposi ion K2o IR2, a digi al objec Ois
a closed digi al 1-mani old i and only i Ois a 8-cu e in Rosen eld’s sense
(see [Ayala∞] and [Rosen eld79]). In §3 he ela ionship be ween he digi al
2-mani olds in K3and he no ion o su ace due o Kong-Roscoe and o he
au ho s ([Mo gen hale 81],[Reed84],[Kong85]) is s udied.
Le us s a e he e a e sion o a Gene alized Digi al Jo dan Theo em, which
can be easily p o ed by using he co esponding con inuous esul (III.11.17 in
[Massey78], o example) and ou p e ious de ini ions.
Theo em 2 (Gene alized Digi al Jo dan Theo em) Le Kbe a polyhe-
d al complex such ha |K|= IRn. I a digi al objec Oin Kis a weak digi al
(n−1)-mani old wi hou bounda y, hen he complemen Ocis di ided in wo
DIG-componen s. Mo eo e , i Ois ini e hen one DIG-componen is ini e.
3 Digi al 2-mani olds and (26,6)-su aces
Le K3be he s anda d cubical decomposi ion o IR3. Gi en a cube σ∈K3,
le N(σ) deno e he se o cubes in K3which mee σ(σi sel included). A
cube µ∈N(σ) is said o be a 26-neighbou o σ. The cube µis said o be a
18-neighbou o σi dim σ∩µ≥1. And µis said o be a 6-neighbou o σi
dim σ∩µ≥2. Le Nβ(σ) deno e he se o β-neighbou s o σ(β= 6,18,26).
Clea ly N6(σ)⊂N18(σ)⊂N26(σ) = N(σ).
Le Obe a digi al objec in K3. Two cubes σ, τ ∈Oa e said o be
β-connec ed in O(β= 6,18,26) i he e exis s a sequence o cubes σ=
σ1, . . . , σk=τin Osuch ha σiis β-neighbou o σi+1 o 1 ≤i≤k−1.
A digi al objec Ois said o be β-connec ed i any wo cubes σ, τ ∈Oa e
β-connec ed in O. A β-componen o Ois a maximal β-connec ed subse o O.
No ice ha Ois 26-connec ed i and only i Ois connec ed in he digi al sense
(see §2). The DIG-componen s o he complemen Oca e cha ac e ized in he
ollowing esul .
Theo em 3 Gi en a digi al objec Oin K3, he DIG-componen s o i s com-
plemen Oca e exac ly he 6-componen s o Oc.
We a e now conside ing a new polyhed al decomposi ion o IR3, deno ed
K3(ZZ3), consis ing o uni cubes wi h e ices in ZZ3. To a oid misunde s and-
ings, we keep he e minology cube o he 3-poly opes o K3and we call ZZ3-cells
he closed cubes in K3(ZZ3). Gi en a cube σ∈K3, he cuboid ZZ3(σ) o σis he
union o all he ZZ3-cells whose e ices co espond o cen e s o cubes in N(σ).
Gi en a ZZ3-cell Aand a digi al objec Oin K3, he se A∩Owill be called he
con igu a ion o Oin A( he poin s in A∩Owill be ma ked in igu es by “•”).
Associa ed wi h some speci ic con igu a ions, Kong and Roscoe [Kong85]
de ine ce ain 2-dimensional polyhed a called pla es. Fo each adjacency β=
4 On Su aces in Digi al Topology
Figu e 1.
6,18,26 a amily IFβo admissible pla es is gi en. He e we show only he amily
IF6which consis s o he plane egions displayed in Figu e 1, associa ed o he
co esponding con igu a ions (up o o a ion o e lec ion). See [Kong85] o a
desc ip ion o IF18 and IF26.
Apla e cycle a a e ex c(σ)∈ZZ3is a sequence {πi; 0 ≤i≤k}o dis inc
pla es such ha
(i) The e is a sequence {ei; 0 ≤i≤k}in which eiand ei+1 a e dis inc
edges o πi(0 ≤i < k), e0and ena e dis inc edges o πk, and c(σ) is a e ex
o each ei.
(ii) I i6=j hen πi∩πjis he union o (a) a numbe (possibly ze o) o
s aigh line segmen s each o which is an edge o bo h pla es, and (b) a se o
e ices o bo h pla es.
(iii) Any edge o a πiis an edge o a mos one o he πj.
Using he concep o IF6-pla e, Kong and Roscoe gi e he ollowing cha -
ac e iza ion o he (26,6)-su aces. This cha ac e iza ion is s a ed he e as a
de ini ion. Namely,
De ini ion 4 (P op. 12 in [Kong85]) Le Obe a digi al objec in K3. The
digi al objec Ois said o be a (26,6)-su ace i he ollowing h ee condi ions
hold:
(i) No con igu a ion o Ocon ains mo e han ou poin s, and only he
con igu a ions wi h ou poin s in Figu e 1 a e possible.
(ii) The se o IF6-pla es o Owhich con ain he poin c(σ),IF6(O)(σ),
de ines a pla e cycle a c(σ).
(iii) I τ∈N(σ)∩O hen c(τ)is he e ex o a pla e in IF6(O)(σ).
I is no di icul o p o e:
Lemma 5 The pla es in IF6(O)(σ)de ine a polyhed al decomposi ion o a 2-disk
con ained in he cuboid ZZ3(σ). Fu he mo e he 2-cells o his decomposi ion
a e iangles o ec angles.
F om his esul we ob ain:
P oposi ion 6 Le Obe a (26,6)-su ace. Then he amily o all IF6-pla es o
Ode ines a polyhed al decomposi ion P(O)o a 2-mani old wi hou bounda y.
Mo eo e , AOis a iangula ion o P(O).
Co olla y 7 Each (26,6)-su ace is a digi al 2-mani old wi hou bounda y.
Ayala e al. 5
Figu e 2.
Figu e 3.
In o de o p o e he con e se, he ollowing esul is needed.
P oposi ion 8 Le Obe a digi al objec in K3such ha AOis a connec ed
2-complex in which each edge is he in e sec ion o exac ly wo iangles (in
o he wo ds, Ois a digi al 2-pseudomani old wi hou bounda y). Then no con-
igu a ion o Ocon ains mo e han ou poin s and only he con igu a ions in
Figu e 2 (a e a sui able o a ion o e lec ion) can appea .
Gi en a ZZ3-cell Aand a digi al objec Oin K3, he ace o Oin Ais he
subpolyhed on o |AO|con ained in A. Then P oposi ion 8 yields
P oposi ion 9 I Ois a digi al 2-pseudomani old wi hou bounda y in K3only
he aces in Figu e 3 (a e a sui able o a ion o e lec ion) can appea . In
pa icula , condi ions 4(i) and 4(iii) hold o O.
P oposi ion 10 I Ois a digi al 2-mani old wi hou bounda y in K3 hen con-
di ion 4(ii) also holds o O.
As a consequence o hese wo p oposi ions we ob ain:

6 On Su aces in Digi al Topology
Co olla y 11 Each digi al 2-mani old wi hou bounda y in K3is a (26,6)-
su ace.
So, om co olla ies 7 and 11 he nex cha ac e iza ion ollows.
Theo em 12 A digi al objec Oin K3is a digi al 2-mani old wi hou bounda y
i and only i Ois a (26,6)-su ace.
This cha ac e iza ion, Theo em 3 and he Gene alized Digi al Jo dan The-
o em 2 allow us o eco e , wi hou any new p oo , Reed’s digi al sepa a ion
heo em (Thm. 1 in [Reed84]) and he main heo em in [Mo gen hale 81]:
Theo em 13 A(26,6)-su ace di ides ZZ3in wo 6-componen s.
Acknowledgemen s: This wo k was pa ially suppo ed by he p ojec s DG-
ICYT PB92-0672 and Un. La Rioja 94PYC16LLP.
Re e ences
[Ayala∞] R. Ayala, E. Dom´ınguez, A.R. F anc´es, A. Quin e o, J. Ru-
bio. A Polyhed al App oach o Digi al Topology. P ep in .
[Kong85] T.Y. Kong, A.W. Roscoe. Con inuous Analogs o Axioma-
ized Digi al Su aces. Compu e Vision, G aphics, and Im-
age P ocessing, 29 (1985), 60-86.
[Massey78] W. Massey. Homology and Cohomology Theo y. Ma cel
Dekke , 1978.
[Mo gen hale 81] D.G. Mo gen hale , A. Rosen eld. Su aces in h ee-
dimensional digi al images. In o ma ion and Con ol, 51
(1981), 227-247.
[Reed84] G.M. Reed. On he Cha ac e iza ion o Simple Closed Su -
aces in Th ee-dimensional Digi al Images. Compu e G aph-
ics and Image P ocessing, 25 (1984), 226-235.
[Rosen eld79] A. Rosen eld. Digi al Topology. Ame . Ma h. Mon hly, 86
(1979), 621-630.