# Strong Euler well-composedness

Nicolas Boutry, Rocio Gonzalez-Diaz, Maria-Jose J Jimenez, Eduardo Paluzo-Hildago

► To cite this version:

Nicolas Boutry, Rocio Gonzalez-Diaz, Maria-Jose J Jimenez, Eduardo Paluzo-Hildago. Strong Euler well-composedness. Journal of Combinatorial Optimization, 2021, 44 (4), pp.3038-3055. 10.1007/s10878-021-00837-8 . hal-04871345

HAL Id: hal-04871345

https://hal.science/hal-04871345v1

Submitted on 7 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Strong Euler Well-Composedness

Nicolas Boutry · Rocio Gonzalez-Diaz · Maria-Jose Jimenez · Eduardo Paluzo-Hidalgo

Received: date / Accepted: date

**Abstract** In this paper, we define a new flavour of well-composedness, called strong Euler well-composedness. In the general setting of regular cell complexes, a regular cell complex of dimension $n$ is 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 $n$D pictures, we formally prove in this paper that strong Euler well-composedness implies digital well-composedness in any dimension $n \ge 2$ and that the converse is not true when $n \ge 4$.

**Keywords** Digital topology · Discrete geometry · Well-composedness · Cubical complexes · Manifolds · Euler characteristic.

## 1 Introduction

The concept of well-composedness of a digital set (also called *picture*) was first introduced in [14] for two-dimensional (2D) pictures and extended later in [15] 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*).

<footnote>Author names are listed in alphabetical order. This work has been partially supported by the Agencia Estatal de Investigación/10.13039/501100011033 under grant PID2019-107339GB-100 and the Agencia Andaluza del Conocimiento under grant PY20-01145.</footnote>

<footnote>N. Boutry
EPITA Research and Development Lab. (LRDE), Le Kremlin-Bicêtre, France,
E-mail: nicolas.boutry@lrde.epita.fr</footnote>

<footnote>R. Gonzalez-Diaz, M.J. Jimenez, E. Paluzo-Hidalgo
Department of Applied Mathematics (I), Universidad de Sevilla,
Campus Reina Mercedes, 41012, Sevilla, Spain,
E-mail: {rogodi,majiro,epaluzo}@us.es</footnote>
tions) for which 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 [19, 2]. 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* [18] has no ambiguous cases on well-composed pictures (no hole problem occurs), we can obtain *thin topological maps on pictures* thanks to well-composedness [17] and the *tree of shapes* is well-defined [9]. Regarding the new flavour of strong Euler well-composedness introduced in this paper, there is not 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, [1, 6, 13, 16, 18, 20]).

In [6], the concept of well-composedness and critical configuration was ex-
tended to any dimension $n \ge 2$. Then, an $n$D picture is *continuously well-
composed* if its continuous analog has a boundary surface that is an $(n-1)$D
manifold, whereas an $n$D picture is *digitally well-composed* if it does not con-
tain any critical configuration.

Equivalences between different flavours of well-composedness have been
studied in [2], namely: continuous well-composedness (CWCness), digital well-
composedness (DWCness), well-composedness in the Alexandrov sense (AWC-
ness), well-composedness based on the equivalence of connectivities (EWC-
ness) and well-composedness on arbitrary grids (AGWCness). More specifi-
cally, it is well-known that AWCness, CWCness, DWCness and EWCness are
equivalent in 2D. In 3D, only AWCness, CWCness, and DWCness are equiv-
alent. No link between AGWCness and other flavours of well-composedness is
known. For pictures of dimension $n \ge 4$, our knowledge of the logical relation-
ships between CWCness, DWCness and EWCness is very incomplete, though
it has been shown that AWCness is equivalent to DWCness (see [7]) and that
DWCness implies EWCness (see [6]). Recently, in [5], a counterexample in 4D
has been given to prove that 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 [10, 11, 3], we defined another flavour of well-composedness called self-
dual weak well-composedness (swWCness) that extends the notion of DWC-
ness to any regular cell complex. Roughly speaking, a regular cell complex
<figure><img src="image_2.png" /><figcaption>Fig. 1 A 4D counter-example showing that χWCness does not imply DWCness in 4D.</figcaption></figure>

is a topological space made up of a collection of $k$-cells (homeomorphic<fnref n="1" /> to $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 $n$D 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 $I$ if 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)$, the set of $n$-cells of $K(I)$ incident to $v$ are face-connected. In [10, 11, 3], we also developed a topological method for repairing the cubical complex $Q(I)$ canonically associated with an $n$D picture $I$ not being DWC. Such a method constructs a “simplicial decomposition” ($P_S(I)$, $P_S(bI)$) of $I$, where $bI$ is $I$'s complement (an $n$D picture that is precisely defined in Definition 1), and where $P_S(I)$ and $P_S(bI)$ satisfy the following conditions:

(1) $P_S(I)$ is a cell complex over $I$, $P_S(bI)$ is a cell complex over $bI$, and

(2) $P_S(I)$ and $P_S(bI)$ are weakly well-composed, that is, ($P_S(I)$, $P_S(bI)$) is self-dual weakly well-composed.

