On surfaces in digital topology

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.