Strong Euler well-composedness

Journal of Combinatorial Optimization https://doi.org/10.1007/s10878-021-00837-8 Strong Euler well-composedness Nicolas Boutry1·Rocio Gonzalez-Diaz2·Maria-Jose Jimenez2· Eduardo Paluzo-Hildago2 Accepted: 23 November 2021 © The Author(s) 2021 Abstract In this paper, we define a new flavour of well-composedness, called strong Euler wellcomposedness. In the general setting of regular cell complexes, a regular cell complex of dimension nis strongly Euler well-composed if the Euler characteristic of the link of each boundary cell is 1, which is the Euler characteristic of an (n−1)-dimensional ball. Working in the particular setting of cubical complexes canonically associated with nD pictures, we formally prove in this paper that strong Euler well-composedness implies digital well-composedness in any dimension n≥2 and that the converse is not true when n≥4. Keywords Digital topology ·Discrete geometry ·Well-composedness ·Cubical complexes ·Manifolds ·Euler characteristic Author names are listed in alphabetical order. This work has been partially supported by Grant PID2019- 107339GB-I00 funded by MCIN/AEI/10.13039/501100011033 and Grant P20_01145 funded by Agencia Andaluza del Conocimiento. BRocio Gonzalez-Diaz [email protected] Nicolas Boutry [email protected] Maria-Jose Jimenez [email protected] Eduardo Paluzo-Hildago [email protected] 1EPITA Research and Development Laboratory (LRDE), Le Kremlin-Bicêtre, France 2Departamento de Matematica Aplicada I, Universidad de Sevilla, Campus Reina Mercedes, 41012 Seville, Spain 123 Journal of Combinatorial Optimization 1 Introduction The concept of well-composedness of a digital set (also called picture) was first introduced in Latecki et al. (1995) for two-dimensional (2D) pictures and extended later in Latecki (1997) for three-dimensional (3D) pictures: a well-composed picture satisfies that its continuous analog has a boundary surface that is a manifold. The concept is described in terms of forbidden subsets (also called critical configurations)forwhich the picture is not well-composed. 3D well-composed pictures may have some computational advantages regarding the application of several algorithms in computer vision, computer graphics and image processing (Siqueira et al. 2005; Boutry et al. 2018). For example, the topology of a given 2D picture can be preserved by rigid transformations thanks to well-composedness; topology-preserving front propagation can lead to well-composed segmentation; Euler numbers of 2D pictures can be computed locally thanks to well-composedness; well-composed Jordan curves are known to separate the digital plane; the boundary of the continuous analog of a well-composed 3D picture is a manifold. Furthermore, numerous applications related to well-composed pictures exist: the Marching Cubes Algorithm (Siqueira et al. 2008) has no ambiguous cases on well-composed pictures (no hole problem occurs), we can obtain thin topological maps on pictures thanks to well-composedness (Marchadier et al. 2004) and the tree of shapes is well-defined (Géraud et al. 2013). Regarding the new flavour of strong Euler well-composedness introduced in this paper, there is no known application so far. Nevertheless, since strong Euler well-composedness can be defined on regular cell complexes and because it implies DWCness on cubical grids, we think that this flavour of well-composedness could be used in wider applications such as, for example, the computation of thin topological maps on regular cell complexes. In general, pictures are not a priori well-composed. Nevertheless, there are several “repairing” methods for turning them into well-composed pictures (see, for example, Boutry et al. 2015a,b; Lachaud and Montanvert 2000; Latecki 1998; Siqueira et al. 2008; Stelldinger and Latecki 2006). In Boutry et al. (2015b), the concept of well-composedness and critical configuration was extended to any dimension n≥2. Then, an nD picture is continuously well-composed if its continuous analog has a boundary surface that is an (n−1)D manifold, whereas an nD picture is digitally well-composed if it does not contain any critical configuration. Equivalences between different flavours of well-composedness have been studied in Boutry et al. (2018), namely: continuous well-composedness (CWCness), digital wellcomposedness (DWCness), well-composedness in the Alexandrov sense (AWCness), well-composedness based on the equivalence of connectivities (EWCness) and wellcomposedness on arbitrary grids (AGWCness). More specifically, it is well-known that AWCness, CWCness, DWCness and EWCness are equivalent in 2D. In 3D, only AWCness, CWCness, and DWCness are equivalent. No link between AGWCness and other flavours of well-composedness is known. For pictures of dimension n≥4, our knowledge of the logical relationships between CWCness, DWCness and EWCness is very incomplete, though it has been shown that AWCness is equivalent to DWCness (see Boutry et al. 2020c) and that DWCness implies EWCness (see Boutry et al. 2015b). Recently, in Boutry et al. (2020b), a counterexample in 4D has been given to prove that 123 Journal of Combinatorial Optimization DWCness does not imply CWCness, which the authors consider to be an important result since it breaks with the idea that all the different flavours of well-composedness are equivalent. In Gonzalez-Diaz et al. (2015,2017), Boutry et al. (2019), we defined another flavour of well-composedness called self-dual weak well-composedness (swWCness) that extends the notion of DWCness to any regular cell complex. Roughly speaking, a regular cell complex is a topological space made up of a collection of k-cells (homeomorphic1to k-dimensional balls) glued together by their boundaries. A regular cell complex satisfying that any of its k-cell is a k-dimensional cube is referred to as a cubical complex. A cubical complex Q(I)can always be associated with any nD picture I(we will see later how to construct Q(I)from I). We say that a regular cell complex K(I)is a cell complex over Iif there exists a deformation retraction from K(I)to Q(I). Besides, K(I)is said to be weakly well-composed if, for each vertex v on the boundary of K(I),thesetofn-cells of K(I)incident to vare face-connected. In Gonzalez-Diaz et al. (2015,2017), Boutry et al. (2019), we also developed a topological method for repairing the cubical complex Q(I)canonically associated with an nD picture Inot being DWC. Such a method constructs a “simplicial decomposition” PS(I),PS(bI)of I, where bI is I’s complement (an nD picture that is precisely defined in Definition 1), and where PS(I)and PS(bI)satisfy the following conditions: (1) PS(I)is a cell complex over I,PS(bI)is a cell complex over bI, and (2) PS(I)and PS(bI)are weakly well-composed, that is, PS(I),PS(bI)is self-dual weakly well-composed. As it is shown in Boutry et al. (2019), in the setting of cubical complexes canonically associated with nD pictures, swWCness is equivalent to DWCness for all n≥2. Our ultimate goal is to prove that our topological reparation method provides CWC regular cell complexes. Since, according to us, such a goal is not reachable yet, in Boutry et al. (2020a), we proposed an intermediary flavour of well-composedness, called Euler wellcomposedness (χWCness). The cell complex K(I)over Iis χWC if the Euler characteristic of the link of each vertex of the boundary of K(I)is equal to 1, which is the Euler characteristic of an (n−1)-dimensional ball. Although partial results regarding χWCness for nD pictures (in the case of n=2,3,4) were given in Boutry et al. (2020a), we have observed that, in general, χWCness does not imply DWC- ness. For example, consider the 4D picture Iin Fig. 1, whose foreground is the set of points FI={(0,1,0,0),(0,0,0,0),(0,0,1,0),(1,0,1,0),(1,1,1,0),(0,2,0,0), (0,2,1,0),(1,2,1,0)}. Clearly, Icontains the 2D critical configuration {p,p}where p=(0,1,0,0)and p=(1,1,1,0), while it can be shown that Q(I)is χWC. This is established below in the proof of Lemma 3. That proof also shows that Q(bI)is χWC.ItfollowsfromtheχWCness of Q(I)and Q(bI)in this example that Theorem 4 of Boutry et al. (2020a) is actually incorrect – its computer-assisted “proof” was unfortunately flawed. The fact that a 4D picture Ineed not be DWC even if both of Q(I)and Q(bI)are χWC is a significant weakness of the concept of χWCness. 1Two topological spaces are homeomorphic if there exists a biyective bicontinuous function between them. 123 Journal of Combinatorial Optimization Fig. 1 A 4D counter-example showing that χWCness does not imply DWCness in 4D Accordingly, the present paper will introduce a new flavour of well-composedness called strong Euler well-composedness (+ χWCness), which is a concept more restrictive than the one of χWCness given in Boutry et al. (2020a), with the aim of proving that + χWCness implies DWCness in any dimension n≥2, even though the converse is not true in any dimension n≥4. The authors are convinced that CWCness implies + χWCness, but do not have a rigorous proof of this at the moment. In such a case, + χWCness would be an effectively computable property useful to detect cases in which the cubical complex canonically associated with a DWC picture is not CWC. The plan is the following: Sect. 2recalls the background needed to understand the rest of the paper. Section 3introduces the concept of strong Euler wellcomposedness. Section 4shows that strong Euler well-composedness implies digital well-composedness. Section 5shows that the converse is not true. Finally, Sect. 6 concludes the paper. 2 Background First, let us introduce the concept of n-dimensional digital sets (also called nDpictures), taken from the field of digital geometry. Definition 1 (nDpicture)Letn≥1 be an integer and Znthe set of points with integer coordinates in Rn.AnnD picture is a pair I=(Zn,FI), where FIis a subset of Zn. The set FIis called the foreground of Iand the set Zn\FIthe background of I.The complement of Iis defined as the nD picture bI =(Zn,Zn\FI). We say that a property Pof nD pictures is self-dual if an nD picture Ihas property Pwhenever the picture bI has property P. In Boutry et al. (2015b), the concept of block was introduced to extend the notion of DWCness to any dimension. Given a point z∈Znand a family of vectors F= {f1,..., fk}⊆B(where B={e1,...,en}is the canonical basis of Zn), the k-block associated with the pair (z,F)is the set defined as: B(z,F)=⎧ ⎨ ⎩ z+ i∈1,k λifi:λi∈{0,1},∀i∈1,k⎫ ⎬ ⎭ . 123 Journal of Combinatorial Optimization Thus, a 0-block is a point, a 1-block is a set of two points in Znon an unit edge, a 2-block is a set of four points on a unit square, and so on. A subset B⊂Znis called a block if there exists a couple (z,F)∈Zn×P(B)(where P(B)represents the set of all the subsets of B), such that B=B(z,F). Definition 2 (antagonists) Two points p,qbelonging to a block Bare said to be antagonists in Bif their distance is equal to the maximum distance using the L1- norm2between two points in B, that is, p−q1=max r−s1:r,s∈B. Remark 1 The antagonist of a point pinablockBcontaining pexists and is unique. Notice that when two points (x1,...,xn)and (y1,...,yn)in Znare antagonists in a k-block with k∈0,nthen there is a set {i1,...,ik}⊆1,nsuch that |xi−yi|=1 for i∈{i1,...,ik}and xi=yiotherwise. Definition 3 (critical configuration)LetI=(Zn,FI)be an nD picture and Bakblock with k∈2,n. We say that Icontains a critical configuration in the block Bif FI∩B={p,p}or FI∩B=B\{p,p}, with p,pbeing antagonists in B. The above concept of critical configuration is used to define the notion of DWCness, based on local patterns, in any dimension. Definition 4 (digital well-composedness)AnnD picture is said to be digitally wellcomposed (DWC) if it does not contain any critical configuration in any block. Notice that the above definition of digital well-composedness is self-dual. Roughly speaking, an nDcubical complex Q is a special kind of regular cell complex made up of a collection of n-dimensional cubes glued together by their boundaries (faces). If a k-dimensional cube (k-cell) μ∈Qis a face of an -dimensional cube (-cell) σ∈Qand k<then μis said to be a proper face of σand σa proper coface of μ.Amaximal cell of Qis not a proper face of any other cell of Q.The next definition states how an nD cubical complex can always be associated with an nD picture. Definition 5 (cubical complex canonically associated with an nDpicture) The cubical complex Q(I)canonically associated with an nD picture I=(Zn,FI)is the nD cubical complex whose maximal cells are n-dimensional unit cubes centered at each point in FIand whose (n−1)-faces are (n−1)-dimensional unit cubes parallel to the coordinate hyperplanes. Figure 2shows, from left to right, the cubical complexes canonically associated with a 2D picture and a 3D picture that each have two foreground points. Notice that each cell in the cubical complex Q(I)is uniquely determined by the coordinates of its barycenter. This way, each n-dimensional cube can be encoded by its barycenter, which is a point p∈Zn; its (n−1)-faces by points under the form p±1 2ei, with ei∈B={e1,...,en}; in general, its k-faces can be encoded by points under the form p+i∈{i1,...,in−k}λiei, where {i1,...,in−k}is a set of n−kdifferent indices in 1,nand λi∈{± 1 2}. That is, k-cells are represented by points with k integer coordinates and n−kcoordinates that are odd multiples of 1 2. 2The L1-norm of a vector α=(α1,...,α n)is ||α||1=i∈1,n|αi|. 123 Journal of Combinatorial Optimization Fig. 2 Top figures: a 2D cubical complex (left) and a 3D cubical complex (right) whose maximal cells are centered at the foreground points of the pictures shown below the complexes. Points in red correspond to the foreground of the pictures whereas points in blue belong to the foreground of the complement of the pictures (Color figure online) Fig. 3 Left: a 2-dimensional cube and its faces (edges in red and vertices in blue). Right: a 3-dimensional cube and its faces (square faces in green, edges in red and vertices in blue) (Color figure online) Remark 2 In the sequel, we will identify a k-cell of Q(I)with its barycenter, if no confusion may arise. Besides, from now on, when needed and for the sake of simplicity, a point pin Rnwill be expressed as Cartesian products of its coordinates: p=(p1,...,pn)=(p1,...,pi)×(pi+1,...,pn)=···=(p1)×···×(pn). Besides, when a coordinate is repeated ktimes, we will write (p1,k ...,p1)=(p1)k. These notations could be combined. For example: (p1,p2,p3,p4,p4)=(p1,p2,p3)×(p4)2, {(p1,p2,0,p4,p4), (p1,p2,1,p4,p4)}={(p1,p2,x):x∈{0,1}} × (p4)2, {(p1,p2,0,0), (p1,p2,0,1), (p1,p2,1,0), (p1,p2,1,1)}=(p1,p2)×{(0), (1)}2. The boundary surface of an nD cubical complex Q, denoted by ∂Q,isthe(n−1)D cubical complex composed by the (n−1)-dimensional cubes that are proper faces of exactly one maximal cell of Q, together with all their faces. See Fig. 3for toy examples. The underlying space of an nD cubical complex Q, i.e., the union of the ndimensional cubes of Qas subspaces of Rn, will be denoted by |Q|.AnnD cubical complex Qis said to be (continuously) well-composed (CWC) if |∂Q|is an (n−1)D manifold, that is, each point of |∂Q|has a neighborhood in |∂Q|homeomorphic to Rn−1. 123 Journal of Combinatorial Optimization 3 Introducing the concept of strong Euler well-composedness In this section, we introduce a new concept of Euler well-composedness that is more restrictive than the one given in Boutry et al. (2020a). Definition 6 (Euler characteristic)LetSbe a finite set of cells. Let akdenote the number of k-cells of S. The Euler characteristic of Sis defined as: χ(S)= ∞  k=0 (−1)kak. Recall that the Euler characteristic of a regular cell complex depends only on its underlying space’s homotopy type (Hatcher 2002, p. 146). Although the following concepts could be defined on regular cell complexes without problem, we will define them in terms of nD cubical complexes, since that will be our context. Definition 7 (star and link) (Edelsbrunner and Harer 2010)Letσbe a cell of a given nD cubical complex Q. Then, – The closure of σ, denoted Cl (σ ), is the set of cells having σas a coface.3By extension, the closure of a set of cells is the union of the closure of each cell in the set. – The star in Qof σ, denoted StQ(σ ), is the set of cells of Qhaving σas a face.4 By extension, the star in Qof a set of cells is the union of the star in Qof each cell in the set. – The link in Qof σ, denoted LkQ(σ ), is the closure of the star in Qof σminus the star in Qof the closure of σ, that is, Cl StQ(σ )\StQCl (σ ). In other words, LkQ(σ ) is the set of cells in Qthat share a coface but no face with σ. We need now to extend the notion of χ-critical vertex given in Boutry et al. (2020a) to the notion of χ-critical cell. Definition 8 (χ-critical cell)LetQbe an nD cubical complex, n≥2. A cell σ∈∂Q is χ-critical for Qif: χLkQ(σ )= χ(Bn−1)=1, where Bn−1is an (n−1)-dimensional ball. For example, in all the cases of Fig. 4except for case (c), the vertex vis a χ-critical vertex for Q(I). Nevertheless, in case (c), the edge eis χ-critical for Q(I). Remark 3 Let Q(I)be the cubical complex canonically associated with an nD picture I,n≥1. Let vbe a vertex (0-cell) of Q(I). Then, χ(Cl StQ(I)(v)) =1 since 3Observe that σ∈Cl (σ ) since σis considered to be a coface of itself. 4Observe that σ∈StQ(σ ) since σis considered to be a face of itself. 123 Journal of Combinatorial Optimization Fig. 4 Different cases of a vertex von the boundary of the cubical complex Q(I)canonically associated with an nD picture I.LkQ(I)(v) isdrawningrey.aA2Dcaseofaχ- critical vertex v, with χLkQ(I)(v)=2. bA 3D case of a χ-critical vertex v, with χLkQ(I)(v)=2. cA 3D case of a vertex von the boundary that is not a χ-critical vertex, since χLkQ(I)(v)=1. dComplementary configuration of case c) in which vis a χ-critical vertex, with χLkQ(I)(v)=0 |Cl StQ(I)(v)|is contractible.5Besides, StQ(I)Cl (v) =StQ(I)(v) ⊆Cl StQ(I)(v) since Cl v={v}. Therefore, χLkQ(I)(v)=χCl StQ(I)(v)−χStQ(I)(v)=1−χStQ(I)(v).(1) The result below extends Remark 3to k-cells with k≥0. Lemma 1 Let Q(I)be a cubical complex canonically associated with an nD picture I and let σbe a k-cell of Q(I)with k <n, then: χLkQ(I)(σ )=1−(−1)kχStQ(I)(σ )). (2) Proof We will proceed by induction. If k=0, then Eq. (2) coincides with Eq. (1). Let k>0. Using the notation given in Remark 2, we can assume, without loss of generality, that σ=(0)k×1 2n−k . Let I0be the picture such that FI0=FI∩((0)×ZN−1). Then FI0=(0)×FJfor some (n−1)D picture J.Let σ=(0)k−1×1 2n−k . Then σ=(0)×σand σis a (k−1)-cell of Q(J).Now, StQ(I)(σ ) =(0)k×1 2,(0), (1)n−k ∩Q(I) 5A topological space is contractible if it is homotopy equivalent to a point (Hatcher 2002,p.2). 123 Journal of Combinatorial Optimization and StQ(I0)(σ ) =StQ(I)(σ ). Similarly, StQ(J)(σ )=(0)k−1×1 2,(0), (1)n−k ∩Q(J). Then, it is satisfied that StQ(I)(σ ) =(0)×StQ(J)(σ ), which indicates that χ(StQ(I)(σ )) =−χ(StQ(J)(σ )). Now, let us prove that χLkQ(I)(σ )=χLkQ(J)(σ ). Readily, Cl StQ(I)(σ ) =(0), 1 2,−1 2×Cl StQ(J)(σ ). Besides, Cl (σ ) =(0), 1 2,−1 2×Cl (σ )and then StQ(I)Cl (σ ) =(0), −1 2,1 2,(−1), (1)×StQ(J)Cl (σ )∩Q(I), from which we conclude that LkQ(I)(σ ) =(0), 1 2,−1 2×LkQ(J)(σ ). Then, χLkQ(I)(σ )=−χLkQ(J)(σ )+χLkQ(J)(σ )+χLkQ(J)(σ ) =χLkQ(J)(σ ). Now, assuming by induction that χLkQ(J)(σ )=1−(−1)k−1χStQ(J)(σ )) then χLkQ(I)(σ )=χLkQ(J)(σ )=1−(−1)k−1χStQ(J)(σ )) =1−(−1)k−1−χStQ(I)(σ ))=1−(−1)kχStQ(I)(σ )), concluding the proof.  It follows from Lemma 1that a cell σ∈∂Q(I)is χ-critical for Q(I)if and only if: χStQ(I)(σ )= 0. Notice that, following the same arguments as in the proof of Lemma 1, we can express the star and the link of any k-cell σof Q(I)(0 <k<n) in terms of the star and the link of a vertex vof Q(J), where Jis an (n−k)-dimensional “slice” of Iand we have that χStQ(I)(σ )=(−1)kχStQ(J)(v)and, therefore, χLkQ(I)(σ )= χLkQ(J)(v). 123 Journal of Combinatorial Optimization and hence, by Remark 4, χStQ(I4)(v)=(−1)4−χStQ(I4)∪Q(bI4)(v)\StQ(I4)(v)=(−1)4−0=1= 0. Consider the general case n>4. Let d∈0,n. Let us denote by a(d,n)the number of d-cells incident to vin the nD cubical complex Q(In). Then, a(0,n)=1, a(d,n)=2a(d−1,n−1)+a(d,n−1)for d∈1,n−1because a d-cell in Q(In) is constructed by adding an extra coordinate of 0 or 1 at the end to the list of coordinates of a point encoding a (d−1)-cell in Q(In−1)or adding the coordinate 1 2at the end of the list of coordinates of a point encoding a d-cell in Q(In−1), a(n,n)=2a(n−1,n−1). Therefore, χStQ(In)(v)= d∈0,n (−1)da(d,n)=1+ d∈1,n (−1)da(d,n) =1+2 d∈1,n (−1)da(d−1,n−1)+ d∈1,n−1 (−1)da(d,n−1) =1−2 d∈0,n−1 (−1)da(d,n−1)+ d∈1,n−1 (−1)da(d,n−1) =1−2χStQ(In−1)(v)+χStQ(In−1)(v)−1 =−χStQ(In−1)(v). Since χStQ(I4)(v)=1 then χStQ(In)(v)=(−1)n= 0. So, Q(In)is not χWC.  Corollary 1 DWCness does not imply + χWCness for any dimension n ≥4. We finish this section with a table summarising the main results obtained so far regarding the concepts of DWCness and + χWCness: n=2,3DWCness←→ + χWCness n≥4DWCness  ←− + χWCness 123 Journal of Combinatorial Optimization 6 Conclusions and future works In this paper, we have provided a new flavour of well-composedness, called strong Euler well-composedness, that is more restrictive than the definition of Euler wellcomposedness given in Boutry et al. (2020a). We have proven two fundamental properties: first, strong Euler well-composedness implies digital well-composedness in any dimension n≥2; second, the converse is not true: digital well-composedness does not imply strong Euler well-composedness as soon as we are in dimension n≥4. As a future work, we plan to prove that the definition of + χWCness provided in this paper is robust to cubical barycentric subdivisions. Observe that a cubical barycentric subdivision of Q(I)is the nD cubical complex canonically associated with the linear interpolation of the nD picture Iin all the possible directions ei, being {e1,...,en}the canonical basis of Zn. This is another reason why we believe that it is a better choice to define well-composedness based on χ-critical cells and not only on χ-critical vertices as it was done in Boutry et al. (2020a). We also plan to prove that if we apply the reparation method given in Gonzalez-Diaz et al. (2015,2017), Boutry et al. (2019)toanyχ-critical cell, then PS(I)(i.e., the simplicial subdivision of the “repaired complex” P(I))is+ χWC, going a step forward to our ultimate goal that is to prove that P(I)is a CWC regular cell complex. Acknowledgements We are really grateful to the reviewers for their suggestions and comments. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Data availability The datasets generated during the current study are available in the github repository, https://github.com/Cimagroup/Strong-Euler-Well-Composed. Declarations Conflict of interest The authors declare that they have no conflict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Boutry N, Géraud T, Najman L (2015) How to make nD images well-composed without interpolation. In: 2015 IEEE international conference on image processing (ICIP). IEEE, pp 2149–2153 Boutry N, Géraud T, Najman L (2015) How to make nD functions digitally well-composed in a self-dual way. In: International symposium on mathematical morphology and its applications to signal and image processing, lecture notes in computer science, vol 9082. Springer, pp 561–572 Boutry N, Géraud T, Najman L (2018) A tutorial on well-composedness. J Math Imaging Vis 60(3):443–478 123 Journal of Combinatorial Optimization Boutry N, Gonzalez-Diaz R, Jimenez MJ (2019) Weakly well-composed cell complexes over nD pictures. Inf Sci 499:62–83 Boutry N, Gonzalez-Diaz R, Jimenez MJ, Paluzo-Hildago E (2020) Euler well-composedness. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16–18, 2020, lecture notes in computer science, vol 12148. Springer, pp 3–19 Boutry N, Gonzalez-Diaz R, Najman L, Géraud T (2020) A 4d counter-example showing that DWCness does not imply CWCness in nD. In: Lukic T, Barneva RP, Brimkov V, Comic L, Sladoje N (eds) Combinatorial image analysis: proceedings of the 20th international workshop, IWCIA 2020, Novi Sad, Serbia, July 16–18, 2020, lecture notes in computer science, vol 12148. Springer, pp 73–87 Boutry N, Najman L, Géraud T (2020) Equivalence between digital well-composedness and wellcomposedness in the sense of Alexandrov on n-d cubical grids. J Math Imaging Vis 62:1285–1333 Edelsbrunner H, Harer J (2010) Computational topology: an introduction. American Mathematical Society, Providence Géraud T, Carlinet E, Crozet S, Najman L (2013) A quasi-linear algorithm to compute the tree of shapes of nD images. In: International symposium on mathematical morphology and its applications to signal and image processing. Springer, pp 98–110 Gonzalez-Diaz R, Jimenez MJ, Medrano B (2015) 3D well-composed polyhedral complexes. Discrete Appl Math 183:59–77 Gonzalez-Diaz R, Jimenez MJ, Medrano B (2017) Efficiently storing well-composed polyhedral complexes computed over 3D binary images. J Math Imaging Vis 59(1):106–122 Hatcher A (2002) Algebraic topology. Cambridge University Press, Cambridge Lachaud JO, Montanvert A (2000) Continuous analogs of digital boundaries: a topological approach to iso-surfaces. Graph Models 62(3):129–164 Latecki LJ (1997) 3D well-composed pictures. Graph Models Image Process 59(3):164–172 Latecki LJ (1998) Discrete representation of spatial objects in computer vision. Kluwer Academic, Dordrecht Latecki L, Eckhardt U, Rosenfeld A (1995) Well-composed sets. CVIU 61(1):70–83 Marchadier J, Arquès D, Michelin S (2004) Thinning grayscale well-composed images. Pattern Recognit Lett 25(5):581–590 Siqueira M, Latecki LJ, Gallier J (2005) Making 3d binary digital images well-composed. In: SPIE, vision geometry XIII, vol 5675. International Society for Optics and Photonics, pp 150–164 Siqueira M, Latecki L, Tustison N, Gallier J, Gee J (2008) Topological repairing of 3D digital images. J Math Imaging Vis 30:249–274 Stelldinger P, Latecki LJ (2006) 3D object digitization: majority interpolation and marching cubes. In: 18th international conference on pattern recognition, vol 2. IEEE, pp 1173–1176 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123