As it is shown in [3], in the setting of cubical complexes canonically associated with $n$D pictures, swWCness is equivalent to DWCness for all $n \ge 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 [4], we proposed an intermediary flavour of well-composedness, called Euler well-composedness ($\chi$WCness). The cell complex $K(I)$ over $I$ is $\chi$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 $\chi$WCness for $n$D pictures (in the case of $n = 2, 3, 4$) were given in [4], we have observed that, in general, $\chi$WCness does not imply DWCness. For example, consider the 4D picture $I$ in Figure 1, whose foreground is the set of points $F_I = \{(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, $I$ contains 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)$

<footnote n="1">¹ Two topological spaces are homeomorphic if there exists a bijective bicontinuous function between them.</footnote>
is $\chi$WC. This is established below in the proof of Lemma 3. That proof also shows that $Q(bI)$ is $\chi$WC. It follows from the $\chi$WCness of $Q(I)$ and $Q(bI)$ in this example that Theorem 4 of [4] is actually incorrect – its computer-assisted “proof” was unfortunately flawed. The fact that a 4D picture $I$ need not be DWC even if both of $Q(I)$ and $Q(bI)$ are $\chi$WC is a significant weakness of the concept of $\chi$WCness.

Accordingly, the present paper will introduce a new flavour of well-composability called strong Euler well-composability ($\chi^+\text{WCness}$), which is a concept more restrictive than the one of $\chi$WCness given in [4], with the aim of proving that $\chi^+\text{WCness}$ implies DWCness in any dimension $n \ge 2$, even though the converse is not true in any dimension $n \ge 4$. The authors are convinced that CWCness implies $\chi^+\text{WCness}$, but do not have a rigorous proof of this at the moment. In such a case, $\chi^+\text{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: Section 2 recalls the background needed to understand the rest of the paper. Section 3 introduces the concept of strong Euler well-composability. Section 4 shows that strong Euler well-composability implies digital well-composability. Section 5 shows that the converse is not true. Finally, Section 6 concludes the paper.

## 2 Background

First, let us introduce the concept of $n$-dimensional digital sets (also called $n$D pictures), taken from the field of digital geometry.

**Definition 1 (nD picture)** Let $n \ge 1$ be an integer and $\mathbb{Z}^n$ the set of points with integer coordinates in $\mathbb{R}^n$. An $n$D picture is a pair $I = (\mathbb{Z}^n, F_I)$, where $F_I$ is a subset of $\mathbb{Z}^n$. The set $F_I$ is called the *foreground* of $I$ and the set $\mathbb{Z}^n \setminus F_I$ the *background* of $I$. The *complement* of $I$ is defined as the $n$D picture $bI = (\mathbb{Z}^n, \mathbb{Z}^n \setminus F_I)$.

We say that a property $P$ of $n$D pictures is *self-dual* if an $n$D picture $I$ has property $P$ whenever the picture $bI$ has property $P$.

In [6], the concept of block was introduced to extend the notion of DWCness to any dimension. Given a point $z \in \mathbb{Z}^n$ and a family of vectors $\mathcal{F} = \{f^1, \dots, f^k\} \subseteq \mathcal{B}$ (where $\mathcal{B} = \{e^1, \dots, e^n\}$ is the canonical basis of $\mathbb{Z}^n$), the $k$-block associated with the pair $(z, \mathcal{F})$ is the set defined as:

$$B(z, \mathcal{F}) = \left\{ z + \sum_{i \in [1, k]} \lambda_i f^i : \lambda_i \in \{0, 1\}, \forall i \in [1, k] \right\}.$$

Thus, a 0-block is a point, a 1-block is a set of two points in $\mathbb{Z}^n$ on an unit edge, a 2-block is a set of four points on a unit square, and so on. A subset $B \subset \mathbb{Z}^n$ is called a *block* if there exists a couple $(z, \mathcal{F}) \in \mathbb{Z}^n \times \mathcal{P}(\mathcal{B})$ (where $\mathcal{P}(\mathcal{B})$ represents the set of all the subsets of $\mathcal{B}$), such that $B = B(z, \mathcal{F})$.
**Definition 2 (antagonists)** Two points $p, q$ belonging to a block $B$ are said to be antagonists in $B$ if their distance is equal to the maximum distance using the $L^1$-norm<fnref n="2" /> between two points in $B$, that is, $\|p - q\|_1 = \max\{\|r - s\|_1 : r, s \in B\}$.

*Remark 1* The antagonist of a point $p$ in a block $B$ containing $p$ exists and is unique.

Notice that when two points $(x_1, \dots, x_n)$ and $(y_1, \dots, y_n)$ in $\mathbb{Z}^n$ are antagonists in a $k$-block with $k \in [0, n]$ then there is a set $\{i_1, \dots, i_k\} \subseteq [1, n]$ such that $|x_i - y_i| = 1$ for $i \in \{i_1, \dots, i_k\}$ and $x_i = y_i$ otherwise.

**Definition 3 (critical configuration)** Let $I = (\mathbb{Z}^n, F_I)$ be an $n$D picture and $B$ a $k$-block with $k \in [2, n]$. We say that $I$ contains a critical configuration in the block $B$ if $F_I \cap B = \{p, p'\}$ or $F_I \cap B = B \setminus \{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)** An $n$D picture is said to be digitally well-composed (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 $n$D cubical 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) $\mu \in Q$ is a face of an $l$-dimensional cube ($l$-cell) $\sigma \in Q$ and $k < l$ then $\mu$ is said to be a *proper face* of $\sigma$ and $\sigma$ a proper coface of $\mu$. A *maximal cell* of $Q$ is not a proper face of any other cell of $Q$. The next definition states how an $n$D cubical complex can always be associated with an $n$D picture.

**Definition 5 (cubical complex canonically associated with an nD picture)** The cubical complex $Q(I)$ canonically associated with an $n$D picture $I = (\mathbb{Z}^n, F_I)$ is the $n$D cubical complex whose maximal cells are $n$-dimensional unit cubes centered at each point in $F_I$ and whose $(n-1)$-faces are $(n-1)$-dimensional unit cubes parallel to the coordinate hyperplanes.

Figure 2 shows, 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 \in \mathbb{Z}^n$; its $(n-1)$-faces by points under the form $p \pm \frac{1}{2}e^i$, with $e^i \in B = \{e^1, \dots, e^n\}$; in general, its $k$-faces can be encoded by points under the form $p + \sum_{i \in \{i_1, \dots, i_{n-k}\}} \lambda_i e^i$, where $\{i_1, \dots, i_{n-k}\}$

<footnote n="2">² The $L^1$-norm of a vector $\alpha = (\alpha_1, \dots, \alpha_n)$ is $||\alpha||_1 = \sum_{i \in [1, n]} |\alpha_i|$.</footnote>
<figure><img src="image_3.png" /><figcaption>**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.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**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).</figcaption></figure>

is a set of $n-k$ different indices in $\llbracket 1, n \rrbracket$ and $\lambda_i \in \{\pm \frac{1}{2}\}$. That is, $k$-cells are represented by points with $k$ integer coordinates and $n-k$ coordinates that are odd multiples of $\frac{1}{2}$.

*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 $p$ in $\mathbb{R}^n$ will be expressed as Cartesian products of its coordinates:

$$p = (p_1, \dots, p_n) = (p_1, \dots, p_i) \times (p_{i+1}, \dots, p_n) = \dots = (p_1) \times \dots \times (p_n).$$

Besides, when a coordinate is repeated $k$ times, we will write $(p_1, \dots, p_k, p_1) = (p_1)^k$. These notations could be combined. For example:

$$(p_1, p_2, p_3, p_4, p_4) = (p_1, p_2, p_3) \times (p_4)^2,$$

$$\{(p_1, p_2, 0, p_4, p_4), (p_1, p_2, 1, p_4, p_4)\} = \{(p_1, p_2, x) : x \in \{0, 1\}\} \times (p_4)^2,$$

$$\{(p_1, p_2, 0, 0), (p_1, p_2, 0, 1), (p_1, p_2, 1, 0), (p_1, p_2, 1, 1)\} = (p_1, p_2) \times \{(0), (1)\}^2.$$

The boundary surface of an $n$D cubical complex $Q$, denoted by $\partial Q$, is the $(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. 3 for toy examples.

The underlying space of an $n$D cubical complex $Q$, i.e., the union of the $n$-dimensional cubes of $Q$ as subspaces of $\mathbb{R}^n$, will be denoted by $|Q|$. An $n$D
cubical complex $Q$ is 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 $\mathbb{R}^{n-1}$.

### 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 [4].

**Definition 6 (Euler characteristic)** Let $S$ be a finite set of cells. Let $a_k$ denote the number of $k$-cells of $S$. The Euler characteristic of $S$ is defined as:

$$ \chi(S) = \sum_{k=0}^{\infty} (-1)^k a_k. $$

Recall that the Euler characteristic of a regular cell complex depends only on its underlying space's homotopy type [12, p. 146].

Although the following concepts could be defined on regular cell complexes without problem, we will define them in terms of $n$D cubical complexes, since that will be our context.

**Definition 7 (star and link)** [8] Let $\sigma$ be a cell of a given $n$D cubical complex $Q$. Then,

- The closure of $\sigma$, denoted $Cl(\sigma)$, is the set of cells having $\sigma$ as a coface$^3$. By extension, the closure of a set of cells is the union of the closure of each cell in the set.

- The star in $Q$ of $\sigma$, denoted $St_Q(\sigma)$, is the set of cells of $Q$ having $\sigma$ as a face$^4$. By extension, the star in $Q$ of a set of cells is the union of the star in $Q$ of each cell in the set.

- The link in $Q$ of $\sigma$, denoted $Lk_Q(\sigma)$, is the closure of the star in $Q$ of $\sigma$ minus the star in $Q$ of the closure of $\sigma$, that is, $Cl(St_Q(\sigma) \setminus St_QCl(\sigma))$. In other words, $Lk_Q(\sigma)$ is the set of cells in $Q$ that share a coface but no face with $\sigma$.

We need now to extend the notion of $\chi$-critical vertex given in [4] to the notion of $\chi$-critical cell.

**Definition 8 ($\chi$-critical cell)** Let $Q$ be an $n$D cubical complex, $n \ge 2$. A cell $\sigma \in \partial Q$ is $\chi$-critical for $Q$ if:

$$ \chi(Lk_Q(\sigma)) \neq \chi(\mathbb{B}^{n-1}) = 1, $$

where $\mathbb{B}^{n-1}$ is an $(n-1)$-dimensional ball.

<footnote n="3">³ Observe that $\sigma \in Cl(\sigma)$ since $\sigma$ is considered to be a coface of itself.</footnote>

<footnote n="4">⁴ Observe that $\sigma \in St_Q(\sigma)$ since $\sigma$ is considered to be a face of itself.</footnote>
For example, in all the cases of Figure 4 except for case (c), the vertex $v$ is a $\chi$-critical vertex for $Q(I)$. Nevertheless, in case (c), the edge $e$ is $\chi$-critical for $Q(I)$.

**Remark 3** Let $Q(I)$ be the cubical complex canonically associated with an $n$D picture $I$, $n \ge 1$. Let $v$ be a vertex (0-cell) of $Q(I)$. Then, $\chi(\mathrm{Cl}\,\mathrm{St}_{Q(I)}(v)) = 1$ since $|\mathrm{Cl}\,\mathrm{St}_{Q(I)}(v)|$ is contractible$^5$. Besides, $\mathrm{St}_{Q(I)}\mathrm{Cl}(v) = \mathrm{St}_{Q(I)}(v) \subseteq \mathrm{Cl}\,\mathrm{St}_{Q(I)}(v)$ since $\mathrm{Cl}\,v = \{v\}$. Therefore,

$$ \chi(\mathrm{Lk}_{Q(I)}(v)) = \chi(\mathrm{Cl}\,\mathrm{St}_{Q(I)}(v)) - \chi(\mathrm{St}_{Q(I)}(v)) = 1 - \chi(\mathrm{St}_{Q(I)}(v)). \quad (1) $$

The result below extends Remark 3 to $k$-cells with $k \ge 0$.

**Lemma 1** Let $Q(I)$ be a cubical complex canonically associated with an $n$D picture $I$ and let $\sigma$ be a $k$-cell of $Q(I)$ with $k < n$, then:

$$ \chi(\mathrm{Lk}_{Q(I)}(\sigma)) = 1 - (-1)^k \chi(\mathrm{St}_{Q(I)}(\sigma)). \quad (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

$$ \sigma = (0)^k \times (\frac{1}{2})^{n-k}. $$

Let $I_0$ be the picture such that $F_{I_0} = F_I \cap ((0) \times \mathbb{Z}^{N-1})$. Then $F_{I_0} = (0) \times F_J$ for some $(n-1)$D picture $J$. Let

$$ \sigma' = (0)^{k-1} \times (\frac{1}{2})^{n-k}. $$

Then $\sigma = (0) \times \sigma'$ and $\sigma'$ is a $(k-1)$-cell of $Q(J)$. Now,

$$ \mathrm{St}_{Q(I)}(\sigma) = ((0)^k \times \{(\frac{1}{2}), (0), (1)\}^{n-k}) \cap Q(I) $$

and $\mathrm{St}_{Q(I_0)}(\sigma) = \mathrm{St}_{Q(I)}(\sigma)$. Similarly,

$$ \mathrm{St}_{Q(J)}(\sigma') = ((0)^{k-1} \times \{(\frac{1}{2}), (0), (1)\}^{n-k}) \cap Q(J). $$

Then, it is satisfied that $\mathrm{St}_{Q(I)}(\sigma) = (0) \times \mathrm{St}_{Q(J)}(\sigma')$, which indicates that

$$ \chi(\mathrm{St}_{Q(I)}(\sigma)) = -\chi(\mathrm{St}_{Q(J)}(\sigma')). $$

Now, let us prove that $\chi(\mathrm{Lk}_{Q(I)}(\sigma)) = \chi(\mathrm{Lk}_{Q(J)}(\sigma'))$. Readily,

$$ \mathrm{Cl}\,\mathrm{St}_{Q(I)}(\sigma) = \{(0), (\frac{1}{2}), (-\frac{1}{2})\} \times \mathrm{Cl}\,\mathrm{St}_{Q(J)}(\sigma'). $$

Besides, $\mathrm{Cl}(\sigma) = \{(0), (\frac{1}{2}), (-\frac{1}{2})\} \times \mathrm{Cl}(\sigma')$ and then

$$ \mathrm{St}_{Q(I)}\mathrm{Cl}(\sigma) = \{(0), (-\frac{1}{2}), (\frac{1}{2}), (-1), (1)\} \times \mathrm{St}_{Q(J)}\mathrm{Cl}(\sigma') \cap Q(I), $$

<footnote>$^5$ A topological space is contractible if it is homotopy equivalent to a point [12, p. 2].</footnote>
from which we conclude that $L_{k_{Q(I)}}(\sigma) = \{(0), (\frac{1}{2}), (-\frac{1}{2})\} \times L_{k_{Q(J)}}(\sigma')$. Then,

$$ \begin{aligned} \chi(L_{k_{Q(I)}}(\sigma)) &= -\chi(L_{k_{Q(J)}}(\sigma')) + \chi(L_{k_{Q(J)}}(\sigma')) + \chi(L_{k_{Q(J)}}(\sigma')) \\ &= \chi(L_{k_{Q(J)}}(\sigma')). \end{aligned} $$

Now, assuming by induction that $\chi(L_{k_{Q(J)}}(\sigma')) = 1 - (-1)^{k-1}\chi(\mathrm{St}_{Q(J)}(\sigma'))$ then

$$ \begin{aligned} \chi(L_{k_{Q(I)}}(\sigma)) &= \chi(L_{k_{Q(J)}}(\sigma')) = 1 - (-1)^{k-1}\chi(\mathrm{St}_{Q(J)}(\sigma')) \\ &= 1 - (-1)^{k-1}(-\chi(\mathrm{St}_{Q(I)}(\sigma))) = 1 - (-1)^{k}\chi(\mathrm{St}_{Q(I)}(\sigma)), \end{aligned} $$

concluding the proof.

<figure><img src="image_5.png" /></figure>

It follows from Lemma 1 that a cell $\sigma \in \partial Q(I)$ is $\chi$-critical for $Q(I)$ if and only if:

$$ \chi(\mathrm{St}_{Q(I)}(\sigma)) \neq 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 $\sigma$ of $Q(I)$ ($0 < k < n$) in terms of the star and the link of a vertex $v$ of $Q(J)$, where $J$ is an $(n-k)$-dimensional “slice” of $I$ and we have that $\chi(\mathrm{St}_{Q(I)}(\sigma)) = (-1)^k\chi(\mathrm{St}_{Q(J)}(v))$ and, therefore, $\chi(L_{k_{Q(I)}}(\sigma)) = \chi(L_{k_{Q(J)}}(v))$.

**Remark 4** Let $Q(I)$ be the cubical complex canonically associated with an $n$D picture $I$, $n \ge 2$. Then, for any vertex $v \in \partial Q(I)$, there exist $2^k \binom{n}{k}$ $k$-cells in $\mathrm{St}_{Q(I) \cup Q(bI)}(v)$. Hence,

$$ \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v)) = \sum_{k=0}^{n} (-1)^k 2^k \binom{n}{k} = (-1)^n. $$

Besides, since $\chi(\mathrm{St}_{Q(I)}(v)) = \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v)) - \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(I)}(v))$ then:

$$ \chi(\mathrm{St}_{Q(I)}(v)) = (-1)^n - \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(I)}(v)). $$

Moreover, if $\sigma$ is an $r$-cell of $\partial Q(I)$ then for $0 \le k \le n-r$ the number of $(r+k)$-cells in $\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma)$ is $2^k \binom{n-r}{k}$, and

$$ \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma)) = \sum_{k=0}^{n-r} (-1)^{r+k} 2^k \binom{n-r}{k} = (-1)^n. $$

Then,

$$ \chi(\mathrm{St}_{Q(I)}(\sigma)) = (-1)^n - \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma) \setminus \mathrm{St}_{Q(I)}(\sigma)). $$

**Definition 9 (strong Euler well-composedness)** An $n$D cubical complex is Euler well-composed ($\chi$WC) if it has no $\chi$-critical vertices [4]. It is strongly Euler well-composed ($\chi^+$WC) if it has no $\chi$-critical cells.
<figure><img src="image_6.png" /><figcaption>Fig. 4 Different cases of a vertex v on the boundary of the cubical complex $Q(I)$ canonically associated with an nD picture I. $L_{k_{Q(I)}}(v)$ is drawn in grey. a) A 2D case of a $\chi$-critical vertex v, with $\chi(L_{k_{Q(I)}}(v)) = 2$. b) A 3D case of a $\chi$-critical vertex v, with $\chi(L_{k_{Q(I)}}(v)) = 2$. c) A 3D case of a vertex v on the boundary that is not a $\chi$-critical vertex, since $\chi(L_{k_{Q(I)}}(v)) = 1$. d) Complementary configuration of case c) in which v is a $\chi$-critical vertex, with $\chi(L_{k_{Q(I)}}(v)) = 0$.</figcaption></figure>

