Continuous Well-Composedness Implies Digital Well-Composedness in n-D

Continuous Well-Composedness Implies Digital Well-Composedness in n-D Nicolas Boutry1 · Rocio Gonzalez-Diaz2 · Laurent Najman3 · Thierry Géraud1 Abstract In this paper, we prove that when a n-D cubical set is continuously well-composed (CWC), that is, when the boundary of its continuous analog is a topological (n − 1)-manifold, then it is digitally well-composed (DWC), which means that it does not contain any critical configuration. We prove this result thanks to local homology. This paper is the sequel of a previous paper where we proved that DWCness does not imply CWCness in 4D. Keywords Well-composed · Topological manifolds · Critical configurations · Digital topology · Local homology 1 Introduction Digital well-composedness (DWCness) is a strong property in digital topology, because it implies the equivalence of 2nand (3n−1)-connectivities in a set and in its complement. A well-known application of this flavor of WCness is the tree of shapes [11,12], a powerful hierarchical representation of the objects in a gray-level [20] or color image [10]. On the other side, continuously well-composed (CWC) images are known as “counterparts” of n-dimensional manifolds (or in short, nmanifolds) in the sense that they do not have singularities (no “pinches”) in their boundary. The consequence is that some geometric differential operators can be directly computed on the discrete sets, which can simplify or fasten specific algorithms. DWCness and CWCness are known to be equivalent in 2D and in 3D [4,16]. As the sequel of [7] where we prove thanks BNicolas Boutry [email protected] Rocio Gonzalez-Diaz [email protected] Laurent Najman [email protected] Thierry Géraud thierry[email protected] 1EPITA Research and Development Laboratory (LRDE), 14-16 rue Voltaire, 94276 Le Kremlin-Bicêtre, France 2Universidad de Sevilla, Sevilla, Spain 3Université Gustave-Eiffel, Champs-sur-Marne, France to a counter-example that DWCness does not imply CWCness in 4D, we prove in this paper that CWCness implies DWCness in n-D. Some other flavors of well-composednesses exist like well-composednessintheAlexandrovsense[2,8,9,20],wellcomposedness on arbitrary grids [2,23], weak well-composedness [5] or Euler well-composedness [6], but we will not go further into details here. The plan is the following: Sect. 2presents an intuitive explanationoftheproofpresentedinthispaper,Sect.3recalls thematerialnecessarytoourproof inmatter ofdiscrete topology;Sect.4containstheproof ofthe mainresult ofthis paper; Sect. 5concludes the paper. 2 Intuitive Proof of our Main Theorem Let us assume that we start from a finite set Xof points of Zn. We want to show that when we dilate Xby a unitary centered cube of radius 1 2in Rn, then the topological properties of the resulting CA(X)⊂Rn, called the continuous analog of X, are related to the properties of the initial set X. More exactly, we want to prove Theorem 5, which asserts that when CA(X) is regular in the sense that its boundary is a topological manifold, then it means at the same time that the initial set Xis regular in the discrete manner. Being regular in a discrete manner, in the context of discrete topology, means that a set does not contain critical configurations, well known to lead to topological issues. Using the technical terms, continuous well-composedness implies digital well-composedness. 132 Toprovethataregular CA(X)impliesa regular X,we will proceedby counterposition, that is, we will provethatassoon as Xcontains (at least) one critical configuration, then the continuous counterpart CA(X)contains a pinch at the center m∈Z 2nof this critical configuration (Sect. 4.3 is devoted to prove this fact). From a technical point of view, we will use local homology to compute local topological properties of CA(X)at mto show that it is not a homology manifold, and thus it is not a topological manifold either (we recall that topology manifoldness implies homology manifoldness). The methodology is then straightforward: by assuming that Xis not regular, we choose any of its critical configurations, we deduce its center m; since mbelongs to the boundary of CA(X)according to Lemma 1, we can study the behavior of the boundary of CA(X)from a topological point of view around mthanks to local homology. These characteristics depend only on the configuration (we do a case-by-case study) as stated by Theorem 4. We will obtain that some homological issue appeared at m(since the local homology group of dimension (n−1)will not be Zas stated in Property 4) and then we will conclude that the boundary of CA(X)is not a topological manifold. Intuitively, this is the way the main proof of this paper will be done. 3 Discrete Topology As usual in discrete topology, we will only work with digital sets, that is, non-empty strict subsets of Znwhich are finite or whose complementary in Znis finite. 3.1 Digital Topology and Digital well-composedness Let n≥2 be a (finite) integer called the dimension.Now, let B={e1,...,en}be the (orthonormal) canonical basis of Zn. We use the notation pi, where ibelongs to 1,n,to determine the ith coordinate of the point p∈Zn. We recall that the L1-norm of a point p∈Zn(seen as a vector) is denoted by .1and is equal to i∈1,n|pi|where |.|is the absolute value. Also, the L∞-norm is denoted by .∞and is equal to maxi∈1,n|pi|. For a given point p∈Zn,the2n-neighborhood in Znis denoted by N2n(p)and is equal to {p∈Zn;p−p1≤ 1}. In other words, N2n(p)=p+λiei;λi∈{−1,0,1},i∈1,n. p∞≤1}. In other words, N3n−1(p)equals: ⎧ ⎨ ⎩p+ i∈1,n λiei;λi∈{−1,0,1},i∈1,n⎫ ⎬ ⎭. From now on, let ζbe a value in {2n,3n−1}.Thestarred ζ-neighborhood of p∈Znis denoted by N∗ ζ(p)and is equal to Nζ(p)\{p}. An element of the starred ζ-neighborhood of p∈Znis called a ζ-neighbor of pin Zn. Two points p,p∈ Znsuch that p∈N∗ ζ(p)or equivalently p∈N∗ ζ(p)are said to be ζ-adjacent. Let Xbe a subset of Zn. A finite sequence π=(p0,..., pk)of points of Xis called a ζ-path joining p0and pkwhen p0is ζ-adjacent only to p1in π,pkis ζ-adjacent only to pk−1in π, and if for all i∈1,k−1,piis ζ-adjacent only to pi−1and to pi+1in π. Such a path is said to be of length k. A digital set X⊂Znis said to be ζ-connected when there exists a ζ-path into Xjoining any pair of points of X. A subset Cof Xwhich is ζ-connected and maximal in the inclusion sense (that is, there is no subset of Xgreater than Cand ζ-connected) is said to be a ζ-component of X. For any q∈Znand any F=(f1,..., fk)⊆B(Fcan be an empty set), we denote by S(q,F)the set: ⎧ ⎨ ⎩q+ i∈1,k λifiλi∈{0,1},∀i∈1,k⎫ ⎬ ⎭. Fig. 1 The two connected sets depicted here represent 2D blocks. The two white points of the block depicted on the left side are 2-antagonists in this block, and draw a primary 2D critical configuration. In a same manner, the two white points antagonists in the block depicted on the right side draw a secondary critical configuration. Indeed, in a 2D space, all critical configurations are at the same time primary and secondary Fig. 2 The two connected sets depicted here represent 3D blocks. The white points of the block depicted on the left side are 3-antagonists in this block, and draw a primary 3D critical configuration. The set of six white points in the block depicted on the right side draws a secondary 3D critical configuration For a given point p ∈ Zn,the (3n − 1)-neighborhood in Zn is denoted by N3n−1( p) and is equal to { p ∈ Zn ;p − 133 Fig. 3 The two connected sets depicted here represent 4D blocks. The white points of the block depicted on the left side are 4-antagonists in this block, and draw a primary 4D critical configuration. The set of fourteen white points in the block depicted on the right side draws a secondary 4D critical configuration We call this set the block associated with the pair (q,F); its center is q+i∈1,k fi 2, and its dimension, denoted by dim(S), is equal to k. More generally, a set S⊂Znis said to be a block when there exists a pair (q,F)∈Zn×P(B) such that S=S(q,F). Then, we say that two points p,p∈Znbelonging to a block Sare antagonists in Swhen the distance between them equals the maximal distance using the L1norm between two points in S; in this case we write p=antagS(p). Note that the antagonist of a point pin a block Scontaining pexists and is unique. Two points that are antagonists in a block of dimension k≥0 are said to be k-antagonists;kis then called the order of antagonism between these two points. Note that in the particular case where pand pare 0antagonists, p=p, the center of the block is equal to p, and the corresponding family of vectors is F=∅. Wesaythata digital subset XofZncontainsa critical configuration in a block Sof dimension k∈2,nwhen there exist two points {p,p}∈Znthat are antagonists in Ss.t. X∩S={p,p}(primary case) or s.t. S\X={p,p}(secondary case). Figures 1,2and 3depict examples of critical configurations. Then, a digital set X⊂Znis said to be digitally wellcomposed (DWC) [3] when it does not contain any critical configuration. 3.2 Basics in Topology and Continuous well-composedness Definition 1 (Topological spaces [1,14]) Let Tbe a set, and let Ube a set of subsets of Tsuch that: –Tand ∅are in U, – Any union of elements of Uis in U, – Any finite intersection of elements of Uis in U. Then, Uis said to be a topology, and the pair (T,U)is called a topological space. The elements of Tare called the points of (T,U), and the elements of Uare called the open Fig. 4 The continuous analog of the set {0,1}×{0,1,2,3} sets of (T,U). We will abusively say that Tis a topological space, assuming it is supplied with its topology U. An open set which contains a point of Tis said to be a neighborhood of this point. For any subset Yof T, we denote by Ycits complement in T; that is, Yc=T\Y.LetTbe a topological space. A set Y⊆Tis said to be closed when it is the complement of an open set in T. Definition 2 ([18]) A topological space Mis said to be locally Euclidean of dimension n≥0atx∈Mif xhas a neighborhood that is homeomorphic to an open subset of Rn. Definition 3 Asecond countable space is a topological space Xwhose topology has a countable basis, that is, there exists some countable collection U={Ui}∞ i=1of open sets of X such that any open subset of Xcan be written as a union of elements of some subfamily of U. Definition 4 AHausdorff space is a topological space where distinct points have disjoint neighborhoods. Definition 5 ([18]) A topological n-manifold M with boundary with n≥0 is a second countable Hausdorff space that is locally Euclidean of dimension nat each x∈M, and such that there exists for any x∈Man open set Ucontaining x and a homeomorphism φU:U→Rnor a homeomorphism φU:U→R≥0×Rn−1. Let us recall what is continuous well-composedness for nD sets according to Latecki [16,17]. The continuous analog CA(p)of a point p∈Znis the closed unit cube centered at this point with faces parallel to the coordinate planes: CA(p)={p∈Rn;p−p∞≤1/2}. Note that for any p∈Zn, the topological space CA(p) is an example of (connected and compact) topological manifold with boundary, and the set Rnis a topological manifold without boundary. The continuous analog C A(X)of a digital set X ⊂Zn (see Fig. 4) is the union of the continuous analogs of the points belonging to the set X: CA(X)= p∈X CA(p). 134 Fig. 5 Boundary of the continuous analog of a set: in dashed circles, the elements pof X, in gray the squares corresponding to CA(p)centered at the points p, and in red the boundary of the continuous analog of Xall around X[This picture is better viewed in color.] (Color figure online) However, contrary to CA(p), a topological space CA(X) (with Xsome digital subset of Zn) is not necessarily a topological manifold, as depicted later (see Fig. 11). Then, we will denote by bdCA(X)the topological boundary (see Fig. 5)ofCA(X): bdCA(X)=CA(X)\Int(CA(X)), where Int(.) is the (topological) interior operator. That is, Int(CA(X)) is a subset of CA(X)which is open and maximal in the inclusion sense. Let XbeasubsetofZn.Wesaythat Xisa continuous wellcomposed set (CWC) when the boundary of its continuous analog bdCA(X)is a (n−1)-manifold, that is, if for any point p∈X, the (open) neighborhood of pin bdCA(X)is homeomorphic1to Rn−1. Note that it is well known that the boundary of the continuous analog is self-dual: Proposition 1 Let X be a digital subset of Zn, then: bdCA(X)=bdCA(Xc). Thus, any digital set Xsubset of Znis CWC iff its complement Xcis CWC. 3.3 Local Homology Since it will be useful in the sequel, let us recall that for A and Btwo sets, the Cartesian product of Aand Bis denoted by A×Band is equal to {(a,b);a∈A,b∈B}. 3.3.1 Cubical Sets Definition 6 (Definition 2.1 p. 40 of [13]) An elementary interval is a closed interval I⊂Rof the form I=[l,l+1],or I={l}, for some l∈Z. Elementary intervals that consist of a single point are said to be degenerate, while those of length 1 are said to be nondegenerate. Definition 7 (Definition 2.3 p. 40 of [13]) An elementary cube Q in Rnis a finite product of elementary intervals, that is, Q=I1×···× In⊂Rn whereeach Iiis an elementaryinterval.Theset of elementary cubes in Rnis denoted by Kn. Note: It is important not to confuse the n-dimensional cubes CA(p)for p∈Zn, used to build the continuous analogs of discrete sets, with k-cubes (with k∈0,n)used in cubical homology, which represent the faces of these ndimensional cubes seen as cubical complexes and allow us to compute homology groups. Remark also that a translation by half coordinates is needed to convert CA(p)or its faces into a k-cube (and conversely). For example, in 1D, the 1cube [0,1]is centered at x=1 2when CA(0)=−1 2,1 2is centered at x=0 and then we use a translation of −1 2to convert the 1-cube into CA(0). However, these translations can be ignored in this paper since topological properties are preserved by translations in Rn. Definition 8 (Definition 2.4 p. 41 of [13]) Let Q=I1×···× In⊂Rnbe an elementary cube. The interval Iiis referred to as the ith component of Qand is written as Ii(Q).The dimension of Qis defined to be the number of nondegenerate components in Qand is denoted by dim(Q). Also, we define Kk:= {Q∈K;dim(Q)=k} and Kn k:= Kk∩Kn. Definition 9 (Definition 2.9 p. 43 of [13]) A set X⊂Rnis cubical if Xcan be written as a finite union of elementary cubes. If it is a cubical set, we adopt the following notation: K(X):= {Q∈K;Q⊆X} and Kk(X):= {Q∈K(X);dim(Q)=k}. Definition 10 (p. 47 of [13]) With each elementary k-cube Q∈Kn k, we associate an algebraic object  Qcalled an elementary k-chain of Rn. The set of all elementary k-chains of Rnis denoted by 1 We call homeomorphism a bicontinuous bijection. When there exists some homeomorphism f : A → B such that B = f (A), we say that these spaces are homeomorphic. 135  Kn k:= {  Q;Q∈Kn k}, and the set of all elementary chains of Rnis given by n  k=0 Kn k. Given any finite collection { Q1,..., Qm}, we are allowed to consider sums of the form α1 Q1+···+αm Qm where α1,...,α mare arbitrary integers. In particular, for each Q∈Kn k, define  Q:Kn k→Zby  Q(P):= 1ifP=Q, 0 otherwise, and let 0 :Kn k→Zbe the zero function, namely, 0(Q)=0 for all Q∈Kn kThen,  Qis the elementary chain dual to the elementary cube Q. Definition 11 (Definition 2.16 p. 48 of [13]) The group Cn k of k-dimensional chains of Rn(k-chains for short) is the free Abelian group generated by the elementary chains of  Kn k.In particular,  Kn kis the basis of Cn k. Definition 12 (Definition 2.23 p. 51 of [13]) Given two elementary cubes P∈Kn kand Q∈Kn k, we define the cubical product of  Pand  Qsuch as  P Q:=  P×Q. 3.3.2 Chain Complexes and Boundary Operator Definition 13 (Definition 2.27 p. 53 of [13]) Let X⊂Rnbe a cubical set. Let  K(X):= {  Q;Q∈K(X)}. Then, Ck(X) is the subgroup of Cn kgenerated by the elements of  Kk(X) and is referred to as the set of k-chains of X. Since we know that X⊂Rn, it is not necessary to write a superscript nin  Kk(X)and Ck(X). Note that given any c∈Ck(X), we have the decomposition c= Qi∈K(X) αi Qi where αi∈Z. Definition 14 (Definition 2.31 p. 54 of [13]) Given k∈Z, the cubical boundary operator ∂k:Cn k→Cn k−1is a homomorphism of free Abelian groups, which is defined for an elementary chain  Q∈ Kn kby induction on the embedding number as follows. Consider first the case n=1. Then, Qis an elementary interval and hence Q={l}∈K1 0or Q=[l,l+1]∈K1 1for some l∈Z. Define ∂k Q:= 0ifQ={l},  {l+1}−  {l}if Q=[l,l+1]. Note that kcan take here two different values, k=0if Q={l}and k=1ifQ={l,l+1}. Now assume that n>1. Let I=I1(Q)and P=I2(Q)× ···×In(Q), then we can write that  Q= I P. Define ∂k Q:= ∂k1 I P+(−1)k1 I∂k2 P, where k1=dim(I)and k2=dim(P). Finally, we extend the definition to all chains by linearity; that is, if c=α1 Q1+ ···+αm Qm, then ∂kc:= α1∂k Q1+···+αm∂k Qm. Proposition 2 Let Q =[0,1]k⊂Rnbe a k-elementary cube with k ≥1. Then, the boundary of  Q equals ∂k Q:= k−1  i=0 (−1)iAlg [0,1]i×{1}×[0,1]k−1−i − k−1  i=0 (−1)iAlg [0,1]i×{0}×[0,1]k−1−i, where Alg(P)is just a notation representing  P. Proof The proof follows from Definitions 12 and 14. Proposition 3 (Proposition 2.39 p. 280 of [13]) Let X⊂Rn be a cubical set. Then, ∂k(Ck(X)) ⊆Ck−1(X). Definition 15 (Definition 2.40 p. 59 of [13]) The boundary operator for the cubical set Xis defined to be ∂X k:Ck(X)→Ck−1(X) obtained by restricting ∂k:Cn k→Cn k−1to Ck(X). Definition 16 (Definition 2.41 p. 59 of [13]) The cubical chain complex for the cubical set X⊂Rnis C(X):= {Ck(X), ∂X k}k∈Z, 136 where Ck(X)are the groups of cubical k-chains generated by K(X)and ∂X kis the cubical boundary operator restricted to X. 3.3.3 Homology Groups Definition 17 (p. 60 of [13]) Let X⊆Rnbe a cubical set. A k-chain c∈Ck(X)is called a cycle in Xif ∂kc=0. The set of all k-cycles in X, which is denoted by Zk(X),isker∂X k and forms a subgroup of Ck(X). Explicitly, Zk(X):= ker ∂X k=Ck(X)∩ker ∂k⊆Ck(X). Ak-chain c∈Ck(X)is called a boundary in Xif there exists c∈Ck+1(X)such that ∂k+1c=c. Thus, the set of boundary elements in Ck(X), which is denoted by Bk(X), consists of the image of ∂X k+1. Since ∂X k+1is a homomorphism, BK(X) is a subgroup of Ck(X). Explicitly, Bk(X):= im ∂X k+1=∂k+1(Ck+1(X)) ⊆Ck(X). Definition 21 (Definition9.1 p. 280 of [13]) A pair of cubical sets Xand Awith the property that A⊆Xis called cubical pair and is denoted by (X,A). Relative homology is used to compute how two spaces A,Xsuch that A⊆Xdiffer from each other. Intuitively, we want to compute the homology of Xmodulo A:we want to ignore the set Aand everything connected to it. In other words, we want to work with chains belonging to C(X)/C(A), which leads to the following definition: Definition 22 (Definition 9.3 p. 280 of [13]) Let (X,A)be a cubical pair. The relative chains of Xmodulo A are the elements of the quotient groups Ck(X,A):= Ck(X)/Ck(A). The equivalence class of a chain c∈C(X)relative to C(A) is denoted by [c]A. Note that for each k,Ck(X,A)is a free Abelian group. The relative chain complex of Xmodulo A is given by {Ck(X,A), ∂(X,A) k} where ∂(X,A) k:Ck(X,A)→Ck−1(X,A)is defined by ∂(X,A) k[c]A:= [∂Xc]A. Obviously, this map satisfies ∂(X,A) k−1∂(X,A) k=0. The relative chain complex gives rise to the relative k-cycles: Zk(X,A):= ker ∂(X,A) k, the relative k-boundaries Bk(X,A):= im ∂(X,A) k+1, and finally the relative homology groups: Hk(X,A):= Zk(X,A)/Bk(X,A). Note that for c∈Ck(X), we can write [c]A=c+Ck(A) using the coset notation since [c]Arepresents the equivalence class whose representative is c. Proposition 4 (Proposition 9.4 p. 281 of [13]) Let Xbe an (edge-)connected cubical set and let A be a non-empty cubical subset of X. Then, H0(X,A)=0. Recall that since ∂k ∂k+1 = 0 (Proposition 2.37, pp.58 of [13]), every boundary is a cycle and thus Bk (X) is a subgroup of Zk (X). We say that two cycles c1, c2 ∈ Zk (X) are homologous and we write c1 ∼ c2 if c1 − c2 is a boundary in Ck (X), that is, c1 − c2 ∈ Bk (X).The equivalence classes are then the elements of the quotient group Zk (X)/Bk (X). Definition 18 (Definition 2.42 p. 60 of [13]) The k-th homology group is the quotient group Hk (X) := Zk (X)/Bk (X). The homology of X is the collection of all homology groups of X. The shorthand notation for this is H(X) := {Hk (X)}k∈Z. Definition 19 (Definition 2.43 p. 60 of [13]) Given c ∈ Zk (X), [c]∈ Hk (X) is the homology class of c in X. Definition 20 (Definition 2.50 p. 67 of [13]) A sequence of vertices V0,..., Vn ∈ K0(X) is an edge path in X if there exists edges E1,..., En ∈ K1(X) such that Vi−1, Vi are the two faces of Ei for i = 1,...,n.For V , V  ∈ K0(X),we write V ∼X V  if there exists an edge path V0,..., Vn ∈ K0(X) in X such that V = V0 and V  = Vn. We say that X is edge-connected if V ∼X V  for any V , V  ∈ K0(X). 3.3.4 Relative Homology Now, we recall some background in matter of relative homology. 137 3.3.5 Exact Sequences Definition 23 (Definition 9.15 p. 289 of [13]) A sequence of groups and homomorphisms ···→G3ψ3 −→ G2ψ2 −→ G1→... is said to be exact at G2when im ψ3=ker ψ2. It is an exact sequence if it is exact at every group. Corollary 1 (The exact homology sequence of a pair (Corollary 9.26 p. 297 of [13])) Let (X,A)be a cubical pair. Then, there is a long exact sequence: ···→Hk+1(A)ι∗ −→ Hk+1(X)π∗ −→ Hk+1(X,A)∂∗ −→ Hk(A)→... where ι:C(A)−→ C(X)is the inclusion map and π: C(X)→C(X,A)is the quotient map. 3.3.6 The First Isomorphism Theorem Let us briefly recall the first isomorphism theorem, critical to compute homology groups in the diagrams depicted at the end of the paper. Theorem 1 The first isomorphism theorem states that for two groups G and H, with φa homomorphism from G to H, then G/ker(φ) ≃im (φ). 3.3.7 Mayer–Vietoris Sequence of a Pair Theorem 2 (p. 142 of [19]) Acubical subset X0of a cubical set Xis a cubical set which is a subset of X. Let Xbe a cubical set; let X0,X1be two cubical subsets. of Xsuch that X=X0∪X1. Let L =X0∩X1. Then, there exists an exact sequence: ···→Hk(L)φk →Hk(X0)⊕Hk(X1)ψk →Hk(X)∂k →Hk−1(L)→... called the Mayer–Vietoris sequence of (X0,X1). The interested reader can refer to the proof of this theorem in [19] (pp. 142) to get the details about which homomorphisms were used to obtain such a remarkable result. 3.3.8 Manifolds and Local Homology Definition 24 ([21]) A cubical set Xis said to be locally a homological n-manifold at x∈Xif the homology groups {Hi(X,X\{x})}i∈Zsatisfy: Hi(X,X\{x})=Zwhen i=n, 0 otherwise. Fig. 6 How to compute ξ(z)(the encircled disks) from a given point z (the not-encircled disks of the same color) (Color figure online) Then, Xis said to be a n-dimensional homological manifold ifit is locally an n-dimensional homological manifoldat each point x∈X. Theorem 3 ([21]) A topological manifold is a homological manifold. More details about local homology can be found in [15, 22]. 4 The Proof that CWCness Implies DWCness in n-D To prove that CWCness implies DWCness in n-D, we proceed by counterposition: we prove that when a digital set contains a primary or secondary critical configuration, then the boundary of its continuous analog is not a homological (n−1)-manifold,andthennotatopological(n−1)-manifold. In the sequel, we will use the notations described in Table 1 and progressively detailed along this section. 4.1 Properties of the Continuous Analog Operator We define the round operator round(·)for any value v∈ R\Z 2\Zas round(v) =wwhere wis the integer such that v∈]w−1 2,w+1 2[. Notations 1 From now on, we will write for z ∈Rnand for ε>0: B∞(z,ε):= {x∈Rn;x−z∞<ε}. Notations 2 Let z be an element of Rn. We define (see Fig. 6): ξ(z):= q∈Zn;z∈CA(q) Remarkably, ξ(z)is also the intersection of the closed ball B∞(z,1/2)with Zn. For a given z∈Rn, the following notation is an alternative way to determine which points of Znare the centers of the continuous analogs which contain z. Due to its definition based on the Cartesian product, it will be easier to manage it in our n-dimensional proofs. 138 Table 1 Summary of the main notations of Sect. 4.1 XcRn\XX⊂Rn XcZn\XX⊂Zn CA(p)The continuous analog of pp∈Zn CA(X)The continuous analog of the set XX⊂Zn bdCA(X)Boundary of the continuous analog of the set XX⊂Zn B∞(z,ε) {x∈Rn;x−z∞<ε}Notation 1z∈Rn,ε >0 ξ(z){q∈Zn;z∈CA(q)}Notation 2z∈Rn ξalt(z)×i∈1,nξalt iNotation 3z∈Rn (v) -operator Notation 4v∈R CA1D(v) [v−1 2,v+1 2]Notation 5v∈R CA1D(T)∪v∈TCA1D(v) Notation 5T⊂Z Notations 3 Let z be an element of Rn. We define: ξalt(z):= ×i∈1,nξalt i, where for any i ∈1,n, ξalt i:= zi−1 2,zi+1 2when zi∈Z 2\Z, {round(zi)}otherwise. Proposition 5 For any z ∈R, we have the following property: ξ(z)=ξalt(z). Proof Let zbe an element of Rn. Let us remark that q∈ξ(z) is equivalent to say that q∈Znsuch that z∈CA(q), that is, z−q∞≤1 2. Now let qbe an element of ξalt(z). Then, for any i∈1,n, qi∈ξalt i, which implies that we have 3 possible cases: – when zi/∈Z 2\Z,qi=round(zi)∈Zand then |zi−qi|≤ 1 2, – when zi∈Z 2\Zandqi=zi−1 2,qi∈Zand|qi−zi|≤1 2, – when zi∈Z 2\Zandqi=zi+1 2,qi∈Zand|qi−zi|≤1 2, then q−z∞≤1 2and q∈Zn, then q∈ξ(z). Now let qbe an element of ξ(z). Then, q∈Znsuch that z−q∞≤1 2. Then, for any i∈1,n,|zi−qi|≤1 2.The consequence is that for any i∈1,n,−1 2≤qi−zi≤1 2, that is: zi−1 2≤qi≤zi+1 2.(1) When zi∈Z 2\Z, we obtain that qi∈zi−1 2,zi+1 2since qi∈Z, then qi∈{zi−1 2,zi+1 2}. When zi/∈Z 2\Z,we Fig. 7 When the interior of the continuous analog of pintersects the continuous analog of some set X,thenpbelongs to X obtain that there exists a unique qithat satisfies (1), and this value is round(zi), then qi∈{round(zi)}. The proof is done.  The goal of this section is to prove Theorem 4(see page15). As the reader will understand easily,before proving such a theorem, we need to understand how the continuous analog relates the points of Znand the unitary cubes centered at points of Zn. Proposition 6 Let X be a subset of Znand let p be an element of Zn. Then, {Int(CA(p)) ∩CA(X)=∅ }⇒{p∈X}. Proof This proposition is depicted in Fig. 7. Let us assume that z∈Int(CA(p)) ∩CA(X). Since z∈Int(CA(p)), then z−p∞<1 2. In addition, since z∈CA(X), there exists some q∈Xsuch that z−q∞≤1 2. Since q−p∞= q−z+z−p∞≤q−z∞+z−p∞<1, then q=p, and then p∈X. As we can see in the next proposition, the continuous analog is also strongly related to ξ. 139 Fig. 8 When a point z(each non-encircled colored disk) belongs to the interior of the continuous analog of some set X(see the gray dashed component), then ξ(z)(depicted by the encircled disks of the same color) is included in X(Color figure online) Proposition 7 Let X be a subset of Zn, and let z be an element of Rn. Then, z∈Int(CA(X)) ⇒ξ(z)⊆X. Proof This proposition is depicted in Fig. 8. Let us assume that zbelongs to Int(CA(X)), then there exists some neighborhood Vzof zsuch that Vz⊆CA(X). Then, there exists some small value ε>0 such that B∞(z,ε)⊆Vz⊆CA(X). Now, two cases are possible: – either z∈Zn, then ξ(z)={z}, and z∈Int(CA(z)), thus z∈Int(CA(z))∩CA(X), which implies byProposition6 that z∈X, then ξ(z)⊆X. –orz/∈Zn, then for every q∈ξ(z), there exists a point qεdefined such as: qε:= z+ε 2(q−z), which belongs to B∞(z,ε) ⊆CA(X). Also, we can reformulate: qε:= 1−ε 2z+ε 2q, which leads easily to qε∈Int(CA(q)), thus it satisfies: qε∈Int(CA(q)) ∩CA(X), and then q∈Xby Proposition 6. We can conclude with ξ(z)⊆X. This concludes the proof.  Since in Theorem 4, we will use the boundary operator used on the continuous analog, we can assume that we will needthefollowingpropositionrelatingthecontinuousanalog of a set and the one of its complementary. Fig. 9 Let Xbe the set of three points of Z2pictured as dashed circles. The interior of the continuous analog of a set X(in light gray) does not intersect the continuous analog of the complementary of X(in dark gray) Proposition 8 Let X be a subset of Zn. Then, Int(CA(X)) ∩CA(Xc)=∅. Proof This proposition is depicted in Fig. 9. Let us assume that there exists some z∈Int(CA(X)) ∩CA(Xc). Because z∈Int(CA(X)), by Proposition 7,thesetξ(z)satisfies ξ(z)⊆X. Let us denote by #(.) the cardinality operator. Then, – either #(ξ(z)) =1, and we are in the case where there exists a unique p∈Xsuch that p−z∞≤1 2, then for all q∈Zn\{p}(containing Xc), q−z∞>1 2, and then z/∈CA(Xc): we obtain a contradiction. –or#(ξ(z)) ≥2, then for all p∈ξ(z),p−z∞=1 2, when for every q∈Zn\ξ(z),q−z∞>1 2. Because ξ(z)⊆X,q⊆Zn\ξ(z), and then for any q∈Xc, q−z∞>1 2. This way, z/∈CA(Xc); one more time, we obtain a contradiction. The proof is done.  Now let us recall and prove an elementary property of the continuous analog relative to the continuous analog of the complementary, it will be used in the next proposition. Proposition 9 Let X be a subset of Zn, then: Int(CA(Xc)) =(CA(X))c. Proof Let zbe an element of Int(CA(X)). Then, there exists some neighborhood Vzof zwhich is included in CA(X). Then, Vz∩(CA(X))c=∅. Let us assume that: z∈CA(Xc)(2) then there exists y∈Xcsuch that z−y∞≤1 2. Because CA(y)is closed, then Vz∩CA(y)=∅. However by (2), 146 and since m∈Z 2n, by Proposition 17, then ξ(m)=S, then: bdCA(X)∩B∞(m,(m)) =bdCA({p,p})∩B∞(m,(m)). Since pand pare k-antagonists with k≥2, by Lemma 4, we obtain: bdCA(X)∩B∞(m,(m)) =(bdCA(p)∪bdCA(p)) ∩B∞(m,(m)). Now let us treat the secondary case: S\X={p,p}. Then, the fact that Xcontains a secondary critical configuration is equivalent to say that Xccontains a primary critical configuration: Xc∩S={p,p}. Then, by Proposition 1, bdCA(X)=bdCA(Xc), and then by following the same reasoning as for the primary case: bdCA(X)∩B∞(m,(m)) =bdCA(Xc)∩B∞(m,(m)), =bdCA(Xc∩ξ(m)) ∩B∞(m,(m)), =bdCA({p,p})∩B∞(m,(m)), =(bdCA(p)∪bdCA(p)) ∩B∞(m,ε). This concludes the proof.  Corollary 2 Let us assume that a digital set X ⊂Zncontains a critical configuration in some block S of center m such that X∩S={p,p}or S \X={p,p}.IfbdCA(p)∪bdCA(p) is not locally Euclidean of dimension (n−1), then bdCA(X) is not locally Euclidean of dimension (n−1)neither. In other words, it is sufficient to show that the set {p,p}of X is not CWC to show that X is not CWC. 4.3 The n-D Proof From now on, in this subsection, we assume that we have a digital set X⊂Znwhich contains some primary critical configuration at the block Sof center m∈Z 2nand such that X∩S={p,p}. In addition, we define: Xp,p:= bdCA(p)∪bdCA(p). The notations of Sect. 4.3 are summarized in Table 2. Thanks to Lemma 1, we know that mbelongs to Xp,p, and thanks to Corollary 2, we know that if Xp,pis not locally homeomorphic to ]0,1[n−1at m, then {p,p}is not CWC, and then Xis not CWC neither. To prove that {p,p}is not CWC, we are going to use homology. Indeed, if we can prove that: Hn−1(Xp,p,Xp,p\{m})= Z, then Xp,pis not a homological manifold at m, and then it is not a topological manifold. For this aim, we will use the first isomorphism theorem. Since Xp,pis the union of two (n−1)-spheres sharing a (n−k)-cube, we can deduce its homology groups: Property 2 The homology groups of Xp,pare the following: ⎧ ⎨ ⎩ H0(Xp,p)=Z, Hn−1(Xp,p)=Z⊕Z, Hk∈Z\{0,n−1}(Xp,p)=0. Now let us define: A=Xp,p\{m}, then we obtain the following values of the homology groups of A(they will be used toprove next that the homology group Hn−1(Xp,p,A)is not equal to Z). Property 3 Let Z∗=Z\{0}. Let A =Xp,p\{m}, then: – When k =n=2, we have: H0(A)=Z2, Hk∈Z∗(A)=0, – When k =2and n =3, we have: ⎧ ⎨ ⎩ H0(A)=Z, H1(A)=Z, Hk∈Z\{0,1}(A)=0, – When k =2and n ≥4, we have: Hn−1(A)=0, Hn−2(A)=Z, – When k =n≥3, we have: H0(A)=Z2, Hn∈Z∗(A)=0, – When k =n−1and n ≥4, we have: ⎧ ⎨ ⎩ Hn(A)=0, Hn−1(A)=0, Hn−2(A)=0, – When k ∈3,n−2and n ≥5, we have: ⎧ ⎨ ⎩ Hn(A)=0, Hn−1(A)=0, Hn−2(A)=0, 147 Table 2 Summary of the main notations of Sect. 4.3 n≥2 The dimension of the ambient space XA digital subset of Znwhich is not DWC SOne of the blocks where a critical configuration occurs in X k≥2 The antagonism order of Srelatively to X p,pThe two k-antagonists in S X∩S={p,p}The studied primary critical configuration of X m=p+p 2The center of S Xp,pbdCA(p)∪bdCA(p) Proof Let us decompose Athis way for the sequel: ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ K0=bdCA(p)\{m}, K1=bdCA(p)\{m}, I=K0∩K1, A=K0∪K1. Now let us treat each case separately. – When k=n=2, Ais homotopy equivalent to a 0sphere since it is a set of two empty 2-cubes minus their intersection. – When k=2 and n=3: –Ais made of two 3-cubes sharing a 1-cube minus its center, then it is connected and H0(A)=Z. –Iis homotopy equivalent to a 0-sphere and then: H0(I)=Z2, Hi∈Z∗(I)=0, weobtain then the Mayer–Vietoris sequence depicted below: H3(I)=0H3(K0)⊕ H3(K1)=0H3(A)=0 H2(I)=0H2(K0)⊕ H2(K1)=0H2(A)=0 H1(I)=0H1(K0)⊕ H1(K1)=0H1(A)=Z H0(I)=Z2H0(K0)⊕ H0(K1)=Z2H0(A)=Z H−1(I)=0 ι3π3 ∂3 ι2π2 ∂2 ι1π1 ∂1 ι0π0 ∂0 thus H1(A)=Z. – When k=2 and n≥4, Iis a (n−k−1)-sphere with (n−k−1)=(n−3)≥1 and then H0(I)=Z, Hn−3(I)=Z, and Hi∈Z\{0,n−3}=0. At the same time, K0and K1are contractile and then H0(K0)=H0(K1)= Zand Hi∈Z∗(K0)=Hi∈Z∗(K1)=0. Then, we obtain the Mayer–Vietoris sequence depicted below: Hn−2(K0)⊕ Hn−2(K1)=0Hn−2(A)=Z Hn−3(I)=ZHn−3(K0)⊕ Hn−3(K1)=0 ψn−2 ∂n−2 φn−3 thus Hn−2(A)=Z. – When k=n≥3, Ais a set of two empty n-cubes minus their intersection (a vertex), and then it is homotopy equivalent to a 0-sphere. – Whenk=n−1andn≥4,thenIishomotopyequivalent toa0-sphereand K0and K1arecontractile,then wehave: H0(I)=Z2, Hi∈Z∗(I)=0, H0(K0)=Z, Hi∈Z∗(K0)=0, and: H0(K1)=Z, Hi∈Z∗(K1)=0, 148 which leads to the results depicted below: Hn−1(K0)⊕ Hn−1(K1)=0Hn−1(A)=0 Hn−2(I)=0Hn−2(K0)⊕ Hn−2(K1)=0Hn−2(A)=0 Hn−3(I)=0 ψn−1 ∂n−1 φn−2ψn−2 ∂n−2 then Hn−1(A)=Hn−2(A)=0. – When k∈3,n−2and n≥5, then Iis homotopy equivalent to a (n−k−1)-sphere since it is equal to a (n−k)-ball minus its center, and because (n−k−1)≥1, we have: ⎧ ⎨ ⎩ H0(I)=Z, Hn−k−1(I)=Z, Hi∈Z\{0,n−k−1}(I)=0, Also, K0and K1are contractile, and then: H0(K0)=Z, Hi∈Z∗(K0)=0, and: H0(K1)=Z, Hi∈Z∗(K1)=0, We obtain then the results depicted below: Hn−1(K0)⊕ Hn−1(K1)=0Hn−1(A)=0 Hn−2(I)=0Hn−2(K0)⊕ Hn−2(K1)=0Hn−2(A)=0 Hn−3(I)=0 ψn−1 ∂n−1 φn−2ψn−2 ∂n−2 then Hn−1(A)=Hn−2(A)=0. This concludes the proof.  Property 4 When we have n ≥2and k =2, then: Hn−1(Xp,p,A)=Z3, and when we have n ≥3and k ∈3,n, then: Hn−1(Xp,p,A)=Z2. In other words, for any n ≥2and any k ∈2,n, we have Hn−1(Xp,p,A)= Z. Proof These results follow from the six following computations: Step 1 :Hn−1(Xp,p,A)when k=n=2 H1(A)=0H1(Xp,p)= Z2H1(Xp,p,A)= Z3 H0(A)=Z2H0(Xp,p)=ZH0(Xp,p,A)= 0 ι1π1 ∂1 ι0π0 Step 2:Hn−1(Xp,p,A)when k=2 and n=3 H2(A)=0H2(Xp,p)= Z2H2(Xp,p,A)= Z3 H1(A)=ZH1(Xp,p)=0 ι2π2 ∂2 ι1 Step 3:Hn−1(Xp,p,A)when k=2 and n≥4 Hn−1(A)=0Hn−1(Xp,p)= Z2Hn−1(Xp,p,A)= Z3 Hn−2(A)=ZHn−2(Xp,p)= 0 ιn−1πn−1 ∂n−1 ιn−2 Step 4:Hn−1(Xp,p,A)when k=n≥3 Hn−1(A)=0Hn−1(Xp,p)= Z2Hn−1(Xp,p,A)= Z2 Hn−2(A)=0 ιn−1πn−1 ∂n−1 Now that we know the important values of the homology groups of A, let us prove the following property induced by Property 3. 149 Step 5:Hn−1(Xp,p,A)when k=n−1 and n≥4 Hn−1(A)=0Hn−1(Xp,p)= Z2Hn−1(Xp,p,A)= Z2 Hn−2(A)=0 ιn−1πn−1 ∂n−1 Step 6:Hn−1(Xp,p,A)when n≥5 and k∈3,n−2 Hn−1(A)=0Hn−1(Xp,p)= Z2Hn−1(Xp,p,A)= Z2 Hn−2(A)=0 ιn−1πn−1 ∂n−1 The proof is done.  Based on Property 4, it follows that Xp,pis not locally a homological manifold at m, and then Xp,pis not locally Euclidean of dimension (n−1)at m. From this, we can conclude that Xp,pis not locally a topological (n−1)-manifold at m. Since Xp,pbehaves like bdCA(X)in the neighborhood of mby Theorem 4, then Xis not CWC. When Xcontains a secondary critical configuration, the reasoning is the same, as explained in Corollary 2. Theorem 5 For any digital set X ⊂Zn,n≥2,XisDWC when X is CWC. In other words, CWCness implies DWCness in n-D, n ≥2. 5 Conclusion We have shown in this paper that CWCness implies DWCness in n-D, which can be summarized by saying that when we do not have any topological issue in the boundary of the continuous analog of a digital subset of Zn, then this last set does not contain any critical configuration, which implies that its connectivities are equivalent. By gathering the properties relative to well-composedness coming from [7] and from the current paper, we can see that we obtain: CWC ⇒HWC ⇒DWC, where we call homology-well-composedness (HWCness) the property of a cubical set to have a homology manifold as boundary. Conversely, we know that: DWC HWC, but we do not know if HWCness implies CWCness. We propose to study this last point in future works: HWC ? ⇒CWC. References 1. Alexandrov, P.S.: Combinatorial topology, volume 1-3. Graylock (1956) 2. Boutry, N.: A study of well-composedness in n-D. PhD thesis, Université Paris-Est, France (2016) 3. Boutry, N., Géraud, T., Najman, L.: How to make n-D functions digitally well-composed in a self-dual way. In: Benediktsson, J.A., Chanussot, J., Najman, L., Talbot, H. (eds), Proceedings of the International Symposium on Mathematical Morphology (ISMM), volume 9082 of Lecture Notes in Computer Science, pp. 561–572, Reykjavik, Iceland. Springer (2015) 4. Boutry, N., Géraud, T., Najman, L.: A tutorial on wellcomposedness. J. Math. Imaging Vis. 60, 443–478 (2017) 5. Boutry, N., Gonzalez-Diaz, R., Jimenez, M.-J.: One more step towards well-composedness of cell complexes over n-D pictures. In: Discrete Geometry for Computer Imagery, volume 11414, pp. 101–114. Springer (2019) 6. Boutry,N., Gonzalez-Diaz, R., Jimenez, M.-J., Paluzo-Hildago,E.: Euler well-composedness. In: International Workshop on Combinatorial Image Analysis, volume 12148, pp. 3–19. Springer Nature (2020) 7. Boutry, N., Gonzalez-Diaz, R., Najman, L., Géraud, T.: A 4D counter-example showing that dwcness does not imply cwcness in n-D. In: International Workshop on Combinatorial Image Analysis, volume 12148 of Lecture Notes in Computer Science, pp. 73–87 (2020) 8. Boutry, N., Najman, L., Géraud, T.: About the equivalence between AWCness and DWCness. Research report, LIGM - Laboratoire d’Informatique Gaspard-Monge ; LRDE - Laboratoire de Recherche et de Développement de l’EPITA, (October 2016) 9. Boutry, N., Najman, L., Géraud, T.: Well-composedness in Alexandrov spaces implies digital well-composedness in Zn.In:Discrete Geometry for Computer Imagery, volume 10502 of Lecture Notes in Computer Science, pp. 225–237. Springer (2017) 10. Carlinet, E., Géraud, T.: MToS: a tree of shapes for multivariate images. IEEE Trans. Image Process. 24(12), 5330–5342 (2015) 11. Caselles, V., Monasse, P.: Geometric description of images as topographic maps. Lecture Notes in Computer Science, 1984, (2009) 12. Géraud, T., Carlinet, E., Crozet, S., Najman, L.: A quasi-linear algorithmto compute thetree ofshapes of n-Dimages. In: Proceedings of the International Symposium on Mathematical Morphology (ISMM), volume 7883 of Lecture Notes in Computer Science, pp. 98–110. Springer (2013) 13. Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology, vol. 157. Springer Science & Business Media, Berlin (2006) 14. Kelley, J. L.: General Topology. Courier Dover Publications, New York (2017) 150 15. Kharlap, A.È.: Local homology and cohomology, homology dimension and generalized manifolds. Matematicheskii Sbornik 138(3), 347–373 (1975) 16. Latecki, L.J.: 3D well-composed pictures. Graph. Models Image Process. 59(3), 164–172 (1997) 17. Latecki, L.J.: Well-composed sets. Adv. Imaging Electron Phys. 112, 95–163 (2000) 18. Lee, J.: Introduction to Topological Manifolds, vol. 202. Springer Science & Business Media, Berlin (2010) 19. James, R.M.: Elements of Algebraic Topology. CRC Press, Boca Raton (2018) 20. Najman, L., Géraud, T.: Discrete set-valued continuity and interpolation. In: Proceedings of the International Symposium on MathematicalMorphology(ISMM),volume7883ofLectureNotes in Computer Science, pp. 37–48. Springer (2013) 21. Ranicki, A.A., Casson, A., Sullivan, D., Armstrong, M., Rourke, C., Cooke, G.: The hauptvermutung book. Collection of papers by Casson, Sullivan, Armstrong, Cooke, Rourke and Ranicki, KMonographs in Mathematics, 1, (1996) 22. Sklyarenko, E.G.: On the theory of generalized manifolds. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 35(4), 831–843 (1971) 23. Wang, Y., Bhattacharya, P.: Digital connectivity and extended wellcomposed sets for gray images. Comput. Vis. Image Understand. 68(3), 330–345 (1997) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Nicolas Boutry received the Ing. degree (with honors) from ESIEE Paris, France, in 2002. Also, he worked from 2002 to 2006 as a Research Assistant at the Swiss Federal Institute of Technology (EPFL), Switzerland, where he worked in Biomedical Engineering and then on Image Compression. Then, he worked as a Research Engineer at MyCO2, France, on shape recognition in videos. Finally, he received the Ph.D. degree in Computer Science (about digital topology and mathematical morphology) from Université Paris-Est, France, in 2016. He is currently working at LRDE, EPITA, France, as a Research Fellow. Rocio Gonzalez-Diaz is an Associate Professor in the Department of Applied Math I at the University of Seville since 2004. She is also at the head of the Computational Image Analysis group since 2010, and Principal Researcher of Spanish projects on Computational Algebraic Topology for Computer Vision and Neural Networks: MTM2015-67072-P Project from 01-2016 to 12-2018 and PID2019107339GB-I00 Project from 062020 to 05-2023. Laurent Najman received the Habilitation à Diriger les Recherches in 2006 from the University of Marne-la-Vallée, a Ph.D. of applied mathematics from Paris-Dauphine University in 1994 with the highest honor (Félicitations du Jury) and an “Ingénieur” degree from the Ecole des Mines de Paris in 1991. After earning his engineering degree, he worked in the Central Research Laboratories of Thomson-CSF for 3 years, working on some problems of infrared image segmentation using mathematical morphology. He then joined a start-up company named Animation Science in 1995, as director of research and development. The technology of particle systems for computer graphics and scientific visualization, developed by the company under his technical leadership, received several awards, including the “European Information Technology Prize 1997” awarded by the European Commission (Esprit Programme) and by the European Council for Applied Science and Engineering and the “Hottest Products of the Year 1996” awarded by the Computer Graphics World journal. In 1998, he joined OCÉ Print Logic Technologies, as senior scientist. He worked there on various problems of image analysis dedicated to scanning and printing. After 10 years of research work on image processing and computer graphics problems in several industrial companies, he joined the Informatics Department of ESIEE, Paris, in 2002, where he is a professor and a member of the Laboratoire d’Informatique Gaspard Monge, Université Paris-Est Marne-la-Vallée. His current research interests are discrete mathematical morphology, discrete topology and discrete optimization. Thierry Géraud received a Ph.D. degree in signal and image processing from Télécom ParisTech in 1997, and the Habilitation à Diriger les Recherches from Université Paris-Est in 2012. He is one of the main authors of the Olena platform, dedicated to image processing and available as free software under the GPL license. His research interests include image processing, pattern recognition, software engineering and object-oriented scientific computing. He is currently working at EPITA Research and Development Laboratory (LRDE), Paris, France.