On surfaces in digital topology

Proc. of the 5th Int. Workshop on Discrete Geometry for Computer Imagery DGCI95. Clermont–Ferrand, France, September 1995. 1 ON SURFACES IN DIGITAL TOPOLOGY R. Ayala∗, E. Dom´ınguez∗∗, A.R. Franc´es∗∗, A. Quintero∗, J. Rubio∗∗ ∗Dept. de Algebra, Computaci´on, Geometr´ıa y Topolog´ıa. Universidad de Sevilla. Facultad de Matem´aticas. Apartado de Correos: 1160. E-41080 Sevilla (SPAIN) e-mail: [email protected] ∗∗Dept. de Inform´atica e Ingenier´ıa de Sistemas. Universidad de Zaragoza. Facultad de Ciencias. Edificio de Matem´aticas. E-50009 Zaragoza (SPAIN) e-mail: [email protected] , [email protected] Abstract: In [Ayala∞] a new framework for digital topology has been proposed. This framework offers the possibility of transfering, in an easy way, definitions, statements and proofs from continuous topology to digital topology (see details in §2). In particular, it provides a straightforward definition of n-dimensional digital manifold. In this paper we prove that the class of digital 2-manifolds without boundary in the grid ZZ3agrees with the class of (26,6)-surfaces defined by Kong-Roscoe and other authors ([Morgenthaler81],[Reed84],[Kong85]). As a consequence, the separation theorem for digital surfaces stated in [Morgenthaler81] and [Reed84] is obtained. Keywords: digital topology, digital surfaces 1 Introduction In [Ayala∞] a new framework for digital topology has been proposed. In this framework, the pixels on a computer screen are represented by means of a polyhedral complex. Associated to this polyhedral complex, three different models (the logical, conceptual and continuous models) are defined and these models allow us to transfer, in an easy way, definitions, statements and proofs from continuous topology to digital topology (see details in §2). In particular, this framework provides a straightforward definition of n-dimensional digital manifold in such a way that closed digital 1-manifolds in the grid ZZ2correspond to the well-known digital Jordan curves in Rosenfeld’s sense ([Rosenfeld79]). In this paper we prove that the class of digital 2-manifolds without boundary in the grid ZZ3agrees with the class of (26,6)-surfaces defined by Kong-Roscoe and other authors ([Morgenthaler81],[Reed84],[Kong85]). As a consequence, the separation theorem for digital surfaces stated in [Morgenthaler81] and [Reed84] is obtained. It must be pointed out that Kong and Roscoe actually define (α, β)-surfaces for α, β ∈ {6,18,26}. Of these surfaces, however, all except (18,6), (6,18), (26,6), and (6,26) are usually discarded on the grounds that their restrictions on the grid ZZ2×{0} ⊂ ZZ3produce the paradoxical 8 or 4-adjacency relations 2 On Surfaces in Digital Topology for ZZ2. Our characterization suggests that, among the non-paradoxical (α, β)- surfaces, the (26,6)-surfaces are more likely to provide a theory for ZZ3which as nearly as possible replicates that of IR3. 2 Digital Topology and polyhedral complexes In this paper Kwill denote a locally finite and homogeneously n-dimensional polyhedral complex. Namely, Kis a complex of convex cells (polytopes) such that each polytope is face of a finite number (non-zero) of n-polytopes. If σ∈K, the boundary of the polytope σis the set ∂σ union of its faces. The interior of σis the set ◦ σ=σ−∂σ. If |K|denotes the underlying polyhedron of K, a centroid-map is a map c:K→ |K|such that c(σ)∈◦ σ. The point c(σ) is called centroid of σand the pair (K, c) is called device model. Given (K, c), we define an undirected graph L(K,c)(or simply LK) whose vertices are the centroids of n-polytopes in Kand two vertices are adjacents in LKif their corresponding n-polytopes intersect. The graph LKis called the logical model of K. The digraph CK, called conceptual model of K, is defined as follows. Its vertices are those of LKand, in addition, the centroids c(σ) such that σis the intersection of two or more n-polytopes of K. The directed edges are pairs (c(τ), c(σ)) with τface of σ. If no confusion arises, we identify each centroid c(σ) with the corresponding polytope σ, and the device model (K, c) with the polyhedral complex K. Adigital object in a device model Kis a subset Oof the set of centroids of n-polytopes of K. From the subgraph of LKgenerated by O, denoted i(O), we define the subgrah pi(O) of CKgenerated by the vertices of i(O) together with the centroids of polytopes which are the intersection of two or more n-polytopes associated to vertices of i(O). Example 1 In this paper we shall deal with the standard cubical decomposition of IRn,Kn. That is, the device model determined by the collection of unit ncubes in IRnwhose edges are parallel to the coordinate axes and whose centers are the points of ZZn⊂IRn. The centroid-map associates to each cube σits center c(σ). Thus a digital object in Kncorresponds to a subset of ZZn. A subset C⊂Ois called a component of the digital object Oif i(C) is a connected component of i(O). On the other hand, if Ocdenotes the complement of Oin the set of n-polytopes of K, a subset D⊂Ocis called a DIG-component of Ocif Dis the set of centroids of Ocwhich belong to a connected component of CK−pi(O). The continuous analogue |AO|of a digital object Ois the underlying polyhedron of the order complex AOassociated to the graph pi(O). That is, hx0, x1, . . . , xmiis a m-simplex of AOif x0x1. . . xmis a directed path in the digraph pi(O). This simplicial complex admits a polyhedral inmersion in K and thus |AO|can be considered a subpolyhedron of |K|. It is easy to verify that there exists a bijective map between the set of DIG-components of the complement Ocand the set of connected components of the topological space Ayala et al. 3 |AK| − |AO|. In fact, each DIG-component D⊂Ocis determined by the n-polytopes in pi(Oc)∩A, where Ais a connected component of |AK|−|AO|. A digital object Ois a digital manifold if |AO|is a combinatorial manifold. If |AO|only is a topological manifold then Ois called a weak digital manifold. In the standard cubical decomposition K2of IR2, a digital object Ois a closed digital 1-manifold if and only if Ois a 8-curve in Rosenfeld’s sense (see [Ayala∞] and [Rosenfeld79]). In §3 the relationship between the digital 2-manifolds in K3and the notion of surface due to Kong-Roscoe and other authors ([Morgenthaler81],[Reed84],[Kong85]) is studied. Let us state here a version of a Generalized Digital Jordan Theorem, which can be easily proved by using the corresponding continuous result (III.11.17 in [Massey78], for example) and our previous definitions. Theorem 2 (Generalized Digital Jordan Theorem) Let Kbe a polyhedral complex such that |K|= IRn. If a digital object Oin Kis a weak digital (n−1)-manifold without boundary, then the complement Ocis divided in two DIG-components. Moreover, if Ois finite then one DIG-component is finite. 3 Digital 2-manifolds and (26,6)-surfaces Let K3be the standard cubical decomposition of IR3. Given a cube σ∈K3, let N(σ) denote the set of cubes in K3which meet σ(σitself included). A cube µ∈N(σ) is said to be a 26-neighbour of σ. The cube µis said to be a 18-neighbour of σif dim σ∩µ≥1. And µis said to be a 6-neighbour of σif dim σ∩µ≥2. Let Nβ(σ) denote the set of β-neighbours of σ(β= 6,18,26). Clearly N6(σ)⊂N18(σ)⊂N26(σ) = N(σ). Let Obe a digital object in K3. Two cubes σ, τ ∈Oare said to be β-connected in O(β= 6,18,26) if there exists a sequence of cubes σ= σ1, . . . , σk=τin Osuch that σiis β-neighbour of σi+1 for 1 ≤i≤k−1. A digital object Ois said to be β-connected if any two cubes σ, τ ∈Oare β-connected in O. A β-component of Ois a maximal β-connected subset of O. Notice that Ois 26-connected if and only if Ois connected in the digital sense (see §2). The DIG-components of the complement Ocare characterized in the following result. Theorem 3 Given a digital object Oin K3, the DIG-components of its complement Ocare exactly the 6-components of Oc. We are now considering a new polyhedral decomposition of IR3, denoted K3(ZZ3), consisting of unit cubes with vertices in ZZ3. To avoid misunderstandings, we keep the terminology cube for the 3-polytopes of K3and we call ZZ3-cells the closed cubes in K3(ZZ3). Given a cube σ∈K3, the cuboid ZZ3(σ) of σis the union of all the ZZ3-cells whose vertices correspond to centers of cubes in N(σ). Given a ZZ3-cell Aand a digital object Oin K3, the set A∩Owill be called the configuration of Oin A(the points in A∩Owill be marked in figures by “•”). Associated with some specific configurations, Kong and Roscoe [Kong85] define certain 2-dimensional polyhedra called plates. For each adjacency β= 4 On Surfaces in Digital Topology Figure 1. 6,18,26 a family IFβof admissible plates is given. Here we show only the family IF6which consists of the plane regions displayed in Figure 1, associated to the corresponding configurations (up to rotation or reflection). See [Kong85] for a description of IF18 and IF26. Aplate cycle at a vertex c(σ)∈ZZ3is a sequence {πi; 0 ≤i≤k}of distinct plates such that (i) There is a sequence {ei; 0 ≤i≤k}in which eiand ei+1 are distinct edges of πi(0 ≤i < k), e0and enare distinct edges of πk, and c(σ) is a vertex of each ei. (ii) If i6=jthen πi∩πjis the union of (a) a number (possibly zero) of straight line segments each of which is an edge of both plates, and (b) a set of vertices of both plates. (iii) Any edge of a πiis an edge of at most one other πj. Using the concept of IF6-plate, Kong and Roscoe give the following characterization of the (26,6)-surfaces. This characterization is stated here as a definition. Namely, Definition 4 (Prop. 12 in [Kong85]) Let Obe a digital object in K3. The digital object Ois said to be a (26,6)-surface if the following three conditions hold: (i) No configuration of Ocontains more than four points, and only the configurations with four points in Figure 1 are possible. (ii) The set of IF6-plates of Owhich contain the point c(σ),IF6(O)(σ), defines a plate cycle at c(σ). (iii) If τ∈N(σ)∩Othen c(τ)is the vertex of a plate in IF6(O)(σ). It is not difficult to prove: Lemma 5 The plates in IF6(O)(σ)define a polyhedral decomposition of a 2-disk contained in the cuboid ZZ3(σ). Furthermore the 2-cells of this decomposition are triangles or rectangles. From this result we obtain: Proposition 6 Let Obe a (26,6)-surface. Then the family of all IF6-plates of Odefines a polyhedral decomposition P(O)of a 2-manifold without boundary. Moreover, AOis a triangulation of P(O). Corollary 7 Each (26,6)-surface is a digital 2-manifold without boundary. Ayala et al. 5 Figure 2. Figure 3. In order to prove the converse, the following result is needed. Proposition 8 Let Obe a digital object in K3such that AOis a connected 2-complex in which each edge is the intersection of exactly two triangles (in other words, Ois a digital 2-pseudomanifold without boundary). Then no configuration of Ocontains more than four points and only the configurations in Figure 2 (after a suitable rotation or reflection) can appear. Given a ZZ3-cell Aand a digital object Oin K3, the trace of Oin Ais the subpolyhedron of |AO|contained in A. Then Proposition 8 yields Proposition 9 If Ois a digital 2-pseudomanifold without boundary in K3only the traces in Figure 3 (after a suitable rotation or reflection) can appear. In particular, conditions 4(i) and 4(iii) hold for O. Proposition 10 If Ois a digital 2-manifold without boundary in K3then condition 4(ii) also holds for O. As a consequence of these two propositions we obtain: 6 On Surfaces in Digital Topology Corollary 11 Each digital 2-manifold without boundary in K3is a (26,6)- surface. So, from corollaries 7 and 11 the next characterization follows. Theorem 12 A digital object Oin K3is a digital 2-manifold without boundary if and only if Ois a (26,6)-surface. This characterization, Theorem 3 and the Generalized Digital Jordan Theorem 2 allow us to recover, without any new proof, Reed’s digital separation theorem (Thm. 1 in [Reed84]) and the main theorem in [Morgenthaler81]: Theorem 13 A(26,6)-surface divides ZZ3in two 6-components. Acknowledgements: This work was partially supported by the projects DGICYT PB92-0672 and Un. La Rioja 94PYC16LLP. References [Ayala∞] R. Ayala, E. Dom´ınguez, A.R. Franc´es, A. Quintero, J. Rubio. A Polyhedral Approach to Digital Topology. Preprint. [Kong85] T.Y. Kong, A.W. Roscoe. Continuous Analogs of Axiomatized Digital Surfaces. Computer Vision, Graphics, and Image Processing, 29 (1985), 60-86. [Massey78] W. Massey. Homology and Cohomology Theory. Marcel Dekker, 1978. [Morgenthaler81] D.G. Morgenthaler, A. Rosenfeld. Surfaces in threedimensional digital images. Information and Control, 51 (1981), 227-247. [Reed84] G.M. Reed. On the Characterization of Simple Closed Surfaces in Three-dimensional Digital Images. Computer Graphics and Image Processing, 25 (1984), 226-235. [Rosenfeld79] A. Rosenfeld. Digital Topology. Amer. Math. Monthly, 86 (1979), 621-630.