Observe that the definition of $\chi^{+}WCness$ is more restrictive than the definition of $\chi$WCness given in [4] in the sense that we do not only check if there are $\chi$-critical vertices (or 0-cells) but we also check if there are $\chi$-critical $k$-cells for any $k \in \mathbb{Z}$. With the following lemma, we can conclude that $\chi^{+}WCness$ and $DWCness$ are equivalent when we deal with cubical complexes canonically associated with nD pictures for $n = 2, 3$.

**Lemma 2** Let $Q(I)$ be the cubical complex canonically associated with an nD picture I for $n = 2, 3$. Then $Q(I)$ has no $\chi$-critical cells if and only if I is $DWC$.

*Proof* We have verified by computer search that there are no counterexamples to this lemma. □

With the following result, we can conclude that the definition of $s\chi$WCness given in [4] is weaker than the definition of $\chi^{+}WCness$ given in this paper for nD pictures with $n \ge 4$, that is, $s\chi$WCness does not imply $\chi^{+}WCness$ for nD pictures with $n \ge 4$.

**Lemma 3** The fact that neither $Q(I)$ nor $Q(bI)$ has $\chi$-critical vertices does not imply that $Q(I)$ has no $\chi$-critical cells for any nD picture I with $n \ge 4$.

*Proof* Let us compute a counterexample for the statement presented above. Consider the cubical complex $Q(I)$ canonically associated with an nD picture $I = (\mathbb{Z}^n, F_I)$ with $n \ge 4$, such that $F_I = \{(0, 1, 0), (0, 0, 0), (0, 0, 1), (1, 0, 1), (1, 1, 1), (0, 2, 0), (0, 2, 1), (1, 2, 1)\} \times (0)^{n-3}$ (see Figure 1). Then, the set of $n$-cells of $Q(I)$ incident to the $(n-3)$-cell

