Strong separating (k, k)−surfaces on Z3

Strong separating (k,k)−surfaces on Z3∗ J. C. Ciria1, E. Domínguez1, A. R. Francés1and A. Quintero2 1Universidad de Zaragoza, Dpto. Informática e Ing. Sist., Zaragoza, Spain. 2Universidad de Sevilla, Dpto. Geometría y Topología, Sevilla, Spain. {jcciria,noesis,afrances}@unizar.es ,[email protected] Abstract For each adjacency pair (k, k)!= (6,6),k, k∈{6,18,26}, we introduce a new family Skk of surfaces in the discrete space Z3that strictly contains several families of surfaces previously defined, and other objects considered as surfaces, in the literature. Actually, Skk characterizes the strongly k−separating objects of the family of digital surfaces, defined by means of continuous analogues, of the universal (k, k)−spaces introduced in [6]. Keyworks discrete surface; continuous analogue, strong separation. 1 Introduction In the graph–theoretical approach to Digital Topology, the search for a definition of digital surfaces as subsets of voxels is still a work in progress since it was started in the early 1980’s. Despite the interest of the applications in which it is involved (ranging from visualization to image segmentation and graphics), there is not yet a well established general notion of digital surface that naturally extends to higher dimensions. The fact is that, after the first definition of surface, proposed by Morgenthaler [11] for the grid Z3with the usual adjacency pairs (26,6) and (6,26), each new contribution has either increased the number of surfaces (strong surfaces [3] and simplicity surfaces [7]) or extended the definition to other adjacency pairs [8], but still leaving out some objects considered as surfaces for practical purposes [10]. For each adjacency pair (k,k)#= (6,6),k,k∈{6,18,26}, and within the framework for Digital Topology in [2], we have recently found [6] a homogeneous (k,k)−space (R3,f kk)whose set of digital surfaces is the largest in that class of digital spaces. Moreover, these sets of surfaces contain all those quoted above. Of course a Jordan separation property holds for them, but some do not satisfy the strong separation property usually required to discrete surfaces in Z3. On the other hand they are defined by means of continuous analogues, and thus it might not be considered as a completely discrete construction. Our goal in this paper is twofold. Firstly we provide a completely discrete characterization of the digital surfaces in each (k,k)−space (R3,f kk), by extending Kong’s method [8] based on plates and graphs. Then, we find in §5 a local characterization for the strong separating condition of digital surfaces of (R3,f kk)which is used to derive a genuine notion of (k,k)−surface. This work contains an extension of previous results for the (26,6)−adjacency in [4]. 2 A set of (k, k)−Jordan objects In this section we introduce, for each of the usual adjacency pairs (k,k)#= (6,6),k,k∈{6,18,26}, defined on Z3, a family of objects that satisfies a Jordan property. Actually, these objects could be considered as a starting definition of a family of (k,k)−surfaces since they are made of small ∗This work has been partially supported by project MTM2007-65726 MICINN, Spain. 73 Pc 3Pb 4Pe 4Pf 4Pb 5Pc 6 Pc 2Pc 5Pb 6P8 Figure 1: Some patterns that may appear in a digital object O⊆Z3. Each picture represents a unit cube Cof Z3, and the black dots are the set of voxels in O∩C. The upper row contains the six non-square plates that may appear in a digital object. The patterns in the lower row cannot appear in a (26,6)−presurface. surface pieces, called plates, which are adequately glued to each other in the way defined by an assembly graph. To introduce these notions we firstly recall some basic definitions from the graph–theoretical approach to Digital Topology. Two distinct voxels σ=(xσ 1,x σ 2,x σ 3),τ=(xτ 1,x τ 2,x τ 3)∈Z3are said to be 6-, 18or 26-adjacent if max{|xσ i−xτ i|;1≤i≤3}≤1and they differ in, at most, one, two or three of their coordinates, respectively. Moreover, we say that two n-adjacent voxels are strictly n-adjacent if they are not m-adjacent for any m < n, where n, m ∈{6,18,26}.Aunit cube of Z3is any subset Cof eight mutually 26-adjacent voxels. Similarly, a unit square of Z3is a subset of four mutually 18-adjacent voxels that is actually the intersection of two distinct unit cubes. For n∈{6,18,26}the transitive closure of the n-adjacency relation defines an equivalence relation on each subset A⊆Z3, whose classes are called the n-components of A. Moreover, Ais said to be n-connected if it has only one n-component. Definition 2.1. Let O⊆Z3be a digital object. A subset p⊆Ois said to be a k−plate in O if either pis a unit square of Z3or p=C∩Ocorresponds (up to rotations and symmetries) to one of the patterns in the set Pk, where Cis a unit cube of Z3and P6={Pc 3,Pb 4,Pe 4,Pf 4,Pb 5,Pc 6}, P18 ={Pc 6}and P26 =∅; see Fig. 1. For any voxel σ∈Owe denote by Pk(O,σ)the set of all k−plates in Ocontaining σ, while Pk(O)is the set of all k−plates in O. Remarks 2.2. Notice that the square plates are the only 26−plates in any object. Notice also that given a unit cube Cand a digital object Othe set C−O#=∅is trivially 26−connected, it is 18−connected iffC∩O/∈P18 and it is 6−connected iffC∩O/∈P6∪{Pc 5,Pb 6}; see Fig. 1. Besides the k−plates, we consider the following bipartite graph, termed the k−assembly graph, for any digital object O⊆Z3. Definition 2.3. The nodes of the k−assembly graph of O⊆Z3,Gk(O), are the elements of Pk(O)∪Ek(O), where Ek(O)is the set of all pairs of voxels σ,τ∈Osatisfying one of the two following properties: 1. σand τare 6−adjacent; 2. σand τare strictly 18−adjacent, no voxel in Ois 6−adjacent to both of them and, moreover, {σ,τ}is in the intersection of two k−plates of O. And two nodes p∈Pk(O)and e∈Ek(O)define an edge of Gk(O)if and only if e⊆p. The k−assembly graph of Oaround a voxel σ∈Ois the subgraph Gk(O,σ)of Gk(O)induced by the set of nodes Pk(O,σ)∪Ek(O,σ), where Ek(O,σ)={e∈Ek(O); σ∈e}. Remark 2.4. For k∈{18,26}the set Ek(O)consists entirely of pairs of 6−adjacent voxels since the square plates and the Pc 6plates cannot share just two strictly 18−adjacent voxels. Definition 2.5. A digital object S⊆Z3is said to be a (k,k)−presurface if the following conditions hold for each voxel σ∈S: 74 τ1 τ2 τ0 (a) S p p q q 1 1 2 2 (b) G6(S) Figure 2: A(18,6)−presurface Sand its 6−assembly graph G6(S). Each dot in (b) represents one of the eight unit cubes shown in (a), which are actually 6−plates of S. Each square in (b) represents a pair of strictly 18−or 6−adjacent voxels in Sthat, together with plates, define the 6−assembly graph of S. 1. For each unit cube Cσ⊆Z3containing σ, the intersection Cσ∩Sdoes not correspond (up to rotations and symmetries) to any pattern in FPkk, where FP6,26 =FP18,26 = FP6,18 =FP18,18 ={P8},FP26,26 =FP26,18 ={Pc 2,P8},FP18,6={Pc 5,Pb 6,P8}and FP26,6= {Pc 2,Pc 5,Pb 6,P8}; see Fig. 1. 2. Given a voxel τ∈Sstrictly 18−adjacent to σand such that no other voxel in Sis 6−adjacent to both σand τ, let C1and C2be the two only unit cubes of Z3containing {σ,τ}. If k=6 then Ci∩S∈P6(O)for at least one index i∈{1,2}, while if k,k∈{18,26}then {σ,τ}is contained in a 6−component of S∩(C1∪C2). 3. If τ∈Sis 6−adjacent to σthen Pk(S, σ)∩Pk(S, τ)consists exactly of two plates. 4. Pk(S, σ)#=∅and Gk(S, σ)is a cycle. Remark 2.6. Notice that condition (2) in the definition above is void if k=6. Example 2.7. Figure 2 depicts a (18,6)−presurface S, made of eight plates, and its 6−assembly graph G6(S). Notice that the voxel τ0∈Sbelongs to exactly two plates p1,p 2∈P6(O)and it is 6−adjacent to both τ1and τ2. Hence, the pairs of voxels qi={τ0,τi},i=1,2, belong to E6(S, τ0) and the 6−assembly graph of Saround τ0,G6(S, τ0), is the cycle defined by the vertices p1,p 2,q 1 and q2in Fig. 2(b). The assembly graph endows each presurface with the combinatorial structure of a surface. More precisely, we will show in Th. 4.8 below that (k,k)−presurfaces characterize the digital surfaces of the universal (k,k)−space (R3,f kk)defined in [6] within the approach to Digital Topology in [2]. In particular, we obtain, as a corollary of this characterization and Th. 3.3, that all (k,k)−presurfaces are Jordan objects; that is, each k-connected (k,k)−presurface Sseparates its complement Z3−S into two k−components. In order to provide the appropriate context for Th. 4.8 we collect the basic elements of this framework in next section. 3 Universal (k, k)−spaces and digital surfaces In this section we recall the definitions and main results from [6] needed in this paper, which were established within the framework for Digital Topology introduced in [2]. In this approach a digital space is a pair (K, f), where Kis a polyhedral complex and fis a lighting function from which we associate to each digital image an Euclidean polyhedron called its continuous analogue. In this paper we will only deal with the universal (k,k)−spaces (R3,f kk)defined in [6]. The complex R3is determined by the collection of unit cubes in the Euclidean space R3centered at points of integer coordinates. Each 3-cell in R3represents a voxel, and so any digital object is a subset of the set cell3(R3)of 3-cells in R3. The lower dimensional cells of R3(actually, d-cubes, 0≤d<3) are used to describe the various possible ways voxels link to each other. Notice that each d−cell σ∈R3can be associated to its center c(σ). In particular, if dim σ=3then c(σ)∈Z3 75 and so every digital object in R3can be naturally identified with a subset of the discrete space Z3. Henceforth we shall use this identification without further comment. Lighting functions are maps of the form P(cell3(R3))×R3→{0,1}, where P(cell3(R3)) stands for the family of all subsets of cell3(R3); i.e., all digital objects. In order to introduce the lighting functions fkkwe need some more notation. As usual, given two cells α,β∈R3we write α≤βif αis a face of β, and α<βif in addition α#=β. Given a digital object O⊆cell3(R3)the star of a cell αin Ois the set st3(α;O)={σ∈O;α≤σ}of 3-cells (voxels) in Ohaving αas a face. Similarly, the extended star of αin Ois the set st∗ 3(α;O)={σ∈O;α∩σ#=∅}. Finally, the support of Ois the set supp(O)of cells of R3(not necessarily voxels) that are the intersection of 3-cells in O; that is, α∈supp(O)if and only if α=∩{σ;σ∈st3(α;O)}. To ease the writing, we use the following notation: st3(α;R3) = st3(α; cell3(R3)) and st∗ 3(α;R3) = st∗ 3(α; cell3(R3)). Remark 3.1. The identification between cells in R3and their centers gives us a one–to–one correspondence between 0−cells (1−cells) and unit cubes (squares, respectively) of Z3. Namely, st3(α;R3)is a unit cube (square) for each 0−cell (1−cell) α∈R3. Thus, if pis plate in a given object O, then p= st3(α;O) = st3(α;R3)∩Ofor some cell αwith dim α≤1, which is called the center of p. Similarly, if e={σ,τ}is a node of Gk(O)in the set Ek(O), the cell δ=σ∩τis a 2−cell or a 1−cell, depending on whether σand τare 6−adjacent or strictly 18−adjacent, which will be also called the center of the node e. For (k,k)#= (6,6),k,k∈{6,18,26}, the lighting functions fkk are defined as follows. Given a digital object O⊆cell3(R3)and a cell δ∈R3,fk,k(O,δ)=1if and only one of the following conditions hold: 1. dim δ≥2and δ∈supp(O) 2. dim δ=0and st3(δ;O)corresponds (up to rotations and symmetries) to some pattern in the set Pk∪FPk,k(see Defs. 2.1 and 2.5) 3. dim δ=1and st3(δ;O) = st3(δ;R3)(i.e., δis the center of a square plate in O), or 4. dim δ=1,st3(δ;O)={σ,τ}, with δ=σ∩τ, and one of the next further conditions also holds: (a) for k=6, and k#=6,fk,6(O,α1)=fk,6(O,α2), where α1,α2are the two vertices of the 1-cell δ; or (b) σand τbelong to distinct 6−components of st∗ 3(δ;O), for k,k∈{18,26}. Each of these maps and, more generally, any lighting function fmay be regarded as a “face membership rule”, in the sense of Kovalevsky [9], that assigns to each digital object Othe set of cells fO={α∈R3;f(O,α) = 1}. This set yields a continuous analogue as a natural counterpart of Oin ordinary topology. Namely, the continuous analogue of Ois the polyhedron |Af O|⊆ R3triangulated by the subcomplex of the first derived subdivision of R3,Af O, consisting of all simplexes whose vertices are centers c(σ)of cells σ∈fO.1 Regarding continuous analogues as a “continuous interpretation” of digital images, we introduce digital notions in terms of the corresponding continuous ones. For example, we say that an object O⊆cell3(R3)is connected if its continuous analogue |AO|is a connected polyhedron. And, in the same way, the background of O,cell3(R3)−O, is said to be co-connected if |AR3|− |AO|is connected. Moreover, we call C⊆cell3(R3)a (co-)component of O(cell3(R3)−O, respectively) if it consists of all voxels σwhose centroids c(σ)belong to a component of |AO| (|AR3|−|AO|, respectively). Similarly, an object S⊆cell3(R3)is a digital surface in the space (R3,f)if its continuous analogue |AS|is a combinatorial surface; that is, if the link lk(v;AS)= {A∈AS;v, A < B ∈ASand v/∈A}is a 1−sphere for each vertex v∈AS. See [2] for more details on these notions of connectedness defined in a much more general context and for a definition of digital manifold in arbitrary dimension. In certain digital spaces these notions are closely related to the usual ones defined on Z3be means of adjacency pairs. More precisely, given an adjacency pair (k,k)we say that (R3,f)is a (k,k)−space if the two following properties hold for any digital object O⊆cell3(R3): 1We often drop the “f” from the notation and also write AR3instead Af cell3(R3). 76 1. Cis a component of Oiffit is a k−component of O; and, 2. Cis a co-component of the background of Oiffit is a k−component of Z3−O. In particular, it is not difficult to show that the digital spaces (R3,f kk)defined above are actually homogeneous (k,k)−spaces, in the sense that, in addition, the continuous analogue they provide for each digital object is invariant under isometries of the Euclidean space preserving Z3. On the other hand, in [1, 2, 5] it can be found several homogeneous (k,k)−spaces whose sets of digital surfaces contain the families of (k,k)−surfaces quoted in the introduction, which are also digital surfaces in the corresponding universal (k,k)−space as a consequence of the following Theorem 3.2 (Th. 20 in [6]).Any digital surface Sin an arbitrary homogeneous (k,k)−space is also a digital surface in the universal (k,k)−space (R3,f kk). Finally, and concerning the Jordan property, we have the following separation theorem for digital surfaces in (R3,f kk)as a corollary of a Jordan–Brouwer Theorem for fairly general digital spaces in [2]. Theorem 3.3. Each k−connected digital surface in (R3,f kk)separates its background cell3(R3)−S into two k−components. 4(k,k)−presurfaces are digital surfaces in (R3,f kk) In this section we will show that the notions of (k,k)−presurface and digital surface are equivalent in the universal (k,k)−space (R3,f kk)for each adjacency pair (k,k)#= (6,6),k, k∈{6,18,26}. This way, continuous analogues and even the lighting function fkk are no longer needed to determine whether a given object is a digital surface in the universal (k,k)−space. Moreover, (k,k)−presurfaces are Jordan objects as a consequence of the separation property stated in Th. 3.3 above. The characterization of digital surfaces as (k,k)−presurfaces relies on the crucial fact that, for any digital object O⊆Z3satisfying conditions (1) to (3) in Def. 2.5, the k−assembly graph Gk(O)encodes the continuous analogue AOin the universal (k,k)−space. In the proof of this result we will use the next lemmas, that state almost immediate properties of the lighting function fkk in relation to the conditions defining (k,k)−presurfaces. The first two lemmas show that fkk(O,δ) = 1 for any cell δ∈R3which is the center of a node of the k−assembly graph of O(see Remark 3.1). Lemma 4.1. Let O⊆Z3be a digital object satisfying condition (1) in Def. 2.5. The two following properties hold for a cell δ∈R3: 1. If dim δ=0then fkk(O, δ) = 1 iffδis the center of a k−plate in O. 2. If dim δ=1and δis the center of a square plate in Othen fkk(O,δ) = 1 and fkk(O,αi)=0 for the two vertices α1,α2<δ. Moreover, if γ>δis a 2−cell then also fkk(O, γ) = 1. Lemma 4.2. Let δe=σ∩τbe the center of a node e={σ,τ}of the k−assembly graph of Oin the set Ek(O). Then fkk(O, δ) = 1. Proof. If σis 6−adjacent to τthen dim δe=2and the result follows directly from the definition of fkk. Otherwise, dim δe=1. Then, necessarily the vertices α1,α2<δeare the centers of the two k−plates of Ocontaining e. Thus, by the definition of the lighting function fkk(O,αi)=1, i=1,2, and also fkk(O, δe) = 1 since k=6by Remark 2.4. Lemma 4.3. Let O⊆Z3be a digital object and pak−plate in Owith center at the cell αp.A cell γ∈R3belongs to supp(p)if and if αp<γand γ∈supp(O). Lemma 4.4. Let O⊆Z3be a digital object satisfying conditions (1) and (2) in Def. 2.5. If β∈R3is an edge which is not the center of a square plate in Oand fkk(O, β) = 1 then k=6 necessarily and the two following properties also hold: 77 1. The set A={α<β;fk,6(O,α)=1}consists of the two vertices of βwhich are actually centers of 6−plates in O; moreover, βis the center of a node e={σ,τ}∈E6(O)of G6(O). 2. fk,6(O,γ) = 0 for any 2−cell γ>β. Lemma 4.5. Let O⊆Z3be a digital object satisfying conditions (1) and (3) in Def. 2.5. If γ∈R3 is a 2−cell such that fkk(O,γ) = 1 then st3(γ;O)={σ,τ}and the set A={α<γ;fkk(O,α) = 1} consists of two elements which are centers of k−plates in O. Therefore, γis the center of the node {σ,τ}∈Ek(O). Lemma 4.6. Let O⊆Z3be a digital object satisfying conditions (1), (2) and (3) in Def. 2.5. If δ1<δ2are two cells in R3with dim δi≤2and fkk(O,δi) = 1,i=1,2, then δ1is the center of a k−plate in Owhile δ2is not. Proposition 4.7. Let O⊆Z3be a digital object satisfying conditions (1), (2) and (3) in Def. 2.5, and let AObe its continuous analogue in the universal (k,k)−space (R3,f kk). Then, there exists a simplicial isomorphism ϕ:Gk(O)→ ! AO=AO−{c(σ); σ∈O}, where the simplicial complex ! AOis the subcomplex of AOconsisting of all simplices A∈AOsuch that c(σ)/∈Afor any voxel σ∈O. Moreover, for each σ∈Othe isomorphism ϕrestricts to an isomorphism ϕσ:Gk(O,σ)→ lk(c(σ); AO). Proof. According to Remark 3.1 let αn∈R3be the center of a node n∈Pk(O)∪Ek(O)of the k−assembly graph of O. Since dim αn≤2, the map n-→ ϕ(n)=c(αn)between the set of nodes of Gk(O)and the vertices of the simplicial complex ! AOis well–defined by Lemmas 4.1 and 4.2. Moreover, ϕis a bijection by Lemmas 4.4 and 4.5. This map naturally extends also to edges. Recall that a k−plate p∈Pk(O)and a pair of voxels e={σ1,σ2}∈Ek(O)define an edge in Gk(O)iffe⊆p. Then αp<αe=σ1∩σ2by Lemma 4.3 and thus their images determine the 1−cell .c(αp),c(αe)/∈ ! AO. Finally we check that ϕis actually a simplicial isomorphism; that is, for any edge .c(γ1),c(γ2)/∈ ! AOthe nodes ϕ−1(c(γi)),i=1,2, determine an edge in Gk(O). Indeed, if γ1<γ2, then γ1is the center of a k−plate p∈Pk(O)while γ2=σ1∩σ2is the center of a pair of voxels e={σ1,σ2}∈Ek(O)(here we use again Lemmas 4.4 and 4.5), and the result follows since σi∈st3(γ1;O)=p,i=1,2. Finally, by using Lemma 4.3 it is immediate to check that ϕ(Pk(O, σ)∪Ek(O,σ)) = {c(α)∈ AO;α<σ}for each voxel σ∈O, and therefore the isomorphism ϕidentifies the graph Gk(O,σ) with lk(c(σ); AO). Theorem 4.8. A digital object S⊆Z3is a (k,k)−presurface if and only if it is a digital surface in the universal (k,k)−space (R3,f kk). Proof. Assume S⊆Z3is a (k, k)−presurface. It will suffice to check that the link Lδ= lk(c(δ); AS) is a 1-sphere for each cell δ∈R3such that fkk(S, δ) = 1. For each voxel δ∈S,Lδcan be identified with the k−assembly graph Gk(S, δ)around δ, by Prop. 4.7, and hence it is a 1-sphere by condition (4) in Def. 2.5. If dim δ=2the result is an immediate consequence of Lemma 4.5. Similarly, if dim δ=1the result follows from Lemma 4.4 in case δis not the center of a plate, and from Lemma 4.1(2) otherwise. Finally, if δis a vertex then it is the center of a plate p∈Pk(S)by Lemma 4.1. By the definition of the lighting function fkk we know that fkk(S, σ∩τ) = 1 for each pair of 6−adjacent voxels σ,τ∈pand, in particular, it is readily checked that Lδis a 1−sphere whenever p is a Pc 6 plate. If pis not a Pc 6plate then k=6. Moreover, if pis not a Cf 4plate, σ1,σ2∈pare strictly 18−adjacent and no other voxel in pis 6−adjacent to both of them, we derive from the fact that c(δ)∈Lσi,i=1,2, which has been proved to be a 1−sphere, that fkk(S, σ1∩σ2)=1. Therefore Lδis also a 1−sphere in these cases by the definition of fkk. In case p={σ1,σ2,σ3,σ4}is a Cf 4 plate we have some choices to make. As c(δ)is in the 1−sphere Lσi,1≤i≤4, it contains exactly two of the three centers cj i=c(σ1∩σi),1≤i#=j≤4. If c1 2,c 1 3∈Lσ1then c4 1/∈Lσ4and thus c4 2,c 4 3∈Lσ4. Therefore c2 1,c 4 2∈Lσ2,c3 1,c 4 3∈Lσ3and so Lδis also a cycle. 78 Conversely, assume Sis a digital surface in (R3,f kk). It will be enough to check conditions (1) to (3) in Def. 2.5 for Ssince, under the assumption of these properties, we get (4) as an immediate consequence of Prop. 4.7. If C∩Ocorresponds to some pattern in the set FPkk for some unit cube C, it can be readily checked from the definition of fkkthat the object Ois not a digital surface. Hence condition (1) holds for S. To check condition (2), let σ,τ∈Sbe two strictly 18-adjacent voxels and assume that they are not 6-connected by a third voxel in S. For the edge β=.α1,α2/=σ∩τwe consider the two possible cases: Case fkk(S, β) = 0. If k=6the definition of fkk shows that fk6(S, α) = 1 for a vertex α<β. Then by condition (1), already proved, and Lemma 4.1 it follows that αis the center of a k−plate in P(S, σ)∩P(S, τ). On the other hand, if k,k∈{18,26}then σ,τare 6−connected in st∗ 3(β;S), by the definition of fkk, which is just condition (2). Case fkk(S, β)=1. Then it can be readily checked that fkk(S, αi)=1for the two vertices α1,α2of β, since Sis a digital surface in (R3,f kk). Therefore the vertices αiare centers of k−plates in P(S, σ)∩P(S, τ)by Lemma 4.1. Notice that this case is only posible if k=6. Finally we prove condition (3). For this let σ,τ∈Sbe two 6−adjacent voxels and let γ=σ∩τ. Then fkk(S, γ) = 1 by definition of fkk. As lk(c(γ); AS)is a 1−sphere there exist exactly two faces α1,α2<γwith fkk(S, αi)=1. If dim αi=0then αiis the center of a k−plate by Lemma 4.1. Similarly, if dim αi=1then the definition of fkk yields that st3(αi;S) = st3(αi;R3) since it contains the two 6−adjacent voxels σand τ, and hence αiis the center of a square plate. Therefore P(S, σ)∩P(S, τ)contains at least two k−plates. But given the center αpof any plate p∈P(S, σ)∩P(S, τ)we know that αp<γby Lemma 4.3 and, moreover, fkk(S, αp)=1by Lemma 4.1. This way αp∈{α1,α2}and P(S, σ)∩P(S, τ)consists of exactly two k−plates. 5(k,k)−surfaces As a consequence of Th. 3.3 and Th. 4.8 we get that each k−connected (k,k)−presurface S separates its background Z3−Sinto two k−components. In addition to this Jordan property, discrete surfaces are usually required to be strongly k−separating; that is, each voxel σ∈Sshould be k−adjacent to both k−components of Z3−S(see [3]). However, it is easy to check that this global property fails for the voxel τ0in the (18,6)−presurface shown in Fig. 2(a). Our goal in this section is to find further local conditions characterizing the strong separation property within the class of (k,k)−presurfaces in order to obtain genuine discrete surfaces according to the following Definition 5.1. A(k,k)−presurface is said to be a (k, k)−surface if it is a strongly k−separating object. In [4, §7] we found the local conditions characterizing the subset of strongly 6−separating (26,6)−presurfaces. The same conditions, and the proof as well, works for the case (18,6). For the remaining cases we get the following. Definition 5.2. Let S⊆Z3be a (k,k)−presurface, k∈{18,26}. A voxel σ∈Sis said to be a k-surface voxel if for each unit cube Cσ⊆Z3containing σthere exists a voxel τ∈Cσ−Swhich is k−adjacent to σ. Notice that every voxel in a (k,26)−presurface Sis a 26−surface voxel since Scannot contain the pattern P8in Fig. 1. Theorem 5.3. A(k,k)−presurface Sis a (k,k)−surface iffeach σ∈Sis a k−surface voxel. Proof. Recall that Sis a digital surface in the universal (k,k)−space (R3,f kk)and so |AS|is a combinatorial surface. As a consequence of the Jordan–Brouwer Theorem the difference D= |lk(c(σ;AR3)|−|lk(c(σ;AS)|consists of two components, each contained in a component of R3− |AS|. Moreover, these components characterize the k−components of Z3−Ssince (R3,f kk)is a (k,k)−space (see §3). Let δ1,δ2<σbe two cells with their centers c(δi)in each of the components 79 of D. Notice that fkk(S, δi)=0. Then, if σis k−surface voxel, the definition of fkk gives us two voxels τi/∈Swhich are k−adjacent to σand such that δi<τi,i=1,2. Therefore, c(τ1)and c(τ2) are in distinct components of R3−|AS|and the result follows. Conversely, assume k= 18 (there is nothing to prove if k= 26). If σis not a 18−surface voxel then there exists a unit cube C, with center at a vertex α∈R3, such that C−Sconsists of a single voxel τwhich is strictly 26−adjacent to σ. Then, we derive from the definitions that fk,18(S, δ)=1for each face α<δ<σ. Moreover, the centers of these cells determine a cycle in lk(c(σ); AS), and then fk,18(S, γ) = 0 for any other face γ<σ, in particular fk,18(S, α) = 0. This way {c(α)}is a component of the difference Dabove, and hence it follows that σis 18−adjacent to just one 18−component of Z3−S. Remark 5.4. It is worth pointing out that the set of (k,k)−surfaces still contains strictly the sets of simplicity and strong surfaces quoted in the introduction since each one of them is a strongly separating object [3, 7]. References [1] R. Ayala, E. Domínguez, A.R. Francés, and A. Quintero. Digital lighting functions. In E. Ahronovitz and Ch. Fiorio, editors, Discrete Geometry for Computer Imagery, volume 1347 of Lecture Notes in Computer Science, pages 137–150. Springer Berlin / Heidelberg, 1997. [2] R. Ayala, E. Domínguez, A.R. Francés, and A. Quintero. Weak lighting functions and strong 26-surfaces. Theoretical Computer Science, 283(1):29 – 66, 2002. [3] G. Bertrand and R. Malgouyres. Some topological properties of surfaces in Z3.Journal of Mathematical Imaging and Vision, 11:207–221, 1999. [4] J.C. Ciria, A. De Miguel, E. Domínguez, A.R. Francés, and A. Quintero. Local characterization of a maximum set of digital (26,6)−surfaces. Image and Vision Computing, 25(10):1685 – 1697, 2007. [5] J.C. Ciria, E. Domínguez, and A.R. Francés. Separation theorems for simplicity 26-surfaces. In Achille Braquelaire, Jacques-Olivier Lachaud, and Anne Vialard, editors, Discrete Geometry for Computer Imagery, volume 2301 of Lecture Notes in Computer Science, pages 153–161. Springer Berlin / Heidelberg, 2002. [6] J.C. Ciria, E. Domínguez, A.R. Francés, and A. Quintero. Universal spaces for (k,k)-surfaces. In S. Brlek, Ch. Reutenauer, and X. Provençal, editors, 15th Discrete Geometry for Computer Imagery, volume 5810 of Lecture Notes in Computer Science, pages 385–396. Springer, 2009. [7] M. Couprie and G. Bertrand. Simplicity surfaces: a new definition of surfaces in Z3.SPIE Vision Geometry V, 3454:40–51, 1998. [8] T.Y. Kong and A.W. Roscoe. Continuous analogs of axiomatized digital surfaces. Computer Vision, Graphics, and Image Processing, 29(1):60 – 86, 1985. [9] V. A. Kovalevsky. Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Processing, 46(2):141 – 161, 1989. [10] G. Malandain, G. Bertrand, and N. Ayache. Topological segmentation of discrete surfaces. Int. Jour. of Computer Vision, 10:183–197, 1993. [11] D.G. Morgenthaler and A. Rosenfeld. Surfaces in three-dimensional digital images. Information and Control, 51(3):227 – 247, 1981. 80