$$ \sigma = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}) \times (0)^{n-3} $$

is:

$$ \{(0, 1, 0), (0, 0, 0), (0, 0, 1), (1, 0, 1), (1, 1, 1)\} \times (0)^{n-3} $$
<figure><img src="image_7.png" /><figcaption>Fig. 5 An example of a 4D picture whose canonically associated cubical complex has the χ-critical cell $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 0)$. The five red points constitute the foreground of the picture. Observe that the 4D picture of Figure 1 can be obtained from this 4D picture by a reflection in the hyperplane $x_2 = 1$.</figcaption></figure>

(see Figure 5). Observe that $\sigma \in \partial Q(I)$ and $\text{St}_{Q(I)}(\sigma)$ is the set:

$$ \begin{aligned} & \{\sigma\} \cup \{(x, \frac{1}{2}, \frac{1}{2}), (\frac{1}{2}, x, \frac{1}{2}), (\frac{1}{2}, \frac{1}{2}, x) : x \in \{0, 1\}\} \times (0)^{n-3} \\ & \cup \{(x, y, \frac{1}{2}), (\frac{1}{2}, x, y) : x, y \in \{0, 1\}\} \times (0)^{n-3} \\ & \cup \{(0, \frac{1}{2}, 0), (0, \frac{1}{2}, 1), (1, \frac{1}{2}, 1)\} \times (0)^{n-3} \\ & \cup \{(0, 1, 0), (0, 0, 0), (0, 0, 1), (1, 0, 1), (1, 1, 1)\} \times (0)^{n-3}. \end{aligned} $$

Then,

$$ \chi(\text{St}_{Q(I)}(\sigma)) = (-1)^{n-3} + 6(-1)^{n-2} + 11(-1)^{n-1} + 5(-1)^n = (-1)^{n+1} \neq 0. $$

Therefore, $\sigma$ is a $\chi$-critical ($n-3$)-cell for $Q(I)$ (with $n-3 \ge 1$), so $Q(I)$ is not $\chi$-WC.

Now, let us prove that none of the vertices of $\partial Q(I)$ are $\chi$-critical for $Q(I)$ or $Q(bI)$. That is, let us prove that if $v \in \partial Q(I)$ then $\chi(\text{St}_{Q(I)}(v)) = 0 = \chi(\text{St}_{Q(bI)}(v))$.

First, let us see that $\chi(\text{St}_{Q(I)}(v)) = 0$.

Let $x_n$ be the last coordinate of $v$ (then $x_n = \pm \frac{1}{2}$). Let

$$ A = \{\sigma = (y_1, \dots, y_n) \in \text{St}_{Q(I)}(v) : y_n = 0\} $$

and

$$ B = \{\sigma = (y_1, \dots, y_n) \in \text{St}_{Q(I)}(v) : y_n = x_n\}. $$

Then, $\text{St}_{Q(I)}(v) = A \sqcup B$. Let $f: A \to B$ such that $f(\sigma) = (y_1, \dots, y_{n-1}, x_n)$ for each $\sigma = (y_1, \dots, y_{n-1}, 0) \in A$. Then, $\chi(\{f(\sigma)\}) = -\chi(\{\sigma\})$ for any $\sigma \in A$.
<figure><img src="image_8.png" /><figcaption>**Fig. 6** A drawing of the vertices of the cubical complex $Q(I)$ canonically associated with the $n$D picture $I$ defined in the proof of Lemma 3. Each colored point represents a set of $2^{n-3}$ vertices of $\partial Q(I)$ that have the same first three coordinates; the point’s color indicates the isometry class of $\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v)$ for every vertex $v$ in that set. That is, $\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v)$ is isometric to $A_1$ if the point is red, isometric to $A_2$ if it is green, isometric to $A_3$ if it is blue, and isometric to $A_4$ if it is purple ($A_1, A_2, A_3$, and $A_4$ are defined in the proof of Lemma 3).</figcaption></figure>

since the dimension of $f(\sigma)$ is one less than the dimension of $\sigma$. Therefore,

$$ \chi(\mathrm{St}_{Q(I)}(v)) = \chi(A) + \chi(B) = \sum_{\sigma \in A} \chi(\{\sigma\}) + \sum_{\sigma \in A} \chi(\{f(\sigma)\}) = 0. $$

Second, let us see that $\chi(\mathrm{St}_{Q(bI)}(v)) = 0$.

Let us observe that $\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v)$ is isometric to one of the following sets:

$$ A_1 = \{(0, 0, 0)\} \times (0)^{n-3}, $$

$$ A_2 = \{(0, 0, 0), (0, 0, x) : x \in \{\frac{1}{2}, 1\}\} \times (0)^{n-3}, $$

$$ A_3 = \{(0, 0, 0), (0, 0, x), (x, 0, 1) : x \in \{\frac{1}{2}, 1\}\} \times (0)^{n-3}, $$

$$ A_4 = \{(0, 0, 0), (0, 0, x), (x, 0, 1), (0, x, 0), (1, x, 1) : x \in \{\frac{1}{2}, 1\}\} \times (0)^{n-3}. $$

An intuition of this last assertion can be obtained by looking at Figure 6 where each colored point represents a set of $2^{n-3}$ vertices of $\partial Q(I)$ that have the same first three coordinates, and for every vertex $v$ in that set the point’s color indicates which set $A_i$ the set $\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v) \subset \mathrm{St}_{Q(I)}(v)$ is isometric to. In all cases,

$$ \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v)) = (-1)^n. $$

Finally, by Remark 4,

$$ \chi(\mathrm{St}_{Q(bI)}(v)) = (-1)^n - \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v) \setminus \mathrm{St}_{Q(bI)}(v)) = 0. $$

**Definition 10 (self-dual strong Euler well-composedness)** The cubical complex $Q(I)$ canonically associated with an $n$D picture $I$ is self-dual strongly Euler well-composed ($s\chi$WC) if both $Q(I)$ and $Q(bI)$ are $\chi$WC.
**Lemma 4** If $Q(I)$ is $s\chi^+WC$ then, for any vertex $v$ of $\partial Q(I)$, the following equation is satisfied:

$$ \chi(\mathrm{Lk}_{\partial Q(I)}(v)) = \chi(S^{n-2}) = 1 + (-1)^{n-2} $$

or, equivalently,

$$ \chi(\mathrm{St}_{\partial Q(I)}(v)) = 1 - \chi(S^{n-1}) = (-1)^{n-1}. $$

*Proof* Let us assume that

$$ \chi(\mathrm{Lk}_{Q(I)}(v)) = 1 = \chi(\mathrm{Lk}_{Q(bI)}(v)), $$

that is,

$$ \chi(\mathrm{St}_{Q(I)}(v)) = 0 = \chi(\mathrm{St}_{Q(bI)}(v)). $$

Now, since

$$ \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(v)) = \chi(\mathrm{St}_{Q(I)}(v)) + \chi(\mathrm{St}_{Q(bI)}(v)) - \chi(\mathrm{St}_{\partial Q(I)}(v)) $$

then, using Remark 4, we conclude that:

$$ \chi(\mathrm{St}_{\partial Q(I)}(v)) = (-1)^{n-1}. $$

□

Nevertheless, the converse is not true.

**Lemma 5** The fact that $\chi(\mathrm{St}_{\partial Q(I)}(v)) = (-1)^{n-1}$ for any vertex $v \in \partial Q(I)$ does not imply that $Q(I)$ is $\chi$WC nor that $I$ is DWC.

*Proof* Case (b) of Figure 4 is a simple counterexample. In that case, we have that $\chi(\mathrm{St}_{\partial Q(I)}(v)) = (-1)^{n-1}$ but $\chi(\mathrm{St}_{Q(I)}(v)) = -1 \neq 0$. Besides, case (b) of Figure 4 is not DWC. □

In the next section, we will prove our main result, that is, $\chi^+WCness$ implies $DWCness$ in any dimension $n \ge 2$ although the converse is not true when $n \ge 4$. Therefore, in principle, we do not need the concept of self-dual $\chi^+WCness$ for our purpose. We end this section with the open question of whether self-dual strong Euler well-composedness is in fact equivalent to strong Euler well-composedness.

## 4 Strong Euler well-composedness implies digital well-composedness

Let us now see one of the two main results of the paper, stating that $\chi^+WCness$ implies $DWCness$ for any $n$D picture with $n \ge 2$.

**Theorem 1** *Strong Euler well-composedness implies digital well-composedness in nD for $n \ge 2$.*
Proof Let us prove that not DWCness implies not $\chi^+$WCness. Let $I = (\mathbb{Z}^n, F_I)$ be an $n$D picture with $n \ge 2$, and let $k$ be an integer in $[0, n-2]$. Let $\{p, p'\}$ be two antagonists in an $(n-k)$-block $B$ that yields a critical configuration for $I$.

Let us assume, first, that $F_I \cap B = \{p, p'\}$, that is, it is a critical configuration. Then $\frac{p+p'}{2}$ encodes a $k$-cell $\sigma$ in $\partial Q(I)$. Let us prove that $\sigma$ is a $\chi$-critical cell for $\tilde{Q}(I)$, that is, let us prove that $\chi(\mathrm{Lk}_{Q(I)}(\sigma)) \neq 1$. First, observe that $\mathrm{Lk}_{Q(I)}(\sigma) = L(p) \sqcup L(p')$ where, for $q = p, p'$,

$$L(q) = \{\mu \in \mathrm{Lk}_{Q(I)}(\sigma) : \mu \text{ is a face of the } n\text{-cell centered at } q\}.$$

Now, since $\chi(L(p)) = \chi(L(p'))$, then

$$\chi(\mathrm{Lk}_{Q(I)}(\sigma)) = \chi(L(p) \sqcup L(p')) = \chi(L(p)) + \chi(L(p')) = 2\chi(L(p)) \neq 1$$

and then $\sigma$ is $\chi$-critical for $Q(I)$. In the other case, where $B \setminus F_I = \{p, p'\}$, when $\sigma$ is the $k$-cell centered at $\frac{p+p'}{2}$, the set $\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma) \setminus \mathrm{St}_{Q(I)}(\sigma)$ consists just of the two $n$-cells centered at $p$ and $p'$. Hence, $\chi(\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma) \setminus \mathrm{St}_{Q(I)}(\sigma)) = 2(-1)^n$ and, by Remark 4,

$$\chi(\mathrm{St}_{Q(I)}(\sigma)) = (-1)^n - \chi(\mathrm{St}_{Q(I) \cup Q(bI)}(\sigma) \setminus \mathrm{St}_{Q(I)}(\sigma)) = (-1)^n - 2(-1)^n,$$

so $\chi(\mathrm{St}_{Q(I)}(\sigma)) = (-1)^{n+1} \neq 0$ and then $\sigma$ is $\chi$-critical for $Q(I)$. $\square$

## 5 Digital well-composedness does not imply (strong) Euler well-composedness

Let us see next, an example of an $n$D picture ($n \ge 4$) that is digital well-composed but not Euler well-composed, showing that DWCness does not imply $\chi$WCness and, therefore, DWCness does not imply $\chi^+$WCness.

**Theorem 2** DWCness does not imply $\chi$WCness for any dimension $n \ge 4$.

Proof Let us fix $n \ge 4$. We will give an example of an $n$D picture $I_n = (\mathbb{Z}^n, F_{I_n})$ (see Figure 7) such that $I_n$ is DWC but $Q(I_n)$ is not $\chi$WC. Let

$$F_{I_n} = \{ (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1), \\ (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 0), (1, 0, 0, 0) \} \times \{(0), (1)\}^{n-4}.$$

To prove that $I_n$ is DWC we only have to check that it does not contain any critical configuration. This has been checked in [4] when $n = 4$ and the same reasoning can be extended to $n$D for $n > 4$.

Now, observe that the set of $n$-cubes of $Q(I_n)$ encoded by $F_{I_n}$ are incident to the vertex $v = (\frac{1}{2})^n \in \partial Q(I)$. Then, to prove that $Q(I_n)$ is not $\chi$WC, it is enough to check that $\chi(\mathrm{St}_{Q(I_n)}(v)) \neq 0$.

Let us see that the counterexample works in 4D. In that case, $v = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})$ and the hypercubes in $\mathrm{St}_{Q(I_4)}(v)$ are encoded by the points $(0, 0, 0, 0), (0, 0, 0, 1)$,
<figure><img src="image_9.png" /><figcaption>Fig. 7 As explained in Theorem 2, for $n \ge 4$, there exists a family of DWC pictures $I_n$ such that $Q(I_n)$ are not $\chi$WC. This picture corresponds to the case $n = 4$.</figcaption></figure>

(0, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 0) and (1, 0, 0, 0). Then, it is easy to check that $\chi(\mathrm{St}_{Q(I_4)}(v)) = 1 - 8 + 24 - 24 + 8 = 1 \neq 0$, so $Q(I_4)$ is not $\chi$WC. Another way to see that Theorem 2 holds when $n = 4$ is that $\mathrm{St}_{Q(I_4) \cup Q(bI_4)}(v) \setminus \mathrm{St}_{Q(I_4)}(v) = A \sqcup B$ where $A$ is composed by the eight 3-cells centered at the barycenters of the eight edges that joint two gray points of Figure 7 and $B$ is composed by the eight 4-cells centered at the eight grey points. Then,

$$ \chi(\mathrm{St}_{Q(I_4) \cup Q(bI_4)}(v) \setminus \mathrm{St}_{Q(I_4)}(v)) = \chi(A) + \chi(B) = 8 - 8 = 0 $$

and hence, by Remark 4,

$$ \chi(\mathrm{St}_{Q(I_4)}(v)) = (-1)^4 - \chi(\mathrm{St}_{Q(I_4) \cup Q(bI_4)}(v) \setminus \mathrm{St}_{Q(I_4)}(v)) = (-1)^4 - 0 = 1 \neq 0. $$

Consider the general case $n > 4$. Let $d \in [0, n]$. Let us denote by $a_{(d,n)}$ the number of $d$-cells incident to $v$ in the $n$D cubical complex $Q(I_n)$. Then,

$$ a_{(0,n)} = 1, $$

$$ \begin{gathered} a_{(d,n)} = 2a_{(d-1,n-1)} + a_{(d,n-1)} \text{ for } d \in [1, n-1] \text{ because a } d\text{-cell in } Q(I_n) \\ \text{is constructed by adding an extra coordinate of 0 or 1 at the end to the} \\ \text{list of coordinates of a point encoding a } (d-1)\text{-cell in } Q(I_{n-1}) \text{ or adding} \\ \text{the coordinate } \frac{1}{2} \text{ at the end of the list of coordinates of a point encoding a} \\ \text{$d$-cell in } Q(I_{n-1}), \end{gathered} $$

$$ a_{(n,n)} = 2a_{(n-1,n-1)}. $$
Therefore,

$$
\begin{align*}
\chi(\mathrm{St}_{Q(I_n)}(v)) &= \sum_{d \in [0, n]} (-1)^d a_{(d,n)} = 1 + \sum_{d \in [1, n]} (-1)^d a_{(d,n)} \\
&= 1 + 2 \sum_{d \in [1, n]} (-1)^d a_{(d-1, n-1)} + \sum_{d \in [1, n-1]} (-1)^d a_{(d, n-1)} \\
&= 1 - 2 \sum_{d \in [0, n-1]} (-1)^d a_{(d, n-1)} + \sum_{d \in [1, n-1]} (-1)^d a_{(d, n-1)} \\
&= 1 - 2\chi(\mathrm{St}_{Q(I_{n-1})}(v)) + \chi(\mathrm{St}_{Q(I_{n-1})}(v)) - 1 \\
&= -\chi(\mathrm{St}_{Q(I_{n-1})}(v)).
\end{align*}
$$

Since $\chi(\mathrm{St}_{Q(I_4)}(v)) = 1$ then

$$
\chi(\mathrm{St}_{Q(I_n)}(v)) = (-1)^n \neq 0.
$$

So, $Q(I_n)$ is not $\chi$WC.

□

**Corollary 1** *DWCness does not imply* $\chi^{+}$WCness for any dimension $n \ge 4$.

We finish this section with a table summarising the main results obtained so
far regarding the concepts of DWCness and $\chi^{+}$WCness:

<table>
  <tr>
    <td>n = 2, 3</td>
    <td>DWCness &harr; &chi;<sup>+</sup>WCness</td>
  </tr>
  <tr>
    <td>n &ge; 4</td>
    <td>DWCness &harr; &chi;<sup>+</sup>WCness</td>
  </tr>
</table>

**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 well-composedness given in [4]. We have proven two fundamental proper-
ties: first, strong Euler well-composedness implies digital well-composedness in
any dimension $n \ge 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 \ge 4$.

As a future work, we plan to prove that the definition of $\chi^{+}$WCness provided
in this paper is robust to cubical barycentric subdivisions. Observe that a
cubical barycentric subdivision of $Q(I)$ is the $n$D cubical complex canonically
associated with the linear interpolation of the $n$D picture $I$ in all the possible
directions $e^i$, being $\{e^1, \dots, e^n\}$ the canonical basis of $\mathbb{Z}^n$. This is another
reason why we believe that it is a better choice to define well-composedness
based on $\chi$-critical cells and not only on $\chi$-critical vertices as it was done in
[4].
We also plan to prove that if we apply the reparation method given in [10, 11, 3] to any $\chi$-critical cell, then $P_S(I)$ (i.e., the simplicial subdivision of the “repaired complex” $P(I)$) is $\tilde{\chi}$WC, going a step forward to our ultimate goal that is to prove that $P(I)$ is a CWC regular cell complex.

## Data availability

The datasets generated during the current study are available in the github repository, https://github.com/Cimagroup/Strong-Euler-Well-Composed.

**Acknowledgements** We are really grateful to the reviewers for their suggestions and comments.

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

1. Boutry, N., Géraud, T., Najman, L.: How to make nD images well-composed without interpolation. In: 2015 IEEE International Conference on Image Processing (ICIP), pp. 2149–2153. IEEE (2015)

2. Boutry, N., Géraud, T., Najman, L.: A tutorial on well-composedness. Journal of Mathematical Imaging and Vision **60**(3), 443–478 (2018)

3. Boutry, N., Gonzalez-Diaz, R., Jimenez, M.J.: Weakly well-composed cell complexes over nD pictures. Information Sciences **499**, 62–83 (2019)

4. Boutry, N., Gonzalez-Diaz, R., Jimenez, M.J., Paluzo-Hildago, E.: Euler well-composedness. In: T. Lukic, R.P. Barneva, V. Brimkov, L. Comic, N. Sladoje (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, pp. 3–19. Springer (2020)

5. Boutry, N., Gonzalez-Diaz, R., Najman, L., Géraud, T.: A 4d counter-example showing that DWCness does not imply CWCness in nD. In: T. Lukic, R.P. Barneva, V. Brimkov, L. Comic, N. Sladoje (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, pp. 73–87. Springer (2020)

6. Boutry, N., Géraud, T., Najman, L.: 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, pp. 561–572. Springer (2015)
7. Boutry, N., Najman, L., Géraud, T.: Equivalence between digital well-composedness and well-composedness in the sense of alexandrov on n-d cubical grids. Journal of Mathematical Imaging and Vision pp. 1–49 (2020)

8. Edelsbrunner, H., Harer, J.: Computational topology: an introduction. American Mathematical Soc. (2010)

9. Géraud, T., Carlinet, E., Crozet, S., Najman, L.: 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, pp. 98–110. Springer (2013)

10. Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B.: 3D well-composed polyhedral complexes. Discrete Applied Mathematics **183**, 59–77 (2015)

11. Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B.: Efficiently storing well-composed polyhedral complexes computed over 3D binary images. Journal of Mathematical Imaging and Vision **59**(1), 106–122 (2017)

12. Hatcher, A.: Algebraic topology. Cambridge University Press (2002)

13. Lachaud, J.O., Montanvert, A.: Continuous analogs of digital boundaries: A topological approach to iso-surfaces. Graphical models **62**(3), 129–164 (2000)

14. Latecki, L., Eckhardt, U., Rosenfeld, A.: Well-composed sets. CVIU **61**(1), 70–83 (1995)

15. Latecki, L.J.: 3D well-composed pictures. Graphical Models and Image Processing **59**(3), 164–172 (1997)

16. Latecki, L.J.: Discrete representation of spatial objects in computer vision. Kluwer Academic (1998)

17. Marchadier, J., Arquès, D., Michelin, S.: Thinning grayscale well-composed images. Pattern Recognition Letters **25**(5), 581–590 (2004)

18. Siqueira, M., Latecki, L., Tustison, N., Gallier, J., Gee, J.: Topological repairing of 3D digital images. Journal of Mathematical Imaging and Vision **30**, 249–274 (2008)

19. Siqueira, M., Latecki, L.J., Gallier, J.: Making 3d binary digital images well-composed. In: SPIE, Vision Geometry XIII, vol. 5675, pp. 150–164. International Society for Optics and Photonics (2005)

20. Stelldinger, P., Latecki, L.J.: 3D object digitization: Majority interpolation and marching cubes. In: 18th International Conference on Pattern Recognition, vol. 2, pp. 1173–1176. IEEE (2006)