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

HAL
open science

# Weakly well-composed cell complexes over nD pictures

Nicolas Boutry, Rocio Gonzalez-Diaz, Maria-Jose Jimenez

► To cite this version:

Nicolas Boutry, Rocio Gonzalez-Diaz, Maria-Jose Jimenez. Weakly well-composed cell complexes over nD pictures. Information Sciences, 2019, 499, pp.62-83. 10.1016/j.ins.2018.06.005. hal-04871225

HAL Id: hal-04871225

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Weakly well-composed cell complexes over nD pictures

Nicolas Boutry$^{a,1}$, Rocio Gonzalez-Diaz$^{b,1}$, Maria-Jose Jimenez$^{b,1}$

$^{a}$EPITA Research and Development Lab. (LRDE), Le Kremlin-Bicêtre, France,
E-mail: nicolas.boutry@lrde.epita.fr,
https://www.lrde.epita.fr/wiki/User:Nboutry

$^b$Department of Applied Math (I), Universidad de Sevilla, Sevilla, Spain,
E-mail: {rogodi,majiro}@us.es,
http://personal.us.es/{rogodi,majiro}

Abstract

In previous work we proposed a combinatorial algorithm to “locally repair” the cubical complex $Q(I)$ that is canonically associated with a given $3D$ picture $I$. The algorithm constructs a $3D$ polyhedral complex $P(I)$ which is homotopy equivalent to $Q(I)$ and whose boundary surface is a $2D$ manifold. A polyhedral complex satisfying these properties is called *well-composed*. In the present paper we extend these results to higher dimensions. We prove that for a given $n$-dimensional picture the obtained cell complex is well-composed in a weaker sense but is still homotopy equivalent to the initial cubical complex.

**Keywords:** Digital topology, discrete geometry, well-composedness, cubical complexes, simplicial complexes, cell complexes, manifolds.

# 1. Introduction

Ensuring that the boundary of an object in a discrete image is constructed from closed surfaces in $\mathbb{R}^3$ allows to implement surface parameterization [10]. This is crucial for certain applications in *geometric modeling* [30] and *computer graphics* [11]. For example, *texture mapping* can be used to enhance visual quality of polygonal models. Also, as discussed in [12], the computation of homology groups [16] and, in particular, the computation of homology generators on a surface [7, 8, 9], can be helpful for *topology repairing, model editing* and *feature recognition*. In *discrete geometry*, it is well-known that the multigrid convergence of some geometrical estimators is slowed when there are “pinches” in the boundary of an object in a discrete image [21, 23]. Requiring that the boundary surface be a manifold avoids such problematic situations. For all these reasons, *well-composedness* [4, 24, 25, 26] (meaning that the boundary of a set is a topological manifold) is a good topological property to be required.

<footnote n="1">¹Partially supported by MINECO, FEDER/UE under grant MTM2015-67072-P. Author names listed in alphabetical order.</footnote>
Thereafter, strong results such as the Jordan Curve Theorem can be applied on the connected components of the boundary [19, 33] in 2D. Moreover, the Jordan-Brouwer separation property [20, 22] can be applied in nD. Since nD signals appear more and more frequently in applications such as 3D Magnetic Resonance Imaging and 4D Computerized Tomography scans, it is important to extend the theory of well-composedness to higher dimensions.

In digital topology, two main families of methods are used to make 2D and 3D binary images well-composed: *topological reparation*, which does not preserve the topology of the initial image in general; and *well-composed interpolation*, which typically preserves the topology but requires an increase of resolution of the whole domain of the image. Regarding topological reparations, the first 2D method was introduced by Latecki *et al.* [26], the first 3D method by Siqueira *et al.* [35] and the first nD method by Boutry *et al.* [3]. Regarding well-composed interpolations, one has to mention the 3D method of Stelldinger *et al.*, called *Majority Interpolation* [36], the nD *min/max* method of Mazo *et al.* [29], and the nD *self-dual in-between* method of Boutry *et al.* [2]. In the midst of these two families, Gonzalez-Diaz *et al.* [13] proposed a 3D method to construct well-composed cell complexes that are homotopy equivalent to the 3D cubical complex canonically associated to the given image. This can be very useful when computing (co)homological information of a set only based on its surface (see [17]). Furthermore, the cell complex resulting from this method, that is, the positions of the cells, their geometry, and their boundary face relationships, can efficiently be stored into 3D binary images [14, 15]. This method is strongly related to *boundary extraction methods*, such as the *marching cubes* of Lorensen *et al.* [27] and its nD extensions, due to Daragon *et al.* [6] (which ensures that the boundary is a *discrete surface*), and Lachaud *et al.* [22] (which ensures that the resulting boundary is a (pseudo-)manifold). However, whether or not these methods preserve the topology is unknown and a procedure for efficiently storing the resulting complex into an nD binary image is also unknown.

Finally, some other definitions of well-composedness such as the one based on the equivalence of connectivities [2], digital well-composedness [2], well-composedness in the sense of Alexandrov [2, 5, 32], or well-composedness on arbitrary grids [1, 4, 37] exist, but they do not ensure that the boundaries consist of surfaces in $\mathbb{R}^n$ and their parameterization may not be possible.

In this paper, we extend to any dimension the method presented in [13, 14, 15]. In brief, given an nD binary image $I$ (also called an nD picture), the nD cubical complex $Q(I)$ canonically associated with $I$ is constructed and stored as an nD binary image $J = (\mathbb{Z}^n, F_J)$. Each point in the foreground $F_J$ of $J$ is the barycenter of a cell of $Q(I)$ (see Section 4.1). Then, using Procedure 1, we detect the critical points of $F_J$ that correspond to critical cells of $Q(I)$ (i.e., cells that are involved in critical configurations). By applying the repairing process given in Procedure 5, we replace each critical point $p$ of $F_J$ by a suitable set $S(p)$ of points (that depends only on the coordinates of $p$), to obtain a new nD binary image $L = (\mathbb{Z}^n, F_L)$. By applying Procedure 6 to the points of $F_L$, we construct a simplicial complex $P_S(I)$ such that $Q(I)$ is a deformation retraction of $P_S(I)$. Finally, we prove that there always exists a face-connected path in $P_S(I)$ of
<figure><img src="image_3.png" /><figcaption>Figure 1: Graphical diagram of the method: we start from an nD picture $I = (\mathbb{Z}^n, F_I)$ (then $F_I \subset 4\mathbb{Z}^n$). The set $F_J$ of points in $\mathbb{Z}^n$ encodes the cells of the associated cubical complex $Q(I)$ (blue is used for 0-cells, red for 1-cells and green for 2-cells). In this example, the set $R$ of critical points is composed by the points encoding the vertex $v$ and all the cells of $Q(I)$ incident to $v$. Now, we “repair” $F_J$ to obtain a set $F_L$ of points in $\mathbb{Z}^n$. Then, we compute the simplicial complex $P_S(I)$ whose set of vertices is $F_L$. Observe that for any two $n$-simplices $\sigma$ and $\sigma'$ incident to a common vertex $v'$ in $P_S(I)$, there exists a face-connected path $\pi$ of $n$-cells in $P_S(I)$ incident to $v'$, joining $\sigma$ and $\sigma'$; therefore, $P_S(I)$ is weak well-composed.</figcaption></figure>

$n$-simplices incident to a common vertex $v'$, joining any two $n$-simplices $\sigma$ and $\sigma'$ incident to $v'$, that is, $P_S(I)$ is what we call weakly well-composed (wWC). Figure 1 graphically illustrates the basic stages of our method. At the end of the paper we include a table with main notations used.

## 2. nD Well-composed pictures

Latecki et al. introduced in [24] the notion of well-composedness for 2D pictures as those sets not containing any *critical configuration*. Later, well-composedness was extended to 3D sets in [25] defining again *forbidden* subsets that make the continuous analog of the picture have a boundary surface that is not a manifold. In [2], the concept of critical configurations (i.e., forbidden subsets) was extended to nD. In this section, after introducing some notations and definitions, we recall how we can characterize critical configurations in nD.

**Definition 1 (nD picture).** Let $n \ge 2$ be an integer and $\mathbb{Z}^n$ the set of points with integer coordinates in nD space $\mathbb{R}^n$. An nD binary image is a pair $I = (\mathbb{Z}^n, F_I)$ where $F_I$ is a finite subset of $\mathbb{Z}^n$ called foreground of $I$. If $F_I \subset 4\mathbb{Z}^n$ (i.e., coordinates are multiples of 4), we will say that $I$ is an nD picture.

We need the foreground $F_I$ included into $4\mathbb{Z}^n$ (and not $\mathbb{Z}^n$) because, as we will see later, in a first step we add new points between the elements of $F_I$ to obtain $F_J$, encoding the cubical complex associated to $I$, which justifies a scale factor of 2; in a second step, during the reparation, we add new points between points
<figure><img src="image_4.png" /><figcaption>Figure 2: Examples of blocks: in pink, $B((0,4), \emptyset)$; in red, $B((4,4), \{e^1\})$; in blue, $B((12,0), \{e^2\})$; in green, $B((16,0), \{e^1, e^2\})$.</figcaption></figure>

of $F_J$ to obtain $F_L$, encoding the repaired complex, which justifies a second factor of 2. In fact, any given nD binary image image $I_0 = (\mathbb{Z}^n, F_{I_0})$ can be transformed into an nD picture $I = (\mathbb{Z}^n, F_I)$ by setting $F_I := 4F_{I_0}$.

**Notation 2.** For integers $k \le k'$, $[[k, k')]$ denotes the set $\{k, k+1, \dots, k'-1, k'\}$.

Let $\mathbb{B} = \{e^1, \dots, e^n\}$ denote the canonical basis of $\mathbb{Z}^n$. Given a point $z \in 4\mathbb{Z}^n$ and a family of vectors $\mathcal{F} = \{f^1, \dots, f^k\} \subseteq \mathbb{B}$, we define the block of dimension $k$ associated to the couple $(z, \mathcal{F})$ (see Figure 2) as:

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

A subset $B \subset 4\mathbb{Z}^n$ is called a block if there exists a couple $(z, \mathcal{F}) \in 4\mathbb{Z}^n \times \mathcal{P}(\mathbb{B})^2$ such that $B = B(z, \mathcal{F})$. We will denote the set of blocks of $4\mathbb{Z}^n$ by $\mathcal{B}(4\mathbb{Z}^n)$.

Two points $p, q$ belonging to a block $B \in \mathcal{B}(4\mathbb{Z}^n)$ are said to be antagonists in $B$ if their distance equals the maximum distance using the $L^1$-norm<fnref n="3" /> between two points in $B$. The antagonist of a point $p$ in a block $B \in \mathcal{B}(4\mathbb{Z}^n)$ containing $p$ exists and is unique. It is denoted by $\text{antag}_B(p)$. Note that when two points $(x_1, \dots, x_n)$ and $(y_1, \dots, y_n)$ are antagonists in a block of dimension $k \in [0, n]$, then $|x_i - y_i| = 4$ for $i \in \{i_1, \dots, i_k\} \subseteq [1, n]$ and $x_i = y_i$ otherwise.

Now, let $I = (\mathbb{Z}^n, F_I)$ be an nD picture and $B \in \mathcal{B}(4\mathbb{Z}^n)$ a block of dimension $k \in [2, n]$. We say that $I$ contains a primary critical configuration of dimension $k$ in the block $B$ if $F_I \cap B = \{p, p'\}$, with $p, p'$ being two antagonists in $B$. We say that $I$ contains a secondary critical configuration of dimension $k$ in the block $B$ if $F_I \cap B = B \setminus \{p, p'\}$, with $p, p'$ being two antagonists in $B$. More generally, a critical configuration (CC) of dimension $k \in [2, n]$ is either a primary or a secondary critical configuration of dimension $k$.

**Definition 3 (DWC).** An nD picture is said to be digitally well-composed (DWC) if it does not contain any CC.

The $2n$-neighborhood of a point $p \in 4\mathbb{Z}^n$ is the set $\mathcal{N}_{2n}(p) = \{p \pm 4e^i : i \in [1, n]\}$. A sequence $(p^1, \dots, p^k)$ of elements of $4\mathbb{Z}^n$ is said to be a $2n$-path in $4\mathbb{Z}^n$ if, for any $i \in [1, k-1]$, $p^i \in \mathcal{N}_{2n}(p^{i+1})$.

<footnote n="2">²The expression $\mathcal{P}(\mathbb{B})$ represents the set of all the subsets of $\mathbb{B}$.</footnote>

<footnote n="3">³The $L^1$-norm of a vector $\alpha = (x_1, \dots, x_n)$ is $||\alpha||_1 = \sum_{i \in [1, n]} |x_i|$.</footnote>
**Proposition 4 ([2]).** Let $I = (\mathbb{Z}^n, F_I)$ be an nD picture. If $I$ is DWC then, for any pair of points $p, p'$ of $F_I$ which are antagonists in some block $B \in \mathcal{B}(4\mathbb{Z}^n)$, there exists a 2n-path in $F_I \cap B$ joining $p$ and $p'$.

**Proposition 5.** Let $I = (\mathbb{Z}^n, F_I)$ be an nD picture. If $I$ is DWIC then, for any block $B \in \mathcal{B}(4\mathbb{Z}^n)$ and for any two points $p, q \in F_I \cap B$, there exists a 2n-path in $F_I \cap B$ joining $p$ and $q$.

**Proof.** Let $B \in \mathcal{B}(4\mathbb{Z}^n)$ be a block such that $F_I \cap B$ is non-empty. For any two points $p, q \in F_I \cap B$, there exists a block $B' \subseteq B$ such that $q = \text{antag}_{B'}(p)$. Then by Proposition 4, there exists a 2n-path joining $p$ and $q$ in $F_I \cap B' \subseteq F_I \cap B$. $\square$

**3. nD wWC cell complexes**

Roughly speaking, a *regular cell complex* $K$ is a collection of cells (where $k$-cells are homeomorphic to $k$-dimensional balls) glued together by their boundaries (faces), in such a way that a non-empty intersection of any two cells of $K$ is a cell in $K$. When the $k$-cells in $K$ are $k$-dimensional cubes, we refer to $K$ as a *cubical complex*. When they are $k$-dimensional simplices (points, edges, triangles, tetrahedra, etc.), we refer to $K$ as a *simplicial complex*. Regular cell complexes have particularly nice properties, for example, their homology is effectively computable (see [28, p. 243]).

**Definition 6 (Face-connected path).** Let $\ell \in [1, n]$. Let $S$ be a set of $\ell$-cells of $K$. We say that two $\ell$-cells $\sigma$ and $\sigma'$ are face-connected in $S$ if there exists a path $\pi(\sigma, \sigma') = (\sigma_1 = \sigma, \sigma_2, \dots, \sigma_{m-1}, \sigma_m = \sigma')$ of $\ell$-cells of $S$ such that for any $i \in [1, m-1]$, $\sigma_i$ and $\sigma_{i+1}$ share exactly one $(\ell-1)$-cell of $K$. The set $S$ is face-connected if any two $\ell$-cells $\sigma$ and $\sigma'$ in $S$ are face-connected in $S$.

The set of cells incident to a cell $\sigma$ in $K$ is denoted by $A_K(\sigma)$ and the set of $\ell$-cells incident to $\sigma$, by $A_K^{(\ell)}(\sigma)$. A $k$-face $\mu$ of a cell $\sigma$ is a $k$-cell that is face of $\sigma$; it is a *proper face* of $\sigma$ if $k < \ell$ and a *maximal face* of $\sigma$ if $k = \ell - 1$. A cell of $K$ which is not a proper face of any other cell of $K$ is said to be a *maximal cell* of $K$. An *external cell* of $K$ is a proper face of exactly one maximal cell in $K$. A regular cell complex is *pure* if all its maximal cells have the same dimension. The *rank* of a cell complex $K$ is the maximal dimension of its cells. The *boundary surface* of a pure regular cell complex $K$, denoted by $\partial K$, is the regular cell complex composed by the external cells of $K$ together with all their faces. Observe that $\partial K$ is also pure.

**Definition 7 (nD cell-complex).** An nD cell complex $K$ is a pure regular cell complex of rank $n$ embedded in $\mathbb{R}^n$. The underlying space (i.e., the union of the cells as subspaces of $\mathbb{R}^n$) will be denoted by $|K|$.

An nD cell complex $K$ is said to be (continuously) well-composed if $|\partial K|$ is an $(n-1)$-manifold, that is, each point of $|\partial K|$ has a neighborhood homeomorphic to $\mathbb{R}^{n-1}$ into $|\partial K|$.
**Definition 8 (wWCness).** An nD cell complex K is weakly well-composed (wWC) if for any 0-cell $\mu$ in K, $\mathcal{A}_K^{(n)}(\mu)$ is face-connected.

We will see later, in Section 4, that if an nD picture I is DWC, then the cubical complex $Q(I)$ canonically associated to I is wWC.

**Definition 9 (Cubical complex $Q(I)$).** The nD cubical complex $Q(I)$ canonically associated to an nD picture $I = (\mathbb{Z}^n, F_I)$ is composed by those size-4 n-dimensional cubes centered at each point in $F_I$ whose $(n-1)$-faces are parallel to the coordinate hyperplanes, together with all their faces.

Roughly speaking, two topological spaces are homotopy equivalent if one can be continuously deformed into the other. A specific example of homotopy equivalence is a deformation retraction of a space $X$ onto a subspace $A$ which is a family of maps $f_t: X \to X, t \in [0,1]$, such that: $f_0(x) = x, \forall x \in X$; $f_1(X) = A$; $f_t(a) = a, \forall a \in A$ and $t \in [0,1]$. The family $\{f_t: X \to X\}_{t \in [0,1]}$ should be continuous in the sense that the associated map $F: X \times I \to X$, where $F(x,t) = f_t(x)$, is continuous. See [18, p. 2].

**Definition 10 (Cell complexes over nD pictures).** A cell complex over an nD picture $I$ is an nD cell complex, denoted by $K(I)$, such that there exists a deformation retraction from $K(I)$ onto $Q(I)$.

# 4. The cubical complex canonically associated to an nD picture I

In Section 4.1, we explain how to compute an nD digital image $J = (\mathbb{Z}^n, F_J)$ encoding the nD cubical complex $Q(I)$. We use this codification to prove that if $I$ is DWC then $Q(I)$ is wWC. Later, in Section 4.2 we give a procedure to obtain the points in $F_J$ encoding the critical cells of $Q(I)$ responsible of $Q(I)$ not being wWC. Finally, in Section 4.3, we compute a simplicial complex $Q_S(I)$ which is, in fact, homeomorphic to $Q(I)$, and prove that $Q_S(I)$ is also weakly-composed if $I$ is DWC.

## 4.1. The nD binary image $J = (\mathbb{Z}^n, F_J)$ encoding $Q(I)$

We say that $J = (\mathbb{Z}^n, F_J)$ encodes $Q(I)$ if $F_J$ is the set of barycenters of the cells in $Q(I)^4$. We say that $p \in F_J$ encodes $\sigma \in Q(I)$ if $p$ is the barycenter of $\sigma$. In that case, we denote $\sigma$ as $\sigma_{Q(I)}(p)$.

**Notation 11.** Let $N, M \in \mathbb{Z}$ such that $0 \le N < M$. Let $p = (x_1, \dots, x_n) \in \mathbb{Z}^n$. Then $N_M(p)$ denotes the set of indices $\{i \in [1, n] : x_i \equiv N \mod M\}$.

Now notice that $2\mathbb{Z}^n$ can be decomposed into the disjoint sets $\mathcal{E}_\ell := \{p \in 2\mathbb{Z}^n : \text{Card}(0_4(p))^5 \text{ is } \ell\}$. For example $\mathcal{E}_n = 4\mathbb{Z}^n$ and $\mathcal{E}_0 = 2\mathbb{Z}^n \setminus 4\mathbb{Z}^n$.

<footnote n="4">⁴Observe that $F_J \subset 2\mathbb{Z}^n$.</footnote>

<footnote n="5">⁵$\text{Card}(S)$ is the cardinality of the set $S$.</footnote>
**Proposition 12.** The set of points of $F_J$ encoding the faces of $\sigma_{Q(I)}(p)$ is:

$$ \mathcal{D}_{F_J}(p) := \mathcal{D}_{F_J}^{+}(p) \setminus \{p\} \quad \text{where} \quad \mathcal{D}_{F_J}^{+}(p) = \left\{ p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j : \lambda_j \in \{0, \pm 2\} \right\}. $$

The subset of points encoding the i-faces of $\sigma_{Q(I)}(p)$ will be denoted by $\mathcal{D}_{F_J}^i(p)$.

For example, if $p \in F_J \cap \mathcal{E}_0$ then $\mathcal{D}_{F_J}(p) = \emptyset$. If $p \in F_J \cap \mathcal{E}_n$ then $\mathcal{D}_{F_J}(p) = \{p' \in F_J \text{ such that } \|p - p'\|_{\infty} = 2\}^6$.

**Proof.** The following procedure computes the set of points encoding the faces of $\sigma = \sigma_{Q(I)}(p)$, for a point $p \in F_J$ with $\mathcal{O}_4(p) = \{i_1, \dots, i_\ell\}$.

Initialization ($\ell = 0$): Then $p \in \mathcal{E}_0$ and $\mathcal{D}_{F_J}^+(p) = \{p\}$ encodes $\sigma$ plus its faces.

Heredity ($\ell \in [1, n]$): We assume that for any point $q \in \mathcal{E}_m \cap F_J$, with $m \in [0, \ell - 1]$, $\mathcal{D}_{F_J}^+(q)$ encodes $\sigma$ plus its faces. Then the set of faces of $\sigma$ is the set of cells $\{\sigma_m\}_m$ covered$^7$ by $\sigma$ and encoded by $\{q_m\}_m := \{p + \lambda^* e^{ik} : k \in [1, \ell]\}$ and $\lambda^* \in \{\pm 2\}$. Thanks to the induction hypothesis:

$$ \mathcal{D}_{F_J}^{+}(q_m) = \left\{ p + \lambda^* e^{ik} + \sum_{r \in [1, \ell] \setminus \{k\}} \lambda_r e^{ir} : \lambda_r \in \{0, \pm 2\} \right\}. $$

Therefore, the cell $\sigma$ and its faces are encoded by the points in the set:

$$ \{p\} \cup \bigcup_m \mathcal{D}_{F_J}^{+}(q_m) = \left\{ p + \sum_{j \in [1, \ell]} \lambda_j e^{ij} : \lambda_j \in \{0, \pm 2\} \right\} = \mathcal{D}_{F_J}^{+}(p). $$

By induction on $\ell$, for any $p \in F_J$, $\mathcal{D}_{F_J}^+(p)$ encodes $\sigma_{Q(I)}(p)$ plus its faces. $\square$

**Proposition 13.** If $p$ encodes an $\ell$-cell $\sigma \in Q(I)$, then the set of points encoding the cells in $Q(I)$ incident to $\sigma$ is:

$$ \mathcal{A}_{F_J}(p) := \mathcal{A}_{F_J}^{+}(p) \setminus \{p\} \quad \text{where} \quad \mathcal{A}_{F_J}^{+}(p) = \left\{ p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j : \lambda_j \in \{0, \pm 2\} \right\} \cap F_J. $$

Besides, the set of points encoding the n-cells incident to $\sigma$ in $Q(I)$ is $\mathcal{A}_{F_J}^n(p) := F_J \cap \{p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j : \lambda_j \in \{\pm 2\}\}$. In general, the $\ell$-cells incident to $\sigma$ in $Q(I)$ are encoded by the points in the set $\mathcal{A}_{F_J}^\ell(p) := \mathcal{A}_{F_J}(p) \cap \mathcal{E}_\ell$.

**Proof.** Let $p \in \mathcal{E}_\ell \cap F_J$. Each point $q = p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j$, where $\lambda_j \in \{0, \pm 2\}$, lies in $\mathcal{E}_{k+\ell}$, being $k$ the number of non-null coefficients $\lambda_j$. If $q \in F_J$, then $q$ encodes a $(k + \ell)$-cell incident to $p$ in $F_J$ since $p \in \mathcal{D}_{F_J}(q)$. $\square$

<footnote>$^6$The $L^\infty$-norm of a vector $\gamma = (x_1, \dots, x_n)$ is $\|\gamma\|_\infty = \max_{i \in [1, n]} |x_i|$.</footnote>

<footnote>$^7$A cell $\sigma^1$ is covered by a cell $\sigma^2$ if $\sigma^2$ is a maximal face of $\sigma^1$.</footnote>
**Lemma 14.** For any $p, p'$ in $2\mathbb{Z}^n$, we have the following equivalences:

$$ 
\begin{aligned}
p' \in \mathcal{A}_{F_J}^{+}(p) &\Leftrightarrow p' = p + \sum_{j \in 2_4(p)} \lambda_j e^j, \quad \lambda_j \in \{0, \pm 2\} \\
&\Leftrightarrow p = p' + \sum_{j \in 0_4(p')} \lambda'_j e^j, \quad \lambda'_j \in \{0, \pm 2\} \Leftrightarrow p \in \mathcal{D}_{F_J}^{+}(p').
\end{aligned}
$$

**Proof.** Only the central equivalence needs to be proved. Assume that $p' = p + \sum_{j \in 2_4(p)} \lambda_j e^j$, $\lambda'_j \in \{0, \pm 2\}$. Then $0_4(p') = 0_4(p) \cup \{j \in 2_4(p) : \lambda_j \neq 0\}$. Define the coefficients $\lambda'_j$, $j \in 0_4(p')$, such that $\lambda'_j := 0$ when $j \in 0_4(p)$ and $\lambda'_j := -\lambda_j$ when $j \in 2_4(p)$ and $\lambda_j \neq 0$. Then $p = p' + \sum_{j \in 0_4(p')} \lambda'_j e^j$. The reasoning is dual for the converse implication. $\square$

**Remark 15.** Let $p, p', p'', p''' \in F_J$ such that $p' \in \mathcal{D}_{F_J}(p)$. Then, (1) if $p'' \in \mathcal{D}_{F_J}(p')$, then $p'' \in \mathcal{D}_{F_J}(p)$; (2) if $p', p'' \in \mathcal{D}_{F_J}(p) \cap \mathcal{A}_{F_J}(p''')$, with

$$ p' = p + \sum_{j \in 0_4(p)} \lambda'_j e^j \quad \text{and} \quad p'' = p + \sum_{j \in 0_4(p)} \lambda''_j e^j, \quad \text{where } \lambda'_j, \lambda''_j \in \{0, \pm 2\} $$

and if $\lambda'_j \neq 0 \neq \lambda''_j$, for some index $j \in 0_4(p)$, then $\lambda'_j = \lambda''_j$.

**Proposition 16.** If two points $p$ and $p'$ encoding two $n$-cells $\sigma$ and $\sigma'$ of $Q(I)$ are $2n$-neighbors, then $\sigma$ and $\sigma'$ share exactly one $(n-1)$-cell.

**Proof.** Since $p, p' \in \mathcal{E}_n$ are $2n$-neighbors then $p' = p + \lambda e^i$ for some $i \in [1, n]$ and $\lambda \in \{\pm 4\}$. Then $q = \frac{1}{2}(p + p') \in \mathcal{E}_{n-1}$ encodes the common $(n-1)$-face. $\square$ Now we are ready to prove the main result of this subsection.

**Proposition 17.** If an $nD$ picture $I = (\mathbb{Z}^n, F_I)$ is $DWC$ then, the associated $nD$ cubical complex $Q(I)$ is $wWC$.

**Proof.** We assume that $F_I$ is $DWC$. Let $p \in F_J$ be a point of $2\mathbb{Z}^n$ encoding a cell $\sigma$ of $Q(I)$. Then the set of points of $4\mathbb{Z}^n$ encoding the $n$-cells in $Q(I)$ incident to $\sigma$ is $\mathcal{A}_{F_J}^n(p)$. Since $F_I$ is $DWC$, it means, by Proposition 5, that for any two points $q$ and $q'$ belonging to $\mathcal{A}_{F_J}^n(p)$, there exists a $2n$-path $(q = p^1, p^2, \dots, p^{k-1}, p^k = q')$ of points in $\mathcal{A}_{F_J}^n(p)$ encoding $n$-cells of $Q(I)$ incident to $\sigma$ such that, for each $i \in [1, k-1]$, $p^i \in \mathcal{N}_{2n}(p^{i+1})$. By Proposition 16, $(\sigma_{Q(I)}(p^1), \dots, \sigma_{Q(I)}(p^k))$ is a path of $n$-cells such that, for any $i \in [1, k-1]$, $\sigma_{Q(I)}(p^i)$ and $\sigma_{Q(I)}(p^{i+1})$ share exactly one $(n-1)$-face of $Q(I)$. Since this is true for any pair of $n$-cells incident to $\sigma_{Q(I)}(p)$, for any $p \in F_J$, then $Q(I)$ is $wWC$. $\square$

## 4.2. Critical cells in $Q(I)$

In this subsection, we define the notion of critical cells of $Q(I)$ that are derived from the notion of critical configurations given in Section 2 and give a procedure to compute the points in $F_J$ that encode them.
<figure><img src="image_5.png" /><figcaption>Figure 3: Left: a critical vertex (in red) resulting from a 2D CC in a 2D space. Middle: a “full” critical edge resulting from a 2D CC in a 3D space and its corresponding critical vertices (in red). Right: a critical vertex (in red) resulting from a 3D CC in a 3D space.</figcaption></figure>

**Definition 18 (Critical cells).** Let $I = (\mathbb{Z}^n, F_I)$ be an nD picture and $Q(I)$ its associated cubical complex. At each block $B \in \mathcal{B}(4\mathbb{Z}^n)$ such that $F_I \cap B$ is a primary or a secondary critical configuration, let $p$ and $p'$ be two antagonists in $B$. Then, the cell centered at $\frac{p+p'}{2}$ is defined as a full-critical cell of $Q(I)$, its vertices as critical vertices, and each cell containing at least one critical vertex will be called critical.

We say that a point $p$ in $F_J$ is *critical* if $p$ encodes a critical cell of $Q(I)$ (see Figure 3). Procedure 1 computes the set $R$ of critical points in $F_J$: starting from the nD picture $I$, for each block $B \in \mathcal{B}(4\mathbb{Z}^n)$ in the domain of the image, it checks if there exists a couple of antagonists $\{p, p'\} \in B$ such that either $F_I \cap B = \{p, p'\}$ (primary configuration) or $B \setminus F_I = \{p, p'\}$ (secondary configuration). Then the intersection of the continuous analogs of the cells encoded by $p$ and $p'$ is a “pinch” (in the sense that the boundary of the continuous analog will not be homeomorphic to $\mathbb{R}^{n-1}$). This pinch, encoded by $p^* = \frac{p+p'}{2}$, is then a full-critical cell of $Q(I)$. Consequently, all the vertices of $Q(I)$ contained in $\mathcal{D}_{F_J}^0(p^*)$ are critical, and all the cells of $Q(I)$ containing a critical vertex are critical cells. We obtain then that $V$ encodes the critical vertices of $Q(I)$ and $R$ encodes the critical cells of $Q(I)$. Note that a discussion about the complexity of a similar algorithm, able to verify that an image is DNC, is discussed in [1]; summarily, the complexity of this algorithm is linear with respect to the number of blocks contained in the smallest hyperrectangle containing $F_I$, and is particularly fast in small dimensions.

**Procedure 1:** Obtaining the critical points in $F_J$.

**Input:** The picture $I = (\mathbb{Z}^n, F_I)$ and the binary image $J = (\mathbb{Z}^n, F_J)$.

**Output:** The set $R$ of critical points in $F_J$.

$V := \emptyset; R := \emptyset;$

for $B \in \mathcal{B}(4\mathbb{Z}^n)$ of dimension $k \in [2, n]$ and $p \in B$ do

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

$p' := \text{antag}_B(p);$

if $(F_I \cap B = \{p, p'\} \text{ or } B \setminus F_I = \{p, p'\}) \text{ then}$

$$ p^* := \frac{p+p'}{2} ; V := V \cup \mathcal{D}_{F_J}^0(p^*) $$

end

end

for $q \in F_J$ such that $\mathcal{D}_{F_J}^0(q) \cap V \neq \emptyset$ do

$$ R := R \cup \{q\} $$

end
<figure><img src="image_7.png" /><figcaption>Figure 4: Three examples of cone joins.</figcaption></figure>

**Remark 19.** If a point $p \in \mathcal{E}_\ell \cap R$, with $\ell \in [0, n]$, then any point $p' \in \mathcal{A}_{F_J}(p)$ is in $R$. Conversely, if a point $p \in \mathcal{E}_\ell \setminus R$, then no point $p' \in \mathcal{D}_{F_J}(p)$ lies in $R$.

### 4.3. Computing the simplicial complex $Q_S(I)$ over $I$

In this subsection we explain how the simplicial complex $Q_S(I)$ (which is, in fact, a subdivision of $Q(I)$) is constructed.

**Definition 20.** [31] The cone (join) on a simplicial complex $K$ with vertex $v$, denoted by $v * K$ is the simplicial complex whose simplices have the form $\langle v_0, \dots, v_\ell, v \rangle$ (where $\langle v_0, \dots, v_\ell \rangle$ is a simplex of $K$ spanned by the set of points $\{v_0, \dots, v_\ell\}$), along with all faces of such simplices.

Some examples of cone joins are depicted in Figure 4.

The simplicial complex $Q_S(I)$ is constructed using Procedure 2 recursively with the cone join operation.

**Procedure 2:** Obtaining the simplicial complex $Q_S(I)$.

**Input:** The point set $F_J$.

**Output:** The simplicial complex $Q_S(I)$.

$$Q_S(I) := \{\langle p \rangle : p \in \mathcal{E}_0 \cap F_J\};$$

**for** $\ell \in [1, n]$ **do**

$$ \left| \begin{array}{l} \quad \text{for } p \in \mathcal{E}_\ell \cap F_J \text{ do} \\ \quad \quad \text{compute the subcomplex } K_{\mathcal{D}_{F_J}}(p) \text{ of } Q_S(I) \text{ formed by the} \\ \quad \quad \text{simplices of } Q_S(I) \text{ such that all their vertices lie in } \mathcal{D}_{F_J}(p); \\ \quad \quad \text{} Q_S(I) := Q_S(I) \cup (p * K_{\mathcal{D}_{F_J}}(p)) \\ \quad \text{end} \end{array} \right. $$

**end**

Observe that $|Q_S^{(0)}(I)| = F_J$ and $|Q_S(I)| = |Q(I)|$. By construction, any $\ell$-simplex $\sigma \in Q_S(I)$, with $\ell \in [0, n]$, can be defined by an (ordered) list of its vertices $\langle v_0, \dots, v_\ell \rangle$ satisfying that $v_i \in \mathcal{D}_{F_J}^i(v_j)$ for $0 \le i < j \le \ell$. Besides, if $\sigma$ is an $n$-simplex of $Q_S(I)$ then there always exists a set of points $\{v_i \in \mathcal{E}_i \cap F_J : i \in [0, n]\}$ such that $\sigma = \langle v_0, \dots, v_n \rangle$.

**Remark 21.** Next tips help to construct simplices incident to a given simplex:
<figure><img src="image_8.png" /><figcaption>Figure 5: Let $Q_S(I)$ be the simplicial subdivision of a 4-size 2-dimensional cube. Starting from two simplices $\sigma = \langle v_0, v_1, v_2 \rangle$ (in dark blue) and $\sigma' = \langle v'_0, v'_1, v_2 \rangle$ (in light blue) in $Q_S(I)$ sharing a vertex $v_2 \in \mathcal{E}_2$, we look for a face-connected path joining $\sigma$ and $\sigma'$ in $\mathcal{A}_{Q_S(I)}^{(2)}(\langle v_2 \rangle)$. Using Procedure 3, we define an intermediary simplex $\alpha = \langle v_0'', v_1'', v_2 \rangle$ (in green) since we are in the case $r=r'$. Then we reiterate the procedure on $(\sigma, \alpha)$ and on $(\alpha, \sigma')$ defining $\mu$ (in yellow) and $\mu'$ (in orange) to get the path $\pi = (\sigma, \mu, \alpha, \mu', \sigma')$ joining $\sigma$ and $\sigma'$ in $\mathcal{A}_{Q_S(I)}^{(2)}(\langle v_2 \rangle)$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 6: A path in $\mathcal{A}_{Q_S(I)}^{(2)}(\langle v_2 \rangle)$ (light gray) induces a path in $\mathcal{A}_{Q_S(I)}^{(1)}(\langle v_1 \rangle)$ (dark gray).</figcaption></figure>

* Let $v \in \mathcal{E}_\ell$ with $\ell \in [0, n-1]$. If $w = v \pm 2e^i$, with $i \in 2_4(v)$, then $w \in \mathcal{E}_{\ell+1}$. Furthermore, when $w$ belongs to $F_J$, then $v \in \mathcal{D}_{F_J}^\ell(w)$. Additionally, when $\ell \in [1, n]$, if $z = v \pm 2e^j$, with $j \in 0_4(v)$, then $z \in \mathcal{D}_{F_J}^{\ell-1}(v)$.

* Let $v_\ell \in \mathcal{E}_\ell \cap F_J$ with $\ell \in [1, n]$. Then, there exist subindices $1 \le i_1 < \dots < i_\ell \le n$, such that $\{i_1, \dots, i_\ell\} = 0_4(v_\ell)$. For $j$ decreasing from $\ell-1$ to $0$, define $v_j := v_{j+1} + \lambda_{j+1} e^{i_{j+1}}$, where $\lambda_j \in \{\pm 2\}$. Then, $\sigma_{Q_S(I)}(v_\ell) = \langle v_0, \dots, v_\ell \rangle$ is an $\ell$-simplex in $\mathcal{A}_{Q_S(I)}(\langle v_\ell \rangle)$.

* Let $\ell \in [1, n]$, $k \in [0, n-\ell]$, $v_{k+\ell} \in \mathcal{E}_{k+\ell} \cap F_J$ and $v_k \in \mathcal{D}_{F_J}^k(v_{k+\ell})$. Then, there exist subindices $1 \le i_{k+1} < \dots < i_{k+\ell} \le n$ with $i_j \in 2_4(v_k)$ and $\lambda_j^* \in \{\pm 2\}$, for $j \in [k+1, k+\ell]$, such that $v_{k+\ell} = v_k + \sum_{j \in [k+1, k+\ell]} \lambda_j^* e^{i_j}$. For $j$ increasing from $k+1$ to $k+\ell-1$, define $v_j := v_{j-1} + \lambda_j^* e^{i_j}$. Then, $\sigma_{Q_S(I)}(v_k, v_{k+\ell}) = \langle v_k, \dots, v_{k+\ell} \rangle$ is an $\ell$-simplex in $\mathcal{A}_{Q_S(I)}(\langle v_k, v_{k+\ell} \rangle)$.

**Example 22.** Let us consider $I = (\mathbb{Z}^4, F_I)$ such that $F_I = \{(0,0,0,0)\}$. Then $Q(I)$ consists in a 4-size 4-dimensional cube centered at $(0,0,0,0)$ and $Q_S(I)$ is a subdivision of the cube in 4-simplices, all of them incident to vertex $v = (0,0,0,0)$. Let $k=0$, $\ell=3$, $v_0 = (2,-2,2,-2) \in \mathcal{E}_0 \cap F_J$ and $v_3 = (2,0,0,0) \in \mathcal{E}_3 \cap F_J$. Then, $v_3 = v_0 + 2e^2 - 2e^3 + 2e^4$. Define $v_1 := v_0 + 2e^2$ and $v_2 := v_0 + 2e^2 - 2e^3$. Then, $\sigma_{Q_S(I)}(v_0, v_3) = \langle v_0, v_1, v_2, v_3 \rangle \in Q_S(I)$.
An example of Procedure 3 computing a face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$, joining two different $\ell$-simplices $\sigma$ and $\sigma'$ is depicted in Figure 5.

**Procedure 3:** Obtaining a face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$, for a given vertex $v_\ell \in \mathcal{E}_\ell \cap F_J$, $\ell \in [1, n]$, joining two different $\ell$-simplices $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$ and $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell \rangle$ in $Q_S(I)$, where $v_i, v'_i \in \mathcal{E}_i \cap F_J$ for $i \in [0, \ell-1]$.

**Input:** $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$ and $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell \rangle$ in $Q_S(I)$ with $v_\ell \in \mathcal{E}_\ell \cap F_J$ and $\sigma \neq \sigma'$.

**Output:** A face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$.

Let $j \in [0, \ell-1]$ such that $v_j \neq v'_j$ and for each $s \in [j+1, \ell]$, $v_s = v'_s$;

if $j=0$ then

$\sigma$ and $\sigma'$ share exactly the $(\ell-1)$-face $\langle v_1, \dots, v_\ell \rangle$

else
$v_j = v_{j+1} + \lambda e^r$ and $v'_j = v_{j+1} + \lambda' e^{r'}$ for some $r, r' \in 0_4(v_{j+1})$ and
$\lambda, \lambda' \in \{\pm 2\}$;

if $r \neq r'$ then

$v''_{j-1} := v_{j+1} + \lambda e^r + \lambda' e^{r'} \in \mathcal{D}_{F_J}^{j-1}(v_j) \cap \mathcal{D}_{F_J}^{j-1}(v'_j);$

Let $\sigma_{Q_S(I)}(v''_{j-1}) = \langle v''_0, \dots, v''_{j-1} \rangle$ obtained using Remark 21;

$\alpha := \langle v''_0, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_\ell \rangle$ and $\alpha' := \langle v''_0, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_\ell \rangle$ share the $(\ell-1)$-face $\langle v''_0, \dots, v''_{j-1}, v_{j+1}, \dots, v_\ell \rangle$;

if $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$) do not share an $(\ell-1)$-face then
repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$)

end

else

$r = r'$ and $\lambda \neq \lambda'$. Take $\lambda^* \in \{\pm 2\}$ and $r'' \in 0_4(v_{j+1})$, $r'' \neq r, r'$;

$v''_j := v_{j+1} + \lambda^* e^{r''} \in \mathcal{D}_{F_J}^j(v_{j+1});$

$\sigma_{Q_S(I)}(v''_j) = \langle v''_0, \dots, v''_j \rangle$ obtained using Remark 21;

$\alpha := \langle v''_0, \dots, v''_j, v_{j+1}, \dots, v_\ell \rangle$;

if $\sigma$ and $\alpha$ (resp. $\alpha$ and $\sigma'$) do not share an $(\ell-1)$-face then
repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha$ and $\sigma'$)

end

end

end

**Proof of Proc 3.** Let $v_\ell \in \mathcal{E}_\ell \cap F_J$, with $\ell \in [1, n]$. Let $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$, $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell \rangle \in \mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ with $\sigma \neq \sigma'$.

Let us prove property ($\mathcal{P}_\ell$): “there exists a face-connected path $\pi(\sigma, \sigma')$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$ and whose vertices are all in $\mathcal{D}_{F_J}^+(v_\ell)$”.

Initialization ($\ell=1$): two different 1-simplices $\sigma = \langle v_0, v_1 \rangle$ and $\sigma' = \langle v'_0, v_1 \rangle$ are joined by the face-connected path $(\sigma, \sigma')$ in $\mathcal{A}_{Q_S(I)}^{(1)}(\langle v_1 \rangle)$.

Heredity ($\ell \in [1, n]$): assume that ($\mathcal{P}_m$) is true for $m \in [0, \ell-1]$. Let $j \in [0, \ell-1]$ such that $v_j \neq v'_j$ and for any $i \in [j+1, \ell-1]$, $v_i = v'_i$. Now, let
$\lambda, \lambda' \in \{\pm 2\}$ and $r, r' \in O_4(v_{j+1})$ such that $v_j = v_{j+1} + \lambda e^r$ and $v'_j = v_{j+1} + \lambda' e^{r'}$.
Then, two cases are possible:

(1) When $r \neq r'$, we define $v''_{j-1} := v_{j+1} + \lambda e^r + \lambda' e^{r'}$ and deduce $v''_0, \dots, v''_{j-2}$ such that $\sigma_{Q_S(I)}(v''_{j-1}) = \langle v''_0, \dots, v''_{j-1} \rangle$. We define then $\alpha := \langle v''_0, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_\ell \rangle$ and $\alpha' := \langle v''_0, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_\ell \rangle$. Since $\alpha$ and $\alpha'$ share the face $\langle v''_0, \dots, v''_{j-1}, v_{j+1}, \dots, v_\ell \rangle$, then $\pi(\alpha, \alpha') := (\alpha, \alpha')$. By $(\mathcal{P}_j)$ ($j < \ell$) there exists a face-connected path $\pi(\mu, \mu')$ in $\mathcal{A}_{Q_S(I)}^{(j)}(\langle v_j \rangle)$ joining $\mu := \langle v_0, \dots, v_{j-1}, v_j \rangle$ and $\mu' := \langle v''_0, \dots, v''_{j-1}, v_j \rangle$. We can rewrite each $i$th element of $\pi(\mu, \mu')$ such that: $\pi(\mu, \mu')(i) = \langle \xi_0^i, \dots, \xi_{j-1}^i, v_j \rangle$, where for each $i$, $\xi_k^i \in \mathcal{E}_k$ where $k$ belongs to $[0, j-1]$. From this path, we can deduce (see Figure 6) a face-connected path $\pi(\sigma, \alpha)$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\alpha$ based on $\pi(\mu, \mu')$: $\forall i, \pi(\sigma, \alpha)(i) := \langle \xi_0^i, \dots, \xi_{j-1}^i, v_j, v_{j+1}, \dots, v_\ell \rangle$. The reasoning is similar for $\alpha'$ and $\sigma'$, so we can obtain $\pi(\alpha', \sigma')$. Using the concatenation operator $\wedge$, we obtain that a face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$ is $\pi(\sigma, \alpha) \wedge \pi(\alpha, \alpha') \wedge \pi(\alpha', \sigma')$.

(2) When $r = r'$, between $\sigma$ and $\alpha$ (respectively, $\alpha$ and $\sigma'$), we can apply (1), from which we deduce $\pi(\sigma, \alpha)$ and $\pi(\alpha, \sigma')$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$, and then a path joining $\sigma$ and $\sigma'$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ is $\pi(\sigma, \alpha) \wedge \pi(\alpha, \sigma')$.

By induction on $\ell$, we deduce that $(\mathcal{P}_\ell)$ is true for any $\ell \in [1, n]$. $\square$

**Example 23.** Let $I = (\mathbb{Z}^4, F_I)$ and $F_I = \{(0,0,0,0)\}$. Let $v_3 = (2,0,0,0)$, $v_0 = (2,2,2,2)$, $v_1 = (2,2,2,0)$, $v_2 = (2,2,0,0)$, $v'_0 = (2,-2,-2,2)$, $v'_1 = (2,-2,0,2)$ and $v'_2 = (2,-2,0,0)$. Let us apply Procedure 3 to obtain a face-connected path in $\mathcal{A}_{Q_S(I)}^{(3)}(\langle v_3 \rangle)$ joining $\sigma = \langle v_0, v_1, v_2, v_3 \rangle$, and $\sigma' = \langle v'_0, v'_1, v'_2, v_3 \rangle$.

* Take $\sigma$ and $\sigma'$, then $j = 2$, $v_2 = v_3 + 2e^2$ and $v'_2 = v_3 - 2e^2$. We are in case (2): $r = 2 = r'$. Let $v'_2 := v_3 - 2e^3 = (2,0,-2,0)$, $v_1^i := (2,2,-2,0)$ and $v_0^i := (2,2,-2,2)$. Let $\alpha_1 := \langle v_0^i, v_1^i, v_2^i, v_3^i \rangle$.

* Take $\sigma$ and $\alpha_1$, then $j = 2$, $v_2 = v_3 + 2e^2$ and $v_2^i = v_3 - 2e^3$. Let $v_1^{ii} := v_3 + 2e^2 - 2e^3 = (2,2,-2,0) = v_1^i$, $v_0^{ii} := v_0^i$, $\alpha_2 := \langle v_0^i, v_1^i, v_2, v_3 \rangle$ and $\alpha'_2 := \langle v_0^i, v_1^i, v_2^i, v_3 \rangle = \alpha_1$, then $\alpha_2$ and $\alpha_1$ share a 2-face.

* Take $\sigma$ and $\alpha_2$, then $j = 1$, $v_1 = v_2 + 2e^3$ and $v_1^i = v_2 - 2e^3$. Let $v_1^{iii} := v_2 + 2e^4 = (2,2,0,2)$, $v_0^{iii} := (2,2,2,2) = v_0$ and $\alpha_3 := \langle v_0, v_1^{iii}, v_2, v_3 \rangle$, then $\sigma$ and $\alpha_3$ share a 2-face.

* Take $\alpha_3$ and $\alpha_2$, then $j = 1$, $v_1^{iii} = v_2 + 2e^4$ and $v_0^i = v_2 - 2e^3$. Let $v_1^{iv} = v_2 + 2e^4 - 2e^3 = (2,2,-2,2) = v_0^{ii}$, $\alpha_4 := (v_0^{ii}, v_1^{iii}, v_2, v_3)$ and $\alpha'_4 := (v_0^{ii}, v_1^{ii}, v_2, v_3) = \alpha_2$, then $\alpha_3$ and $\alpha_4$ (resp. $\alpha_4$ and $\alpha_2$) share a 2-face.

* Take $\alpha_1$ and $\sigma'$, then $j = 2$, $v_2^i = v_3 - 2e^3$ and $v'_2 = v_3 - 2e^2$. Let $v_1^v := v_3 - 2e^3 - 2e^2 = (2,-2,-2,0)$, $v_0^v := (2,-2,-2,2) = v'_0$, $\alpha_5 := \langle v'_0, v_1^v, v_2^v, v_3^v \rangle$ and $\alpha'_5 := \langle v'_0, v_1^v, v_2^v, v_3^v \rangle$, then $\alpha_5$ and $\alpha'_5$ (resp. $\alpha'_5$ and $\sigma'$) share a 2-face.

* Take $\alpha_1$ and $\alpha_5$, then $j = 1$, $v_1^i = v_2^i + 2e^2$ and $v_1^v = v_2^i - 2e^2$. Let $v_1^{vi} := v_2^i + 2e^4 = (2,0,-2,2)$, $v_0^{vi} := (2,2,-2,2) = v_0^i$ and $\alpha_6 := \langle v_0^i, v_1^{vi}, v_2^i, v_3^i \rangle$, then $\alpha_1$ and $\alpha_6$ share a 2-face.
• Take $\alpha_6$ and $\alpha_5$, then $j = 1$, $v_1^{vi} = v_2^{vi} + 2e^4$ and $v_1^v = v_2^v - 2e^2$. Let $v_0^{vii} := v_2^i + 2e^4 - 2e^2 = (2, -2, -2, 2) = v'_0$, $\alpha_7 := \langle v'_0, v_1^{vi}, v_2^i, v_3 \rangle$ and $\alpha'_7 := \langle v'_0, v_1^v, v_2^i, v_3 \rangle = \alpha_5$, then $\alpha_6$ and $\alpha_7$ (resp. $\alpha_7$ and $\alpha_5$) share a 2-face. Finally, the resulting face-connected path is $(\sigma, \alpha_3, \alpha_4, \alpha_2, \alpha_1, \alpha_6, \alpha_7, \alpha_5, \alpha'_5, \sigma')$.

**Procedure 4:** Obtaining a face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$, with $\ell \in [2, n]$, $k \in [0, n-\ell]$, $v_{k+\ell} \in \mathcal{E}_{k+\ell} \cap F_J$ and $v_k \in \mathcal{D}_{F_J}^k(v_{k+\ell})$, joining two different simplices $\sigma$ and $\sigma'$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$.

**Input:** $\sigma = \langle v_k, v_{k+1}, \dots, v_{k+\ell-1}, v_{k+\ell} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, \dots, v'_{k+\ell-1}, v_{k+\ell} \rangle$ in $Q_S(I)$, with $\sigma \neq \sigma'$.

**Output:** A face-connected path in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$ joining $\sigma$ and $\sigma'$. Let $j \in [k+1, k+\ell-1]$ such that $v_j \neq v'_j$ and $v_s = v'_s$ for each $s \in [j+1, k+\ell-1]$;

if $j = k+1$ then

$\sigma$ and $\sigma'$ share the $(\ell-1)$-face $\langle v_k, v_{k+2}, \dots, v_{k+\ell-1}, v_{k+\ell} \rangle$

$v_j = v_{j+1} + \lambda e^r$ and $v'_j = v_{j+1} + \lambda' e^{r'}$ for some $r, r' \in 0_4(v_{j+1})$ with $r \neq r'$ and $\lambda, \lambda' \in \{\pm 2\}$ (by Remark 15);

$v''_{j-1} := v_{j+1} + \lambda e^r + \lambda' e^{r'}$;

let $\sigma_{Q_S(I)}(v_k, v''_{j-1}) = \langle v_k, v''_{k+1}, \dots, v''_{j-1} \rangle$ obtained using Remark 21; $\alpha := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$ and $\alpha' := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$;

if $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$) do not share an $(\ell-1)$-face then
repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$)

end

end

**Proof of Procedure 4.** Let $\sigma = \langle v_k, \dots, v_{k+\ell-1}, v_{k+\ell} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, \dots, v'_{k+\ell-1}, v_{k+\ell} \rangle$, $\sigma \neq \sigma'$. Let us prove property ($\mathcal{P}'_\ell$) : "there exists a face-connected path $\pi(\sigma, \sigma')$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$ whose vertices are all in $\mathcal{A}_{F_J}^+(v_k) \cap \mathcal{D}_{F_J}^+(v_{k+\ell})$, joining $\sigma$ and $\sigma''$.

Initialization ($\ell = 2$): Observe that $\sigma = \langle v_k, v_{k+1}, v_{k+2} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, v_{k+2} \rangle$ share the 1-face $\langle v_k, v_{k+2} \rangle$. Then $\pi(\sigma, \sigma') = (\sigma, \sigma')$.

Heredity ($\ell \in [3, n]$): we assume that ($\mathcal{P}'_m$) is true for $m \in [2, \ell-1]$. We want to prove that ($\mathcal{P}'_\ell$) is true. We define $\alpha := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$ and $\alpha' := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_{k+\ell} \rangle$. It follows that $\alpha$ and $\alpha'$ share an $(\ell-1)$-face. Since $j \in [k+1, k+\ell-1]$, then $j-k \le \ell-1$. Then (by ($\mathcal{P}'_{j-k}$)), the $(j-k)$-simplices $\mu = \langle v_k, v_{k+1}, \dots, v_{j-1}, v_j \rangle$ and $\mu' = \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j \rangle$ are joined by a face-connected path $\pi(\mu, \mu')$ in $\mathcal{A}_{Q_S(I)}^{(j-k)}(\langle v_k, v_j \rangle)$. By rewriting each $i^{th}$ element of $\pi(\mu, \mu')$: $\pi(\mu, \mu')(i) = \langle v_k, \xi_{k+1}^i, \dots, \xi_{j-1}^i, v_j \rangle$, we deduce the $i^{th}$ element of a new path $\pi(\sigma, \alpha)$: $\pi(\sigma, \alpha)(i) = \langle v_k, \xi_{k+1}^i, \dots, \xi_{j-1}^i, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$, in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$ joining $\sigma$ and $\alpha$. We proceed similarly with $\alpha'$ and $\sigma'$ to
<figure><img src="image_10.png" /><figcaption>Figure 7: From left to right: an nD picture $I = (\mathbb{Z}^n, F_I)$; its corresponding simpli-
cial complex $Q_S(I)$; two 2-simplices $\sigma$ and $\sigma'$ of $Q_S(I)$ incident to a vertex $v_\ell$ and a
$2n$-path $\pi_{2n} := (v_n^0, v_n^1, v_n^2)$ of points in $\mathcal{A}_{F_J}^n(v_\ell)$; the face-connected path of 2-simplices
$(\sigma^{(0,-)}, \sigma^{(0,+)}, \sigma^{(1,-)}, \sigma^{(1,+)}, \sigma^{(2,-)}, \sigma^{(2,+)})$ (in light gray, yellow, orange, red, green, and
light gray) in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell \rangle)$ computed from $\pi_{2n}$ using Remark 24.</figcaption></figure>

obtain $\pi(\alpha', \sigma')$ in $\mathcal{A}_{Q_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$. We obtain the path we were looking for, using the concatenation operator $\wedge$: $\pi(\sigma, \sigma') := \pi(\sigma, \alpha) \wedge \pi(\alpha, \alpha') \wedge \pi(\alpha', \sigma')$. By induction on $\ell \in [2, n]$, $(\mathcal{P}'_\ell)$ is true for any $\ell \in [2, n]$ and $k \in [0, n-\ell]$. $\square$

**Remark 24.** Given vertices $v_\ell \in \mathcal{E}_\ell \cap F_J$ and $v_n, v'_n \in \mathcal{A}_{F_J}^n(v_\ell)$, there exist subindices $1 \le i_1 < \dots < i_\ell \le n$ and $1 \le i_{\ell+1} < \dots < i_n \le n$, such that $\{i_1, \dots, i_\ell\} = 0_4(v_\ell)$ and $\{i_{\ell+1}, \dots, i_n\} = 2_4(v_\ell)$. We have

$$
v_n = v_\ell + \sum_{j \in [\ell+1, n]} \lambda_j e^{ij} \quad \text{and} \quad v'_n = v_\ell + \sum_{j \in [\ell+1, n]} \lambda'_j e^{ij}, \quad \text{where } \lambda_j, \lambda'_j \in \{\pm 2\}.
$$

For $j \in [0, \ell - 1]$, define $v_j := v_{j+1} + \lambda_{j+1} e^{ij+1}$, being $\lambda_j \in \{\pm 2\}$. We have
$v_j \in \mathcal{D}_{F_j}^j(v_{j+1})$, for all $j \in [0, \ell - 1]$.

(P1) If $v_n, v'_n$ are 2n-neighbors, then there exists $r \in [\ell+1, n]$ such that $\lambda_r \neq \lambda'_r$ and $\lambda_j = \lambda'_j$, for all $j \neq r$. Suppose, without loss of generality, that $r=n$. Define $v_{n-1} := \frac{1}{2}(v_n + v'_n)$. For $j \in [\ell+1, n-2]$, define $v_j := v_{j+1} + \lambda_{j+1}e^{ij+1}$. Then $\sigma := \langle v_0, \dots, v_{n-1}, v_n \rangle$ and $\sigma' := \langle v_0, \dots, v_{n-1}, v'_n \rangle$ are n-simplices in $\mathcal{A}_{Q_S(I)}(\langle v_\ell \rangle)$ sharing a common $(n-1)$-face.

(P2) Any two $n$-simplices $\mu$ and $\mu'$ in $Q_S(I)$ incident to $v_n$ are face-connected in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_n \rangle)$ by Procedure 3.

(P3) Any two $n$-simplices $\mu = \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-1}, v_n \rangle$ and $\mu' := \langle v'_0, \dots, v'_{\ell-1}, v_\ell, v'_{\ell+1}, \dots, v'_{n-1}, v_n \rangle$ are face-connected in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell, v_n \rangle)$: Let $\mu'' := \langle v'_0, \dots, v'_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-1}, v_n \rangle$. By Procedure 3 (resp. by Procedure 4), $\mu$ and $\mu''$ (resp. $\mu''$ and $\mu'$) are face-connected in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell, v_n \rangle)$.

Now let us prove the main result in this subsection (depicted in Figure 7).

**Proposition 25.** If *I* is *DWC* then *Q*<sub>S</sub>(*I*) is *wWC*.
**Proof.** Assume that $I$ is DWC. Let $\ell \in [0, n]$ and $v_\ell \in \mathcal{E}_\ell \cap F_J$. Let $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_n \rangle$ and $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell, v'_{\ell+1}, \dots, v'_n \rangle$ be two different $n$-simplices of $Q_S(I)$ incident to $v_\ell$. We want to prove property $(\mathcal{P})$: “there exists a face-connected path in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$”.
When $\ell = n$, then $v'_n = v_n$, and $(\mathcal{P})$ is true by Remark 24.(P2).

Now, when $\ell \in [0, n-1]$, since $I$ is DWC, then there exists a $2n$-path in $\mathcal{A}_{F_J}^n(v_\ell)$ denoted $\pi_{2n} := (v_n^0 := v_n, v_n^1, \dots, v_n^{m-1}, v_n^m := v_n')$ joining $v_n$ and $v_n'$. For each pair $(v_n^i, v_n^{i+1})$, where $i$ belongs to $[0, m-1]$, we obtain, using Remark 24.(P1), the $n$-simplices $\sigma^{(i,+)}$ and $\sigma^{(i+1,-)}$ in $\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell \rangle)$ sharing an $(n-1)$-face. Since, by Remark 24.(P3), there are face-connected paths:

$$ 
\begin{align*}
\pi(\sigma = \sigma^{(0,-)}, \sigma^{(0,+)}) &\text{ in } \mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell, v_n^0 \rangle), \\
\pi(\sigma^{(i,-)}, \sigma^{(i,+)}) &\text{ in } \mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell, v_n^i \rangle), \quad \text{for } i \in [1, m-1], \\
\pi(\sigma^{(m,-)}, \sigma^{(m,+)} = \sigma') &\text{ in } \mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell, v_n^m \rangle),
\end{align*}
$$

(where $\pi(a, b)$ means that there is a face-connected path of $n$-simplices joining $a$ and $b$). Then $\sigma$ and $\sigma'$ are face-connected by a path resulting from the concatenation of the paths described above:

$$ 
\begin{align*}
\pi(\sigma, \sigma') &:= \pi(\sigma^{0,-}, \sigma^{0,+}) \wedge \pi(\sigma^{0,+}, \sigma^{1,-}) \wedge \dots \wedge \pi(\sigma^{m-1,+}, \sigma^{m,-}) \wedge \pi(\sigma^{m,-}, \sigma^{m,+}), \\
\text{in } \mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell \rangle). \quad \text{Since } (\mathcal{P}) \text{ is true for any pair of } n\text{-simplices } \sigma \text{ and } \sigma' \text{ in } & \\
\mathcal{A}_{Q_S(I)}^{(n)}(\langle v_\ell \rangle) \text{ and for any } v_\ell \text{ in } Q_S(I), \text{ then } Q_S(I) \text{ is wWC.} \quad \square
\end{align*}
$$

**5. Combinatorial method to obtain the weak well-composed simpli-**
**cial complex $P_S(I)$ over an nD picture $I$**

The aim of this section is to compute a wWC simplicial complex $P_S(I)$ over $I$. For doing this, we first “enlarge” the nD binary image $J = (\mathbb{Z}^n, F_J)$, encoding $Q(I)$, around the critical points and compute a new nD binary image $L = (\mathbb{Z}^n, F_L)$. Then, we construct the simplicial complex $P_S(I)$ and prove later that $P_S(I)$ is a wWC simplicial complex over $I$. For the sake of clarity, the proofs of the results presented in this section are given in an annex at the end of this document.

**5.1. Computing the nD binary image $L = (\mathbb{Z}^n, F_L)$**

In this subsection we give a procedure to obtain the nD binary image $L = (\mathbb{Z}^n, F_L)$ that will be used later to compute the simplicial complex $P_S(I)$.

**Notation 26.** The set $\mathbb{Z}^n \setminus 2\mathbb{Z}^n$ can be decomposed into the disjoint sets:

$$ \mathcal{O}_\ell := \{p \in \mathbb{Z}^n \setminus 2\mathbb{Z}^n : \text{Card}(\mathcal{O}_p) \text{ is } \ell\}, $$

where $\ell \in [0, n-1]$. Then, $\mathbb{Z}^n = (\cup_{i \in [0, n]} \mathcal{E}_i) \sqcup (\cup_{i \in [0, n-1]} \mathcal{O}_i)$.
<figure><img src="image_11.png" /><figcaption>Figure 8: Computing $F_L$ from $F_J$, where $F_J$ (showed on the left) encodes two 2-cubes sharing a vertex (as in Figure 1). The blue, red and green points on the left figure belong, respectively, to $\mathcal{E}_0$, $\mathcal{E}_1$ and $\mathcal{E}_2$. Black points in the middle are critical. The blue, red and green points on the right belong, respectively, to $((\mathcal{E}_0 \setminus R) \cup \mathcal{O}_0) \cap F_L$, $((\mathcal{E}_1 \setminus R) \cup \mathcal{O}_1) \cap F_L$ and $(\mathcal{E}_2 \cap F_L) \cup R$. Note that each red rectangle, admitting a center called $p$, encloses the set $S(p)$.</figcaption></figure>

**Definition 27 (S-Block).** Let $p \in 2\mathbb{Z}^n$. The S-block $S(p)$ is the set:

$$S(p) := \left\{ p + \sum_{j \in 2\mathcal{I}_4(p)} \lambda_j e^j : \lambda_j \in \{0, \pm 1\} \right\}.$$

Observe that if $p \in \mathcal{E}_\ell$ then $S(p) \setminus \{p\} \subseteq \bigsqcup_{i \in [0, \ell]} \mathcal{O}_i$ and, for any point $q \in S(p)$, it is satisfied that $||p - q||_\infty \le 1$. For example, if $p$ encodes a 0-cell, then $S(p) = \{q \in \mathbb{Z}^n : ||p - q||_\infty \le 1\}$. If $p$ encodes an $n$-cell, then $S(p) = \{p\}$.

The following result establishes that $\mathbb{Z}^n = \bigsqcup_{p \in 2\mathbb{Z}^n} S(p)$.

**Remark 28.** For any point $q \in \mathbb{Z}^n$ the only $p \in 2\mathbb{Z}^n$ such that $q \in S(p)$ is:

$$p = q + \sum_{j \in 1_2(q)} \mu_j e^j, \text{ where } \mu_j = 1 \text{ if } j \in 1_4(q) \text{ or } -1 \text{ if } j \in 3_4(q).$$

Procedure 5 is used to compute the nD binary image $L = (\mathbb{Z}^n, F_L)$, by adding the S-block $S(p)$ to $J = (\mathbb{Z}^n, F_J)$, for each critical point $p$ (see Figure 8).

**Procedure 5:** Computing the nD binary image $L = (\mathbb{Z}^n, F_L)$.

**Input:** The nD binary image $J = (\mathbb{Z}^n, F_J)$ encoding $Q(I)$ and the set $R$ of critical points of $F_J$.

**Output:** An nD binary image $L = (\mathbb{Z}^n, F_L)$.

$F_L := F_J$ // initial points are preserved;

foreach $p \in R$ do

| $F_L := F_L \cup S(p)$ // we enlarge $J$ around the critical points

end

Observe that since $p \subseteq S(p)$, initial points are preserved, and, since $S(p) \cap S(q) = \emptyset$ if $p \ne q$ by Remark 28, then the entire set $S(p)$ is added to $F_L$.

## 5.2. The intermediary sets $\mathcal{D}_{F_L}(p)$ and $\mathcal{A}_{F_L}(p)$ for any $p \in F_L$

In this subsection, we first define a partition of $F_L$ into the sets $C_\ell$ for $\ell \in [0, n]$. Second, for each point $p \in C_\ell$, we define the sets $\mathcal{D}_{F_L}(p)$ (used to compute $P_S(I)$) and $\mathcal{A}_{F_L}(p)$ (used to prove that $P_S(I)$ is wWC).
<figure><img src="image_12.png" /><figcaption>Figure 9: From left to right: The set $F_L$ from Figure 8; computation of $D_{F_L}(p)$ (blue points) for a (red) point $p \in \mathcal{E}_1 \setminus R$; $\mathcal{D}_{F_L}^1(p)$ (in red) for a (green) point $p \in \mathcal{E}_2 \cap R$; $D_{F_L}(p)$ (in blue) for a (red) point $p \in \mathcal{O}_1$.</figcaption></figure>

In [13, 14, 15], in 3D context, $\mathcal{C}_\ell$ would encode the $\ell$-cells of a 3D polyhedral complex over $I$; $\mathcal{D}_{F_L}(p)$ would encode the set of faces of the cell encoded by $p$; and $\mathcal{A}_{F_L}(p)$ would encode the set of cells incident to $p$.

**Remark 29.** The set $F_L$ can be decomposed into the disjoint sets:

$$ \mathcal{C}_n := (\mathcal{E}_n \cap F_L) \cup R \text{ and } \mathcal{C}_\ell := ((\mathcal{E}_\ell \setminus R) \cup \mathcal{O}_\ell) \cap F_L \text{ for } \ell \in [0, n-1]. $$

**Definition 30.** For $p \in F_L$, define the set $\mathcal{D}_{F_L}(p) := \mathcal{D}_{F_L}^+(p) \setminus \{p\}$ where:

* If $p \in \mathcal{C}_0$ then $\mathcal{D}_{F_L}^+(p) = \{p\}$.

* If $p \in \mathcal{E}_\ell \setminus R$, for $\ell \in [1, n]$, then $p \in \mathcal{C}_\ell$ and $\mathcal{D}_{F_L}^+(p) := \mathcal{D}_{F_j}^+(p)$;

* If $p \in \mathcal{E}_\ell \cap R$, for $\ell \in [1, n]$, then $p \in \mathcal{C}_n$ and

$$ \mathcal{D}_{F_L}^+(p) := S(p) \sqcup (\mathcal{D}_{F_j}(p) \setminus R) \sqcup \bigsqcup_{r \in \mathcal{D}_{F_j}(p) \cap R} (S(r) \cap \mathcal{N}(p)). $$

* If $p \in \mathcal{O}_\ell$, for $\ell \in [1, n-1]$, then $p \in \mathcal{C}_\ell$ and $\exists q \in R$ s.t. $p \in S(q)$. We have:

$$ \mathcal{D}_{F_L}^+(p) := (S(q) \cap \mathcal{N}^+(p)) \sqcup (\mathcal{D}_{F_j}(q) \setminus R) \sqcup \bigsqcup_{r \in \mathcal{D}_{F_j}(q) \cap R} (S(r) \cap \mathcal{N}(p)), $$

with $\mathcal{N}^+(p) := \{p + \sum_{j \in \mathcal{O}_2(p)} \lambda_j e^j : \lambda_j \in \{0, \pm 1\}\}$ and $\mathcal{N}(p) := \mathcal{N}^+(p) \setminus \{p\}$. For $p \in \mathcal{C}_\ell$, $\ell \in [1, n]$ and $j \in [0, \ell-1]$, $\mathcal{D}_{F_L}^j(p)$ denotes the set $\mathcal{D}_{F_L}(p) \cap \mathcal{C}_j$.

Notice that if $p \in 2\mathbb{Z}^n$ then $\mathcal{N}(p) = \{q \in \mathbb{Z}^n : \|p - q\|_\infty = 1\}$.

The intermediary steps for computing $\mathcal{D}_{F_L}(p)$ are depicted in Figure 9.

**Proposition 31.** If $p \in \mathcal{C}_\ell$ then $\mathcal{D}_{F_L}(p) \subseteq \bigsqcup_{i \in [0, \ell-1]} \mathcal{C}_i$.

**Example 32.** Let $p \in \mathcal{C}_\ell$ with $\ell \in [1, n]$.
* Suppose $p = (0, \dots, 0, 2, \dots, 2) \in \mathcal{E}_\ell \setminus R$. Then $\mathcal{D}_{F_L}^+(p) = \{(x_1, \dots, x_\ell, 2, \dots, 2) : x_i \in \{0, \pm 2\}\}$.

* Suppose $p = (0, \dots, 0, 2, \dots, 2) \in \mathcal{E}_\ell \cap R$. We have $S(p) = \{(0, \dots, 0, x_{\ell+1}, \dots, x_n) : x_i \in \{2, 2 \pm 1\}\}$ and $\mathcal{D}_{F_j}(p) \setminus R = \{(x_1, \dots, x_\ell, 2, \dots, 2) : x_i \in \{0, \pm 2\}\} \setminus R$.
  Now, if, for example, $r = (0, \dots, 0, 2, \dots, 2) \in \mathcal{D}_{F_j}(p) \cap R$, with $\ell' < \ell$, then $S(r) \cap \mathcal{N}(p) = \{(0, \dots, 0, 1, \dots, 1, x_{\ell+1}, \dots, x_n) : x_i \in \{2, 2 \pm 1\}\}$.

* Suppose $p = (0, \dots, 0, 2, \dots, 2, 1, \dots, 1) \in \mathcal{O}_\ell$, $k \in [0, \ell]$ and $\ell < n$. We have $q = (0, \dots, 0, 2, \dots, 2, \dots, 2) \in \mathcal{E}_k$ is the only point such that $p \in S(q)$. We have $S(q) \cap \mathcal{N}^+(p) = \{(0, \dots, 0, x_{k+1}, \dots, x_\ell, 1, \dots, 1) : x_i \in \{2, 2 \pm 1\}\}$ and $\mathcal{D}_{F_j}(q) \setminus R = \{(x_1, \dots, x_k, 2, \dots, 2) : x_i \in \{0, \pm 2\}\} \setminus R$.
  Now, if, for example, $r = (0, \dots, 0, 2, \dots, 2, \dots, 2) \in \mathcal{D}_{F_j}(q) \cap R$, with $k' < k$, then $S(r) \cap \mathcal{N}(p) = \{(0, \dots, 0, 1, \dots, 1, x_{k+1}, \dots, x_\ell, 1, \dots, 1) : x_i \in \{2, 2 \pm 1\}\}$.

**Remark 33.** Let $p \in F_L$.

* If $p \in \mathcal{E}_\ell \setminus R$ then $p \in C_\ell$. A point $p'$ lies in $\mathcal{D}_{F_L}^{\ell-1}(p)$ (for $\ell \in [1, n]$) iff:

$$p' = p + \lambda e^j, \text{ with } \lambda \in \{\pm 2\} \text{ and } j \in \mathcal{O}_4(p).$$

* If $p \in \mathcal{E}_\ell \cap R$ then $p \in C_n$. A point $p'$ lies in $\mathcal{D}_{F_L}^{n-1}(p)$ iff one of the following cases holds for $p'$ (corresponding to each of the sets in Definition 30):

$$p' = p + \lambda e^j, \text{ with } \lambda \in \{\pm 1\} \text{ and } j \in \mathcal{O}_4(p);$$

$$p' = p + \lambda e^j, \text{ with } \lambda \in \{\pm 2\} \text{ and } j \in \mathcal{O}_4(p) \text{ s.t. } p + \lambda e^j \in \mathcal{E}_{n-1} \setminus R;$$

$$p' = p + \lambda e^j, \text{ with } \lambda \in \{\pm 1\} \text{ and } j \in \mathcal{O}_4(p) \text{ s.t. } p + 2\lambda e^j \in R.$$

* If $p \in \mathcal{O}_\ell$, then $p \in C_\ell$ and $\exists q \in 2\mathbb{Z}^n$ s.t. $p \in S(q)$ (by Remark 28). Therefore, a point $p'$ lies in $\mathcal{D}_{F_L}^{\ell-1}(p)$ (for $\ell \in [1, n-1]$) iff one of the following cases holds (corresponding to each of the sets in Definition 30):

$$p' = p + \lambda e^j, \text{ with } \lambda \in \{\pm 1\} \text{ and } j \in \mathcal{O}_4(p);$$

$$p' = q + \lambda e^j, \text{ with } \lambda_j \in \{\pm 2\} \text{ and } j \in \mathcal{O}_4(p) \text{ s.t. } q + \lambda e^j \in \mathcal{E}_{\ell-1} \setminus R;$$

$$p' = p + \lambda e^j, \text{ with } \lambda_j \in \{\pm 1\}, \text{ and } j \in \mathcal{O}_4(p) \text{ s.t. } q + 2\lambda e^j \in R.$$

**Definition 34.** Define the set $\mathcal{A}_{F_L}(p) := \mathcal{A}_{F_L}^+(p) \setminus \{p\}$ for $p \in C_\ell$, where:

* If $\ell = n$ then $\mathcal{A}_{F_L}^+(p) = \{p\}$.

* If $\ell < n$ and $p \in \mathcal{E}_\ell \setminus R$ then $\mathcal{A}_{F_L}^+(p) := (\mathcal{A}_{F_j}^+(p) \setminus R) \sqcup \sqcup_{q \in \mathcal{A}_{F_j}(p) \cap R} S(q)$.

* If $\ell < n$ and $p \in \mathcal{O}_\ell$ then $\mathcal{A}_{F_L}^+(p) := F_L \cap \{p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j : \lambda_j \in \{0, \pm 1\}\}$.
The set $\mathcal{A}_{F_L}(p) \cap \mathcal{C}_{\ell+1}$, for $p \in \mathcal{C}_{\ell}$ and $\ell \in [0, n-1]$, is denoted by $\mathcal{A}_{F_L}^{\ell+1}(p)$.

**Example 35.** Let $p \in \mathcal{C}_{\ell}$ for $\ell \in [0, n-1]$.

* Suppose $p = (0, \dots, 0, 2, \dots, 2) \in \mathcal{E}_{\ell} \setminus R$. Then $\mathcal{A}_{F_j}^{+}(p) = \{(0, \dots, 0, x_{\ell+1}, \dots, x_n) : x_i \in \{2, 2 \pm 2\}\}$.

Now, if, for example, $q = (0, \dots, 0, 2, \dots, 2) \in \mathcal{A}_{F_j}(p) \cap R$, with $\ell' > \ell$, then $S(q) = \{(0, \dots, 0, x_{\ell+1}, \dots, x_n) : x_i \in \{2, 2 \pm 1\}\}$.

* Suppose $p = (0, \dots, 0, 2, \dots, 2, 1, \dots, 1) \in \mathcal{O}_{\ell}$, we have $\mathcal{A}_{F_L}^{+}(p) = F_L \cap \{(0, \dots, 0, 2, \dots, 2, x_{\ell-k+1}, \dots, x_n) : x_i \in \{1, 1 \pm 1\}\}$.

**Proposition 36.** If $p \in \mathcal{C}_{\ell}$ for $\ell \in [0, n-1]$, then $\mathcal{A}_{F_L}(p) \subseteq \bigsqcup_{i \in [\ell+1, n]} \mathcal{C}_i$ and $p' \in \mathcal{A}_{F_L}(p)$ iff $p \in \mathcal{D}_{F_L}(p')$.

**Remark 37.** Let $p \in \mathcal{C}_{\ell}$ and $p'' \in \mathcal{D}_{F_L}^k(p)$, where $\ell \in [1, n]$ and $k \in [0, \ell-1]$. The expression of a point $p' \in \mathcal{D}_{F_L}^{\ell-1}(p) \cap \mathcal{A}_{F_L}^{\ell-1}(p'')$ can be deduced from Remark 33 and Definition 34:

* If $p'' \in \mathcal{O}_k$, then $p' \in \mathcal{O}_{\ell-1}$ and $p \in \mathcal{O}_{\ell}$ or $p \in \mathcal{E}_{\ell'} \cap R$, for some $\ell'$ (this last case only if $\ell = n$). In any case, since $p' \in \mathcal{D}_{F_L}^{\ell-1}(p)$, then $p' = p + \lambda e^j$, for $\lambda \in \{\pm 1\}$ and $j \in \{0, 2\}$. Now, since $p' \in \mathcal{A}_{F_L}^{\ell-1}(p'')$, $j \in \{1, 2\}$. Therefore, $p' = p + \lambda e^j$ for $\lambda \in \{\pm 1\}$ and $j \in \{0, 2\} \cap \{1, 2\}$.

* Else $p'' \in \mathcal{E}_k \setminus R$. Since $p' \in \mathcal{D}_{F_L}^{\ell-1}(p)$, by Remark 33, $p' = z + \lambda e^j$ for $z \in \{p, q\}$ (being $q$ the point in $2\mathbb{Z}^n$ such that $p \in S(q)$), $\lambda \in \{\pm 1, \pm 2\}$ and $j \in \{0, 2\}$. Moreover, $p' \in \mathcal{A}_{F_L}^{\ell-1}(p'')$, so, necessarily $j \in \{0, 2\} \cap \{2, 4\}(p'')$.

### 5.3. Computing the wWC simplicial complex $P_S(I)$ over $I$

The aim of this section is to compute a simplicial complex $P_S(I)$ whose vertex set is $F_L$ and prove that it is wWC over $I$.

First, $P_S(I)$ is constructed using the cone join operation as follows.

**Procedure 6:** Obtaining the simplicial complex $P_S(I)$.

**Input:** The point set $F_L$.

**Output:** The simplicial complex $P_S(I)$.

$$P_S(I) := \{\langle p \rangle : p \in \mathcal{C}_0\};$$

for $\ell \in [1, n]$ do

for $p \in \mathcal{C}_{\ell}$ do

let $K_{\mathcal{D}_{F_L}}(p)$ be the set of simplices whose vertices lie in $\mathcal{D}_{F_L}(p)$;

$$P_S(I) := P_S(I) \cup (p * K_{\mathcal{D}_{F_L}}(p))$$

end

end

As in the case of $Q_S(I)$, any simplex $\sigma \in P_S(I)$ is given by an (ordered) list its vertices $\langle v_0, \dots, v_{\ell} \rangle$ such that $v_i \in \mathcal{D}_{F_L}(v_j)$ for $0 \le i < j \le n$. In particular, if $\sigma$ is an $n$-simplex, then $\sigma = \langle v_0, \dots, v_n \rangle$ where $v_i \in \mathcal{C}_i$ for all $i \in [0, n]$. An example of computation of $P_S(I)$ from $F_L$ is given in Figure 10.
<figure><img src="image_13.png" /><figcaption>Figure 10: From left to right: the set $F_L$; the corresponding set $C_0$ (in blue); adding $(p * K_{D_{F_L}}(p))$ for each (red) point $p \in C_1$; adding $(p * K_{D_{F_L}}(p))$ for each (green) point $p \in C_2$.</figcaption></figure>

**Remark 38.** [31, p. 12] Let $K_1, K_2$ be simplicial complexes and $f: K_1^{(0)} \to K_2^{(0)}$ a map such that if $\langle v_0, \dots, v_k \rangle$ in $K_1$ then $f(v_0), \dots, f(v_k)$ are vertices of a simplex of $K_2$. Then $f$ can be extended to a continuous map $g: |K_1| \to |K_2|$.

**Proposition 39.** *There exists a deformation retraction of $|P_S(I)|$ onto $|Q_S(I)|$.*

**Proof.** The maps $f_t: |P_S(I)| \to |P_S(I)|$, $t \in [0, 1]$, are defined as follows: For any $v \in F_L$, let $f_t(v) := v + t(p-v)$, where $p \in F_J$ is such that $v \in S(p)$. We have that:

* $f_t(v) = v$ for any $v \in F_J$ and $t \in [0, 1]$ (because if $v \in F_J$ then $v \in S(v)$).

* Let us see that if $\sigma = \langle v_0, \dots, v_k \rangle$ is a simplex of $P_S(I)$ then $f_1(v_0), \dots, f_1(v_k)$ are vertices of a simplex of $Q_S(I)$: Since $\sigma \in P_S(I)$, then $v_i \in C_\ell$ for $\ell \in [0, k]$ and $v_j \in A_{F_L}(v_i)$ for $0 \le i < j \le k$. Now, given $i \in [0, k-1]$:

- If $v_i \in \mathcal{E}_i \setminus R$ then $f_1(v_i) = v_i$.

- If $v_i \in \mathcal{O}_i$ then there exists $p_i \in R$ such that $v_i \in S(p_i)$. Moreover,
    * If $k < n$ then $v_j \in \mathcal{O}_j \cap S(p_j)$ for $j \in [0, k]$ and $p_j \in R \cap A_{F_J}(p_i)$.
    * If $k = n$, then $v_n \in A_{F_J}(p_i)$ and $f_1(v_n) = v_n$.

Then, $f_1: F_L \to F_J$ can be extended to a continuous map $f_1: |P_S(I)| \to |Q_S(I)|$ by Remark 38.

* $f_0(x) = x$ and $f_1(x) \in |Q_S(I)|$, for any $x \in |P_S(I)|$;

* $f_t(y) = y$, for any $y \in |Q_S(I)|$ and for any $t \in [0, 1]$.

Then, $F: |P_S(I)| \times [0, 1] \to |P_S(I)|$, given by $F(x, t) = f_t(x)$, is a deformation retraction of $|P_S(I)|$ onto $|Q_S(I)|$. $\square$

**Proposition 40.** Let $\ell \in [1, n]$ and $k \in [0, n-\ell]$.

* For any $v_\ell \in C_\ell$, there exists an $\ell$-simplex $\sigma_{P_S(I)}(v_\ell) = \langle v_0, \dots, v_\ell \rangle$ such that $v_i \in C_i$ for all $i \in [0, \ell]$.

* For any $v_k \in C_k$ and $v_{k+\ell} \in A_{F_L}^{k+\ell}(v_k)$, there exists an $\ell$-simplex $\sigma_{P_S(I)}(v_k, v_{k+\ell}) = \langle v_k, \dots, v_{k+\ell} \rangle$ such that $v_i \in C_i$ for all $i \in [k, k+\ell]$.
**Procedure 7:** Computing a face-connected path in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ for $v_\ell \in C_\ell$, and $\ell \in [1, n]$, joining two different simplices $\sigma$ and $\sigma'$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$.

**Input:** Two different $\ell$-simplices $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$ and $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell \rangle$ in $P_S(I)$ s.t. $v_i, v'_i \in C_i$, for all $i \in [0, \ell-1]$ and $v_\ell \in C_\ell$.

**Output:** A face-connected path in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$.
Let $j \in [0, \ell-1]$ such that $v_j \neq v'_j$ and for each $s \in [j+1, \ell]$, $v_s = v'_s$;

**if** $j=0$ **then**

$\sigma$ and $\sigma'$ share the $(\ell-1)$-simplex $\langle v_1, \dots, v_\ell \rangle$

**else**

$v_{j+1} \in S(w_r)$ for some $w_r \in \mathcal{E}_r$ and $r \in [0, j+1]$;

$v_j = z + \lambda e^i$ and $v'_j = z' + \lambda' e^{i'}$, where $i, i' \in 0_2(v_{j+1})$,

$\lambda, \lambda' \in \{\pm 1, \pm 2\}$ and $z, z' \in \{v_{j+1}, w_r\}$ (by Remark 33);

**if** $i \neq i'$ **then**

**if** $|\lambda| = |\lambda'|$ **then**

$v''_{j-1} := z + \lambda e^i + \lambda' e^{i'} \in \mathcal{D}_{F_L}^{j-1}(v_j) \cap \mathcal{D}_{F_L}^{j-1}(v'_j)$

**else**

(suppose $|\lambda| = 1$ and $|\lambda'| = 2$) $w''_{j-1} := w_r + 2\lambda e^i + \lambda' e^{i'}$;

**if** $w''_{j-1} \in C_{j-1}$ **then**

$v''_{j-1} := w''_{j-1} \in \mathcal{D}_{F_L}^{j-1}(v_j) \cap \mathcal{D}_{F_L}^{j-1}(v'_j)$

**else**

$v''_j := v_{j+1} + \lambda e^i + \frac{1}{2}\lambda' e^{i'} \in \mathcal{D}_{F_L}^{j-1}(v_j) \cap \mathcal{D}_{F_L}^{j-1}(v'_j)$

**end**

**end**

By Proposition 40, there exists $v''_t \in C_t$, $t \in [0, j-2]$, s.t.

$\alpha := \langle v''_0, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_\ell \rangle$ and $\alpha' := \langle v''_0, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_\ell \rangle$ are $\ell$-simplices in $\mathcal{A}_{P_S(I)}(\langle v_\ell \rangle)$ sharing a common $(\ell-1)$-face;

**if** $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$) do not share an $(\ell-1)$-face **then**

repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$)

**end**

**else**

$\exists i'' \in 0_2(v_{j+1}), i'' \neq i$, s.t. $v''_j := z'' + \lambda'' e^{i''} \in \mathcal{D}_{F_L}^j(v_{j+1})$ for some $z'' \in \{v_{j+1}, w_r\}$ and $\lambda'' \in \{\pm 1, \pm 2\}$ (by Remark 33);

By Proposition 40, there exist $v''_t \in C_t$, $t \in [0, j-1]$, such that $\alpha := \langle v''_0, \dots, v''_j, v_{j+1}, \dots, v_\ell \rangle$ is an $\ell$-simplex in $\mathcal{A}_{P_S(I)}(\langle v_\ell \rangle)$;

**if** $\sigma$ and $\alpha$ (resp. $\alpha$ and $\sigma'$) do not share an $(\ell-1)$-face **then**

repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha$ and $\sigma'$)

**end**

**end**

**end**

Procedure 7 is depicted in Figures 11 and 12.
**Procedure 8:** Computing a face-connected path in $\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$, for $v_{k+\ell} \in \mathcal{C}_{k+\ell}$, $v_k \in \mathcal{D}_{F_L}^k(v_{k+\ell})$, $\ell \in [2, n]$ and $k \in [0, n-\ell]$, joining two different simplices $\sigma$ and $\sigma'$ in $\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$.

**Input:** Two different $\ell$-simplices $\sigma = \langle v_k, v_{k+1}, \dots, v_{k+\ell-1}, v_{k+\ell} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, \dots, v'_{k+\ell-1}, v_{k+\ell} \rangle$ in $\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$.

**Output:** A face-connected path in $\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$ joining $\sigma$ and $\sigma'$. Let $j \in [k+1, k+\ell-1]$ such that $v_j \neq v'_j$ and for each $s \in [j+1, k+\ell-1]$ $v_s = v'_s$;

**if** $j=k+1$ **then**

$\sigma$ and $\sigma'$ share the $(\ell-1)$-simplex $\langle v_k, v_{k+2}, \dots, v_{k+\ell} \rangle$

**else**

$v_{j+1} \in S(w_r) \cap \mathcal{A}_{F_L}^{j+1}(v_k)$ for some $r \in [0, j+1]$ and $w_r \in \mathcal{E}_r$;

$v_j = z + \lambda e^i$ and $v'_j = z' + \lambda' e^{i'}$ where $\lambda, \lambda' \in \{\pm 1, \pm 2\}$,

$i, i' \in \mathcal{I}_4(v_k) \cap \mathcal{I}_2(v_{j+1})$ and $z, z' \in \{v_{j+1}, w_r\}$ (by Remark 37);

**if** $i \neq i'$ **then**

**if** $|\lambda| = |\lambda'|$ **then**

$v''_{j-1} := z + \lambda e^i + \lambda' e^{i'}$

**else**

(suppose $|\lambda| = 1$ and $|\lambda'| = 2$) $v''_{j-1} := w_r + 2\lambda e^i + \lambda' e^{i'}$

**end**

by Proposition 40, there exists $v''_t \in \mathcal{C}_t$, $t \in [k+1, j-2]$, such that

$\alpha := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_\ell \rangle$ and $\alpha' := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_{k+\ell} \rangle$ are in $\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$;

**if** $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$) do not share an $(\ell-1)$-face **then**

repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$)

**end**

**else**

by Remark 37, $\exists$ $i'' \neq i$ s.t. $v''_j := z'' + \lambda'' e^{i''} \in \mathcal{D}_{F_L}^j(v_{j+1}) \cap \mathcal{A}_{F_L}^j(v_k)$ for some $z'' \in \{v_{j+1}, w_r\}$ and $\lambda'' \in \{\pm 1, \pm 2\}$;

**if** $v_k \in \mathcal{O}_k$ **then**

$i'' \in \mathcal{I}_2(v_{j+1}) \cap \mathcal{I}_2(v_k)$

**else if** $v_k \in \mathcal{E}_k \setminus R$ and $v_{j+1} \in \mathcal{E}_{j+1} \setminus R$ **then**

$i'' \in \mathcal{I}_4(v_{j+1}) \cap \mathcal{I}_4(v_k)$

**else**

$i'' \in \mathcal{I}_2(v_{j+1}) \cap \mathcal{I}_4(v_k)$

**end**

by Proposition 40, there exists $v''_t \in \mathcal{C}_t$, for $t \in [k+1, j-1]$, such that $\alpha := \langle v_k, v''_{k+1}, \dots, v''_j, v_{j+1}, \dots, v_{k+\ell} \rangle$ is in

$\mathcal{A}_{\mathcal{P}_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$;

**if** $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$) do not share an $(\ell-1)$-face **then**

repeat the process for $\sigma$ and $\alpha$ (resp. $\alpha'$ and $\sigma'$)

**end**

**end**

**end**
<figure><img src="image_14.png" /><figcaption>Figure 11: Computing a face-connected path (using Procedure 7) joining two simplices of $P_S(I)$ which are incident to $v_1 \in C_1$. Blue points belong to $C_0$, red points to $C_1$ and green ones to $C_2$. In Case A and Case B, we start from $\sigma = \langle v_0, v_1 \rangle$ and $\sigma' = \langle v'_0, v'_1 \rangle$ and we deduce directly the face-connected path $\pi = (\sigma, \sigma')$ in $\mathcal{A}_{P_S(I)}^{(1)}(\langle v_1 \rangle)$, since $\sigma$ and $\sigma'$ share $v_1$.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 12: Computing a face-connected path (using Procedure 7) joining two simplices of $P_S(I)$ incident to $v_2 \in C_2$. Blue points belong to $C_0$, red points to $C_1$ and green ones to $C_2$. Case A: let $\sigma = \langle v_0, v_1, v_2 \rangle$ and $\sigma' = \langle v'_0, v'_1, v'_2 \rangle$. Then $z = w_2 = v_2$. Since $i = i'$, there exists $t \in O_4(v_2)$. Let $w_1'' = v_2 + \lambda''et$, from which we compute $v_0''$, and then $v_0''$. We obtain then $\alpha = \langle v_0'', v_1'', v_2 \rangle$ and $\alpha' = \langle v_0'', v_1', v_2 \rangle$ which share a 1-face. Since $\sigma$ and $\alpha$ do not share a 1-face, we again apply the procedure to obtain the face-connected path joining them. Case B: let $\sigma = \langle v_0, v_1, v_2 \rangle$ and $\sigma' = \langle v'_0, v'_1, v'_2 \rangle$. Then $z = w_2 = v_2$. Since $i \neq i'$ and $\lambda \neq \lambda'$, we compute $w_0'' \in C_0$, and then $w_0'' = w_0''$. We deduce $\alpha = \langle v_0'', v_1, v_2 \rangle$ and $\alpha' = \langle v_0'', v_1', v_2 \rangle$. We obtain the face-connected path $(\sigma, \alpha, \alpha', \sigma')$ joining $\sigma$ and $\sigma'$ in $\mathcal{A}_{P_S(I)}^{(2)}(\langle v_2 \rangle)$.</figcaption></figure>

Let $\ell \in [0, n-1]$ and $v_\ell \in C_\ell$. We have the following results.

**Remark 41.** Any two $n$-simplices are face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v_\ell, v_n \rangle)$.

**Proposition 42.** Let $v_n, v'_n \in \mathcal{A}_{F_L}^n(v_\ell)$ such that $v_n \in \mathcal{E}_k \cap R$ and $v'_n \in \mathcal{A}_{F_J}(v_n)$ for some $k \in [0, n-1]$. There exist two $n$-simplices (one incident to $v_n$ and the other incident to $v'_n$) in $\mathcal{A}_{P_S(I)}(\langle v_\ell \rangle)$ sharing a common $(n-1)$-face.

**Proposition 43.** Let $w_n, w'_n \in \mathcal{E}_n \cap \mathcal{A}_{F_L}^n(v_\ell)$. If $w_n$ and $w'_n$ are $2n$-neighbors, then there exist two $n$-simplices (one incident to $w_n$ and the other incident to $w'_n$) face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v_\ell \rangle)$.
<figure><img src="image_16.png" /><figcaption>Figure 13: From left to right: an nD picture $I = (\mathbb{Z}^n, F_I)$; its corresponding simplicial complex $P_S(I)$ (blue points belong to $C_0$, red points to $C_1$ and green ones to $C_2$), a vertex $v$ and two $n$-simplices $\sigma$ and $\sigma'$ of $P_S(I)$ incident to $v$; looking for a path in $A_{P_S(I)}^{(2)}(\langle v \rangle)$ joining $\sigma = \langle v, v_1, v_2 \rangle$ and $\sigma' = \langle v, v'_1, v'_2 \rangle$: since $v_2 \in \mathcal{E}_1 \cap R$ and $v'_2 \in \mathcal{E}_1 \cap R$ then $k = k' = 1$; since Card$(0_4)(v)$ is 0 then $l' = 0$ and there exists only one $\omega \in \mathcal{E}_0 \cap R$ such that $v \in S(\omega)$; we deduce the path $(\sigma^{(0,-)} = \sigma, \sigma^{(0,+)}, \sigma^{(1,-)}, \sigma^{(1,+)}, \sigma^{(2,-)}, \sigma^{(2,+)} = \sigma')$ joining $\sigma$ and $\sigma'$.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Figure 14: Diagram of the proof of Th. 44.</figcaption></figure>

Finally, the main result of the paper ensures that the simplicial complex $P_S(I)$ previously constructed is always wWC. This proof is illustrated in Figure 13.

**Theorem 44.** *The simplicial complex $P_S(I)$ is always wWC.*

In Figure 14 a diagram of the proof of Th. 44 is given. A 4D example is depicted in Figure 15 (in fact, the projections on the fourth coordinate $t$, from $t = -2$ to $t = 6$).

**6. Complexity**

Starting from an nD binary image $I_0 = (\mathbb{Z}^n, F_{I_0})$ whose domain is contained in an $n$D rectangle of $M_0$ pixels, we scale it by a factor of 4 to obtain the new image $I = (\mathbb{Z}^n, F_I)$ contained in an $n$D rectangle of $M = 4^n \cdot M_0$ pixels.

The time complexity of $\{\mathcal{E}_\ell\}_{\ell \in [0,n]}$, $\{\mathcal{O}_\ell\}_{\ell \in [0,n-1]}$ and the $0_4, 2_4, 0_2$ and $1_2$ operators is $\theta(n \cdot M)$. With $p \in \mathbb{Z}^n$, when $0_2(p) = [1,n]$, we obtain $\mathcal{N}^+(p)$ by setting all the values $\lambda_i$ to $\{0, \pm 1\}$ in the expression $p + \lambda_1 e^1 + \cdots + \lambda_n e^n$. The time complexity of $\mathcal{N}^+(p)$ is $O(3^n \cdot n^2)$. We can compute the values of $\mathcal{N}^+(p)$ only for $p \in [-1, 2]^n$ (by periodicity). This way, we obtain a time complexity of $O(3^n \cdot n^2 \cdot 4^n)$ for computing $\mathcal{N}^+$. The same reasoning holds for $S$ and $D_{F_J}$. Let us now estimate the complexity of Procedure 1. As detailed in [1],
<figure><img src="image_18.png" /><figcaption>Figure 15: A primary 4D CC $X = \{p, p'\}$, with $p = (0, 0, 0, 0)$ and $p' = (4, 4, 4, 4)$, repaired into a wWC cell complex by the implementation of the method proposed in the paper.</figcaption></figure>

detecting CCs in an nD image of $M$ pixels can be done in $O(5^n \cdot M)$ and a slight modification of this method will give the coordinates of the center $p^*$ of each CC in $I$. The union of $V$ and $\mathcal{D}_{F_J}^0(p^*)$ needs at most $3^n \cdot M$ operations, which means a total of $O(3^n \cdot M^2 \cdot 5^n)$ operations for the first loop of Procedure 1. Concerning the second loop, we have to check if $\mathcal{D}_{F_J}^0(q) \cap V$ is empty, which means a maximum of $3^n \cdot M$ operations for each $q$. The time complexity of the second loop is $O(3^n \cdot M^2)$. The time complexity of Procedure 1 is then $O(15^n \cdot M^2)$. Since $\mathcal{D}_{F_J}(p)$ and $S(p)$ are known, the computation of $F_J$ and of $F_L$ can be done in $O(M)$ each. The time complexity of $C_{\ell \in \llbracket 0, n \rrbracket}$ is $O(M \cdot n)$ and the time complexity of $\mathcal{D}_{F_L}$ is $O(3^n \cdot M^2 + 27^n \cdot M)$. About the computation of $P_S(I)$ in Procedure 6, for each $\ell \in \llbracket 1, n \rrbracket$ and $p \in C_\ell$, we have a maximum of $\mathcal{A}(n)$ simplices in $P_S(I)$, which is less or equal to $2^{2^n} \cdot M$ and a maximum of $3^n$ vertices in $\mathcal{D}_{F_L}(p)$. Since we check if the vertices of each simplex of $P_S(I)$ belong to $\mathcal{D}_{F_L}(p)$, we proceed to make at most $\mathcal{A}(n) \cdot (n+1) \cdot 3^n \cdot n$ operations. The time complexity of $p \ast K_{\mathcal{D}_{F_L}}(p)$ is $O(3^n \cdot n)$, and the one of the union with $P_S(I)$ is $O(3^n \cdot \mathcal{A}(n))$. The time complexity of the computation of $P_S(I)$ is then $O(\mathcal{A}(n) \cdot 3^n \cdot n^2 \cdot M)$. The time complexity for computing $P_S(I)$ is then $T_{\text{comp}}(M_0, n) = O(2^{2^n} \cdot 48^n \cdot n^2 \cdot M_0^2 + 108^n \cdot M_0)$.

In terms of storage, $F_I$, $F_J$, and $F_L$ are matrices of size $M$. The sets $\{\mathcal{E}_\ell\}_{\ell \in \llbracket 0, n \rrbracket}$ and $\{\mathcal{O}_\ell\}_{\ell \in \llbracket 0, n-1 \rrbracket}$ need one matrix of size $4^n$ each. By periodicity, the $0_4$, $2_4$, $0_2$ and $1_2$ operators can be stored as matrices of lists, and then will use an amount of space not greater than $4^n \cdot n$. Then, the sets $\mathcal{N}^+(p)$ and $\mathcal{D}_{F_J}(p)$ can be stored using matrices of $4^n$ lists, which makes an amount
of $4^n \cdot 3^n \cdot n$ bytes. The sets $V$, $R$, and the elements of the family $\{C_\ell\}_{\ell \in [0,n]}$ will be stored in one matrix of size $M$ each. For each $p$, the sets $D_{F_L}(p)$ will be stored as matrices of size $3^n$ of elements of $n$ coordinates, which means a total of $M \cdot 3^n \cdot n$ bytes at most. Finally, the set $P_S(I)$ uses an amount of memory not greater than $A(n)$ simplices times a maximal number of $(n+1)$ points made of $n$ coordinates. Then, the final storage cannot be greater than $A(n) \cdot (n+1) \cdot n$. The total amount of memory needed is then $T_{stor}(M_0, n) = O(2^{2n} \cdot n^2 \cdot 4^n \cdot M_0)$.

When the dimension $n$ is a constant, the time complexity and the amount of memory needed to compute $P_S(I)$ are, respectively, quadratic and linear w.r.t. the number of pixels of $I$.

## 7. Conclusion

The method presented in this paper extends a 3D method presented in [13, 14, 15] to any dimension. Starting from an nD cubical complex $Q(I)$ that is not well-composed, we “topologically repair” it by computing a simplicial complex $P_S(I)$ which is homotopy equivalent to $Q(I)$ and wWC. In subsequent work, our goal is to prove that $P_S(I)$ is (continuously) well-composed. One way is to prove that $P_S(I)$ is a subdivision of a cell complex $P(I)$ that generalizes the one computed in [13, 14] and that can be efficiently stored as an nD binary image by storing one point per $n$-cell, as in the 3D case studied in [15].

**Acknowledgments.** We thank both reviewers for their valuable suggestions.

## References

[1] Nicolas Boutry. *A Study of Well-composedness in nD*. PhD thesis, Université Paris-Est, France, 2016.

[2] Nicolas Boutry, Thierry Géraud, and Laurent Najman. 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*, volume 9082 of *Lecture Notes in Computer Science*, pages 561–572. Springer, 2015.

[3] Nicolas Boutry, Thierry Géraud, and Laurent Najman. How to make nD images well-composed without interpolation. In *IEEE International Conference on Image Processing*, pages 2149–2153. IEEE, 2015.

[4] Nicolas Boutry, Thierry Géraud, and Laurent Najman. A tutorial on well-composedness. *Journal of Mathematical Imaging and Vision*, 60(3):443–478, 2018.

[5] Nicolas Boutry, Laurent Najman, and Thierry Géraud. Well-composedness in alexandrov spaces implies digital well-composedness in $Z^n$. In *International Conference on Discrete Geometry for Computer Imagery*, volume 10502 of *Lecture Notes in Computer Science*, pages 225–237. Springer, 2017.
[6] Xavier Daragon, Michel Couprie, and Gilles Bertrand. Discrete surfaces and frontier orders. *Journal of Mathematical Imaging and Vision*, 23(3):379–399, 2005.

[7] Tamal K Dey and Kuiyu Li. Persistence-based handle and tunnel loops computation revisited for speed up. *Computers & Graphics*, 33(3):351–358, 2009.

[8] Tamal K Dey, Kuiyu Li, and Jian Sun. On computing handle and tunnel loops. In *IEEE International Conference on Cyberworlds*, pages 357–366. IEEE, 2007.

[9] Tamal K Dey, Kuiyu Li, Jian Sun, and David Cohen-Steiner. Computing geometry-aware handle and tunnel loops in 3D models. *Transactions on Graphics*, 27(3), 2008.

[10] Michael S Floater and Kai Hormann. Surface parameterization: a tutorial and survey. In *Advances in multiresolution for geometric modelling*, pages 157–186. Springer, 2005.

[11] James D Foley, Andries Van Dam, Steven K Feiner, John F Hughes, and Richard L Phillips. *Introduction to computer graphics*, volume 55. Addison-Wesley Reading, 1994.

[12] Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano. Well-composed cell complexes. In *International Conference on Discrete Geometry for Computer Imagery*, volume 6607 of *Lecture Notes in Computer Science*, pages 153–162. Springer, 2011.

[13] Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano. 3D well-composed polyhedral complexes. *Discrete Applied Mathematics*, 183:59–77, 2015.

[14] Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano. Encoding specific 3D polyhedral complexes using 3D binary images. In *International Conference on Discrete Geometry for Computer Imagery*, volume 9647 of *Lecture Notes in Computer Science*, pages 268–281. Springer, 2016.

[15] Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano. Efficiently storing well-composed polyhedral complexes computed over 3D binary images. *Journal of Mathematical Imaging and Vision*, 59(1):106–122, 2017.

[16] Rocio Gonzalez-Diaz, Maria Jose Jimenez, Belen Medrano, Helena Molina-Abril, and Pedro Real. Integral operators for computing homology generators at any dimension. In *Iberoamerican Congress on Pattern Recognition*, volume 5197 of *Lecture Notes in Computer Science*, pages 356–363. Springer, 2008.
[17] Rocio Gonzalez-Diaz, Javier Lamar, and Ronald Umble. Computing cup products in $Z_2$-cohomology of 3D polyhedral complexes. *Foundations of Computational Mathematics*, 14(4):721–744, 2014.

[18] Allen Hatcher. *Algebraic topology*. Cambridge University Press, 2002.

[19] T Yung Kong and Azriel Rosenfeld. Digital topology: Introduction and survey. *Computer Vision, Graphics, and Image Processing*, 48(3):357–393, 1989.

[20] Ralph Kopperman, Paul R Meyer, and Richard G Wilson. A jordan surface theorem for three-dimensional digital spaces. *Discrete & Computational Geometry*, 6(2):155–161, 1991.

[21] Jacques-Olivier Lachaud. *Espaces non-euclidiens et analyse d'image: modèles déformables riemanniens et discrets, topologie et géométrie discrète*. PhD thesis, Université Sciences et Technologies-Bordeaux I, 2006.

[22] Jacques-Olivier Lachaud and Annick Montanvert. Continuous analogs of digital boundaries: A topological approach to iso-surfaces. *Graphical models*, 62(3):129–164, 2000.

[23] Jacques-Olivier Lachaud and Boris Thibert. Properties of gauss digitized shapes and digital surface integration. *Journal of Mathematical Imaging and Vision*, 54(2):162–180, 2016.

[24] Longin Latecki, Ulrich Eckhardt, and Azriel Rosenfeld. Well-composed sets. *Computer Vision and Image Understanding*, 61(1):70–83, 1995.

[25] Longin Jan Latecki. 3D well-composed pictures. *Graphical Models and Image Processing*, 59(3):164–172, 1997.

[26] Longin Jan Latecki. Well-composed sets. In *Advances in Imaging and Electron Physics*, volume 112, pages 95–163. Elsevier, 2000.

[27] William E. Lorensen and Harvey E. Cline. Marching cubes: A high resolution 3D surface construction algorithm. In *Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques*, SIGGRAPH, pages 163–169, New York, NY, USA, 1987. ACM.

[28] William S Massey. *A basic course in algebraic topology*. Springer Science & Business Media, 1991.

[29] Loïc Mazo, Nicolas Passat, Michel Couprie, and Christian Ronse. Digital imaging: A unified topological framework. *Journal of Mathematical Imaging and Vision*, 44(1):19–37, 2012.

[30] Michael E Mortenson. *Geometric modeling*. Wiley, 1997.

[31] James R Munkres. *Elements of algebraic topology*, volume 4586. Addison-Wesley, 1984.
[32] Laurent Najman and Thierry Géraud. Discrete set-valued continuity and interpolation. In *International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing*, volume 7883 of Lecture Notes in Computer Science, pages 37–48. Springer, 2013.

[33] Azriel Rosenfeld. Digital topology. *American Mathematical Monthly*, 86(8):621–630, 1979.

[34] Colin P Rourke and Brian Joseph Sanderson. *Introduction to piecewise-linear topology*. Springer Science & Business Media, 2012.

[35] Marcelo Siqueira, Longin Jan Latecki, and Jean Gallier. Making 3D binary digital images well-composed. In *SPIE, Vision Geometry XIII*, volume 5675, pages 150–164. International Society for Optics and Photonics, 2005.

[36] Peer Stelldinger and Longin Jan Latecki. 3D object digitization: Majority interpolation and marching cubes. In *18th International Conference on Pattern Recognition*, volume 2, pages 1173–1176. IEEE, 2006.

[37] Yang Wang and Prabir Bhattacharya. Digital connectivity and extended well-composed sets for gray images. *Computer Vision and Image Understanding*, 68(3):330–345, 1997.

**Annex: Proofs of the results presented in Section 5**

**Proof of Proposition 31.** If $p \in \mathcal{E}_\ell \setminus R$, the assertion is true by Proposition 12. If $p \in \mathcal{E}_\ell \cap R$, then $p \in \mathcal{C}_n$ and $S(p) \setminus \{p\} \subseteq \sqcup_{i \in \llbracket \ell, n-1 \rrbracket} \mathcal{O}_i$. If $q \in \mathcal{D}_{F_j}(p)$, then $q \in \sqcup_{i \in \llbracket 0, n-1 \rrbracket} \mathcal{E}_i$ and $S(q) \setminus \{q\} \subseteq \sqcup_{i \in \llbracket 0, \ell-1 \rrbracket} \mathcal{O}_i$. Finally, if $p \in \mathcal{O}_\ell$, $\ell < n$, let $k \in \llbracket 0, \ell \rrbracket$ be $\text{Card}(\mathcal{O}_4(p))$: If $p \in S(q)$, then $q \in \mathcal{E}_k$ and $\mathcal{D}_{F_j}(q) \subseteq \sqcup_{i \in \llbracket 0, k-1 \rrbracket} \mathcal{E}_i$. Besides, $S(q) \subseteq \mathcal{E}_k \sqcup (\sqcup_{i \in \llbracket k, n-1 \rrbracket} \mathcal{O}_i)$ and $N(p) \subseteq \sqcup_{i \in \llbracket 0, \ell-1 \rrbracket} \mathcal{O}_i$, so $S(q) \cap N(p) \subseteq \sqcup_{i \in \llbracket k, \ell-1 \rrbracket} \mathcal{O}_i$. In the case that $k = \ell$, one can check that $S(q) \cap N(p) = \emptyset$. Since $\mathcal{D}_{F_j}(q) \subseteq \sqcup_{i \in \llbracket 0, k-1 \rrbracket} \mathcal{E}_i$, if $r \in \mathcal{D}_{F_j}(q)$ then $S(r) \subseteq (\sqcup_{i \in \llbracket 0, k \rrbracket} \mathcal{E}_i) \sqcup (\sqcup_{j \in \llbracket i, n-1 \rrbracket} \mathcal{O}_j)$ and then $S(r) \cap N(p) \subseteq \sqcup_{j \in \llbracket k-1, \ell-1 \rrbracket} \mathcal{O}_j$. $\square$

**Proof of Proposition 36.** For each $p \in \mathcal{C}_\ell$, let $p'$ be a point in $\mathcal{A}_{F_L}(p)$. Let us prove first that $p' \in \sqcup_{i \in \llbracket \ell+1, n \rrbracket} \mathcal{C}_i$ and that $p \in \mathcal{D}_{F_L}(p')$. If $p \in \mathcal{E}_\ell \setminus R$:

* If $p' \in \mathcal{A}_{F_j}(p) \setminus R$, then $p' = p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j e^j$ for some $\lambda_j \in \{0, \pm 2\}$, not all null, so $p' \in \mathcal{E}_{\ell+k}$ ($k$ is the number of coefficients $\lambda_j \neq 0$). By Lemma 14, $p \in \mathcal{D}_{F_j}(p')$. Since $p' \notin R$, $\mathcal{D}_{F_j}(p') = \mathcal{D}_{F_L}(p')$. Hence $p \in \mathcal{D}_{F_L}(p')$.

* If $p' \in \sqcup_{q \in \mathcal{A}_{F_j}(p) \cap R} S(q)$, let $q = p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j^* e^j$ be the point in $\mathcal{E}_{\ell+k} \cap R$ such that $\lambda_j^* = 2$ or $-2$ for specific subset of $k$ indices in $\mathcal{O}_4(p)$ and $\lambda_j^* = 0$ for the rest. The points in $S(q)$ are those with the form $p + \sum_{j \in \mathcal{O}_4(p)} \lambda_j^* e^j + \sum_{j \in \mathcal{O}_4(q)} \lambda_j e^j$ with $\lambda_j \in \{0, \pm 1\}$, so they lie in $\mathcal{E}_{k+\ell}$ if all the coefficients $\lambda_j$ are null (the point $q$ itself) or in $\mathcal{O}_{n-k'}$, with $k'$
being the number of non-null coefficients $\lambda_j$. Since $1 \le k' \le n - \ell - k$, we know $S(q) \subset \mathcal{E}_{k+\ell} \sqcup \bigsqcup_{i \in [k+\ell, n-1]} \mathcal{O}_i$. In the case that $p' = q \in \mathcal{E}_{k+\ell} \cap R$, the point $p' + \sum_{j \in 0_4(p') \cap 2_4(p)} -\lambda_j^* e^j$ is $p$, which is, therefore, a point in $\mathcal{D}_{F_j}(p') \setminus R \subset \mathcal{D}_{F_L}(p')$; if $p' \in S(q) \setminus \{q\}$, with $q \in \mathcal{A}_{F_j}(p) \cap R$, then $p \in \mathcal{D}_{F_j}(q)$ by Lemma 14, and hence, $p \in \mathcal{D}_{F_j}(q) \setminus R \subset \mathcal{D}_{F_L}(p')$.

If $p \in \mathcal{O}_\ell$, let $q$ be the point such that $p \in S(q)$. Let $\ell_1 := \text{Card}(0_4(p))$, then $q \in \mathcal{E}_{\ell_1}$ and $\ell_1 \le \ell$. Let $p'$ be a point in $\mathcal{A}_{F_L}(p)$. Then, $p' = p + \sum_{j \in 1_2(p)} \lambda_j e^j$, with $\lambda_j = 1$ or $-1$ for a specific subset of $k$ indices in $1_2(p)$ ($1 \le k \le n-\ell$) and $\lambda_j = 0$ otherwise. For $1 \le k \le n-\ell-1$, $p' \in \mathcal{O}_{\ell+k}$, that is, $p' \in \bigsqcup_{i \in [\ell+1, n-1]} \mathcal{C}_i$. For $k = n-\ell$, $p' \in \mathcal{E}_{\ell'}$ where $\ell'$ is Card$(0_4(p'))$, which satisfies that $\ell_1 \le \ell'$, since some of the odd coordinates in $p$ may have become congruent with 0 mod 4 in $p'$. Notice that, in this case, $p' \in \mathcal{A}_{F_j}(q)$, since both $p'$ and $q$ are points in $2\mathbb{Z}^n$ and $0_4(q) \subset 0_4(p')$, but then, $p' \in R$ by Remark 19, since $q \in R$. Hence, $p' \in \mathcal{E}_{\ell'} \cap R \subset \mathcal{C}_n$. Let us prove now that $p \in \mathcal{D}_{F_L}(p')$.

* If $1 \le k \le n - \ell - 1$, $p' \in \mathcal{O}_{k+\ell}$. Let $q'$ be the point such that $p' \in S(q')$. Notice that $q' \in \mathcal{E}_{\ell_1+k_1}$, for some $0 \le k_1 \le n-\ell-1$, which is $\text{Card}(0_4(p')) \setminus \text{Card}(0_4(p))$. If $p$ and $p'$ lie in the same $S$-block, that is, $q = q'$ (which happens when $k_1 = 0$), then $p \in S(q') \cap N(p')$, so $p \in \mathcal{D}_{F_L}(p')$. On the other hand, if $q \ne q'$ then $q' \in \mathcal{E}_{\ell_1+k_1}$, with $1 \le k_1 \le k$. Since $q \in \mathcal{E}_{\ell_1} \cap R$, by Remark 19, $q' \in \mathcal{E}_{\ell_1+k_1} \cap R$ and $\exists r \in \mathcal{D}_{F_j}(q') \cap R$ such that $p \in S(r) \cap N(p')$, which is $r = q$. So $p \in \mathcal{D}_{F_L}(p')$.

* If $k = n - \ell$, $p' \in \mathcal{E}_{\ell'}$ with $\ell_1 \le \ell'$. There are two cases: if $\ell' = \ell_1$, then $p' = q$ and since $p \in S(q)$, $p \in \mathcal{D}_{F_L}(p')$; if $\ell' > \ell_1$, then by Remark 19, $p' \in \mathcal{E}_{\ell'} \cap R$ since $p' \in \mathcal{A}_{F_j}(q)$ and $q \in R$. Also, $p \in N(p')$ and there exists a point $q' \in \mathcal{D}_{F_j}(p') \cap R$ such that $p \in S(q')$, which is $q' = q$. So $p \in \mathcal{D}_{F_L}(p')$.

Now, let us prove the converse.

If $p' \in \mathcal{E}_\ell \setminus R$, then $\mathcal{D}_{F_L}(p') = \mathcal{D}_{F_j}(p') \subset \mathcal{E}_k \setminus R$, with $k < \ell$ (by Remark 19). If $p \in \mathcal{D}_{F_j}(p')$, then $p' \in \mathcal{A}_{F_j}(p) \setminus R \subset \mathcal{A}_{F_L}(p)$.

If $p' \in \mathcal{E}_\ell \cap R$ and $p \in \mathcal{D}_{F_L}(p')$, we have the following cases:

* $p \in S(p') \setminus \{p'\}$, then $p = p' + \sum_{j \in 2_4(p')} \lambda_j e^j$, with $\lambda_j \in \{0, \pm 1\}$, not all null, so $p \in \mathcal{O}_{n-k}$, $k$ being the number of coefficients $\lambda_j \ne 0$, $k \in [1, n-\ell]$. Then points in $\mathcal{A}_{F_L}(p)$ are under the form $p + \sum_{j \in 1_2(p)} \mu_j e^j$, with $\mu_j \in \{0, \pm 1\}$ not all null. Since $\{j \in 2_4(p') : \lambda_j \ne 0\} = 1_2(p)$, we have $p' = p + \sum_{j \in 1_2(p)} (-\lambda_j) e^j$ and hence $p' \in \mathcal{A}_{F_L}(p)$.

* $p \in \mathcal{D}_{F_j}(p') \setminus R$, then $p = p' + \sum_{j \in 0_4(p')} \lambda_j e^j$, for some coefficients $\lambda_j \in \{0, \pm 2\}$, not all null, such that $p \notin R$. Then $p \in \mathcal{E}_{\ell-k} \setminus R$, $k$ being the number of coefficients $\lambda_j \ne 0$, $1 \le k \le \ell$. Since $p' \in \mathcal{A}_{F_j}(p) \cap R$, then $S(p') \subset \mathcal{A}_{F_L}(p)$ and hence, $p' \in \mathcal{A}_{F_L}(p)$.

* $p \in \bigsqcup_{r \in \mathcal{D}_{F_j}(p') \cap R} (S(r) \cap N(p'))$. Let $r = p' + \sum_{j \in 0_4(p')} \lambda_j^* e^j$, with $\lambda_j^* \in \{0, \pm 2\}$, not all null, be a point in $\mathcal{D}_{F_j}(p') \cap R$, such that $p =$
$p' + \sum_{j \in \mathcal{O}_{4}(p')} \frac{1}{2} \lambda_j^* e^j + \sum_{j \in \mathcal{O}_{24}(p')} \lambda_j e^j$, for some coefficients $\lambda_j \in \{0, \pm 1\}$. Hence $p \in \mathcal{O}_{n-k-k'}$, where $k$ and $k'$ are, respectively, the number of coefficients $\lambda_j^* \neq 0$ and $\lambda_j \neq 0$. Thus $p' = p + \sum_{j \in \mathcal{O}_{12}(p)} \mu_j e^j$, with $\mu_j = -\frac{1}{2} \lambda_j^*$ for the indices $j$ such that $\lambda_j^* \neq 0$, and $\mu_j = -\lambda_j$ for those $j$ such that $\lambda_j \neq 0$, what means that $p' \in \mathcal{A}_{\mathcal{F}_L}(p)$ (being $p \in \mathcal{O}_{n-k-k'}$).

If $p' \in \mathcal{O}_\ell$, let $q'$ be the point such that $p' \in S(q')$. We have $q' = p' + \sum_{j \in \mathcal{O}_{12}(p')} \mu_j^* e^j$, with $\mu_j^* = 1$, if $j \in \mathcal{O}_{14}(p')$ and $\mu_j^* = -1$ if $j \in \mathcal{O}_{34}(p')$. For a point $p \in \mathcal{D}_{\mathcal{F}_L}(p')$, we have the following cases:

* If $p \in S(q') \cap N(p')$, then $p = p' + \sum_{j \in \mathcal{O}_{24}(p')} \lambda_j e^j$, for some coefficients $\lambda_j \in \{0, \pm 1\}$, not all null. Now, $p \in \mathcal{O}_{\ell-k}$, $k$ being the number of coefficients $\lambda_j \neq 0$. Now, $p'$ can be expressed as $p' = p + \sum_{j \in \mathcal{O}_{12}(p)} \mu_j e^j$ with $\mu_j = -\lambda_j$ (and $\mu_j = 0$ for the indices $j$ for which $\lambda_j$ was not defined), so $p' \in \mathcal{A}_{\mathcal{F}_L}(p)$.

* If $p \in \mathcal{D}_{\mathcal{F}_J}(q') \setminus R$, then $q' \in \mathcal{A}_{\mathcal{F}_J}(p)$ (by Lemma 14); or, since $p' \in S(q')$, $q' \in R$. Hence, $q' \in \mathcal{A}_{\mathcal{F}_J}(p) \cap R$ and $p' \in S(q')$, so $p' \in \mathcal{A}_{\mathcal{F}_L}(p)$.

* If $p \in \bigsqcup_{r \in \mathcal{D}_{\mathcal{F}_J}(q') \cap R} (S(r) \cap N(p'))$. Let $r = q' + \sum_{j \in \mathcal{O}_{4}(q')} \lambda_j^* e^j$, with $\lambda_j^* \in \{0, \pm 2\}$, not all null, such that $r \in R$. Then $p = p' + \sum_{j \in \mathcal{O}_{4}(p')} \frac{1}{2} \lambda_j^* e^j + \sum_{j \in \mathcal{O}_{24}(p')} \lambda_j e^j$, for some coefficients $\lambda_j \in \{0, \pm 1\}$. Then $p \in \mathcal{O}_{\ell-k-k'}$ where $k$ and $k'$ are, respectively, the number of coefficients $\lambda_j^* \neq 0$ and $\lambda_j \neq 0$. Then $p' = p + \sum_{j \in \mathcal{O}_{12}(p)} \mu_j e^j$, with $\mu_j = -\frac{1}{2} \lambda_j^*$ for the indices $j$ such that $\lambda_j^* \neq 0$ and $\mu_j = -\lambda_j$ for those $j$ such that $\lambda_j \neq 0$, so $p' \in \mathcal{A}_{\mathcal{F}_L}(p)$ (being $p \in \mathcal{O}_{\ell-k-k'}$). $\square$

**Proof of Proposition 40.** Let $\ell \in [1, n]$ and $k \in [0, n - \ell]$.

Let us see how to construct $\sigma_{\mathcal{P}_S(I)}(v_\ell)$. Let $w_r \in \mathcal{E}_r$, $r \in [0, \ell]$, s.t. $v_\ell \in S(w_r)$. There exist subindices $1 \le i_1 < \dots < i_r \le n$ and $1 \le i_{r+1} < \dots < i_\ell \le n$ such that $\{i_1, \dots, i_r\} = \mathcal{O}_4(v_\ell)$ and $\{i_{r+1}, \dots, i_\ell\} = \mathcal{O}_4(v_\ell)$. From $j = \ell - 1$ to $j = r$, let $v_j := v_{j+1} + \lambda_{j+1} e^{i_{j+1}}$, $\lambda_{j+1} \in \{\pm 1\}$. From $j = r - 1$ to $j = 0$, let $w_j := w_{j+1} + \lambda_{j+1} e^{i_{j+1}}$, $\lambda_{j+1} \in \{\pm 2\}$. Then:

* If $w_j \notin R$, let $v_j := w_j$.

* Else, $w_j = w_r + \sum_{s \in [j+1, r]} \lambda_s^* e^{i_s}$ where $\lambda_s^* \in \{\pm 2\}$, for $s \in [j+1, r]$; let $v_j := v_r + \sum_{s \in [j+1, r]} \frac{1}{2} \lambda_s^* e^{i_s}$.

Then $v_j \in \mathcal{D}_{\mathcal{F}_L}^j(v_{j+1})$ and $\sigma_{\mathcal{P}_S(I)}(v_\ell) := \langle v_0, \dots, v_\ell \rangle \in P_S^{(\ell)}(I)$.

Let us see now how to construct $\sigma_{\mathcal{P}_S(I)}(v_k, v_{k+\ell})$.

* If $v_k \in \mathcal{O}_k$ then there exist subindices $1 \le i_{k+1} < \dots < i_{k+\ell} \le n$ such that $\{i_{k+1}, \dots, i_{k+\ell}\} = \mathcal{O}_2(v_{k+\ell}) \cap \mathcal{O}_1(v_k)$ and $v_k = v_{k+\ell} + \sum_{j \in [k+1, k+\ell]} \mu_j^* e^{i_j}$, where $\mu_j^* \in \{\pm 1\}$. From $j = k+\ell-1$ to $j = k+1$, let $v_j := v_{j+1} + \mu_{j+1}^* e^{i_{j+1}}$.

* If $v_{k+\ell} \in \mathcal{E}_{k+\ell} \setminus R$, then there exist subindices $1 \le i_{k+1} < \dots < i_{k+\ell} \le n$ such that $\{i_{k+1}, \dots, i_{k+\ell}\} = \mathcal{O}_4(v_{k+\ell}) \cap \mathcal{O}_2(v_k)$ and $v_k = v_{k+\ell} + \sum_{j \in [k+1, k+\ell]} \lambda_j^* e^{i_j}$, where $\lambda_j^* \in \{\pm 2\}$. From $j = k + \ell - 1$ to $j = k + 1$, let $v_j := v_{j+1} + \lambda_{j+1}^* e^{i_{j+1}}$.
• Else, $v_k \in \mathcal{E}_k \setminus R$, and there exists unique $w_r \in \mathcal{E}_r$, with $r \in [k, k+l]$, such that $v_{k+\ell} \in S(w_r)$ and subindices $1 \le i_{k+1} < \dots < i_r \le n$ and $1 \le i_{r+1} < \dots < i_{k+\ell} \le n$, such that $\{i_{k+1}, \dots, i_r\} = \mathbf{0}_4(v_{k+\ell}) \cap \mathbf{2}_4(v_k)$, and $\{i_{r+1}, \dots, i_{k+\ell}\} = \mathbf{2}_4(v_{k+\ell}) \cap \mathbf{2}_4(v_k)$. Then $v_k = w_r + \sum_{j \in [k+1, r]} \lambda_j^* e^{ij}$ where $\lambda_j^* \in \{\pm 2\}$. From $j=k+\ell-1$ to $j=r$, let $v_j := v_{j+1} + \mu_{j+1} e^{ij_{j+1}}$ where $\mu \in \{\pm 1\}$. From $j=r-1$ to $j=k+1$, let $w_j := w_{j+1} + \lambda_{j+1}^* e^{ij_{j+1}}$. If $w_j \in \mathcal{C}_j$, let $v_j := w_j$. Else, $v_j := w_r + \sum_{s \in [j+1, r]} \frac{1}{2} \lambda_s^* e^{is}$.

Then $v_j \in \mathcal{D}_{F_L}^j(v_{j+1}) \cap \mathcal{A}_{F_L}^j(v_k)$ and $\sigma_{P_S(I)}(v_k, v_{k+\ell}) := \langle v_k, \dots, v_{k+\ell} \rangle \in P_{S(I)}^{(\ell)}$. $\square$

**Proof of Procedure 7.** Let $\ell \in [1, n]$, $v_\ell \in \mathcal{C}_\ell$, $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$, $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v_\ell \rangle$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$. Let us prove property ($\mathcal{P}_\ell$): "there exists a face-connected path $\pi(\sigma, \sigma')$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$".

Initialization ($\ell=1$): two different 1-simplices $\sigma = \langle v_0, v_1 \rangle$ and $\sigma' = \langle v'_0, v'_1 \rangle$ in $P_S(I)$, with $v_1 \in \mathcal{C}_1$ are joined by the path $\pi(\sigma, \sigma') := (\sigma, \sigma')$ in $\mathcal{A}_{P_S(I)}^{(1)}(\langle v_1 \rangle)$.

Heredity ($\ell \in [2, n]$): we assume that ($\mathcal{P}_m$) is true for $m \in [1, \ell-1]$, let us prove that ($\mathcal{P}_\ell$) is true. Let us define $j \in [0, \ell-1]$ such that $v_j \ne v'_j$ and for any $i \in [j+1, \ell-1]$, $v_i = v'_i$. Then, we have $\sigma = \langle v_0, \dots, v_j, v_{j+1}, \dots, v_\ell \rangle$ and $\sigma' = \langle v'_0, \dots, v'_j, v_{j+1}, \dots, v_\ell \rangle$. Now, $v_{j+1} \in S(w_r)$ for some $r \in [0, j+1]$ and $w_r \in \mathcal{E}_r$. Let $\lambda, \lambda' \in \{\pm 1, \pm 2\}$, $i, i' \in 0_2(v_{j+1})$ and $z, z' \in \{v_{j+1}, w_r\}$ such that $v_j = z + \lambda e^i$ and $v'_j = z' + \lambda' e^{i'}$. Then, the following cases hold:

(1) If $i \ne i'$, then we define $v''_{j-1} \in \mathcal{D}_{F_L}^{j-1}(v_j) \cap \mathcal{D}_{F_L}^{j-1}(v'_j)$ and we deduce $\sigma_{P_S(I)}(v''_{j-1}) := \langle v''_0, \dots, v''_{j-1} \rangle \in P_S(I)$ by Proposition 40. We then define $\alpha := \langle v''_0, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_\ell \rangle$, and $\alpha' := \langle v''_0, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_\ell \rangle$. Then $\pi(\alpha, \alpha') := (\alpha, \alpha')$ is a face-connected path in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$. By ($\mathcal{P}_j$) where $j < \ell$, we know that there exists a path $\pi(\mu, \mu')$ joining $\mu = \langle v_0, \dots, v_{j-1}, v_j \rangle$ and $\mu' = \langle v''_0, \dots, v''_{j-1}, v_j \rangle$ in $\mathcal{A}_{P_S(I)}^{(j)}(\langle v_j \rangle)$. From this path, we can deduce a path $\pi(\sigma, \alpha)$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\alpha$. Similarly, we obtain $\pi(\alpha', \sigma') \in \mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$. By concatenation, we obtain a face-connected path in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$.

(2) When $i = i'$, we define $v''_j \in \mathcal{D}_{F_L}^j(v_{j+1})$. We deduce $\sigma_{P_S(I)}(v''_j) := \langle v''_0, \dots, v''_j \rangle \in P_S(I)$ by Proposition 40, and define $\alpha := \langle v''_0, \dots, v''_j, v_{j+1}, \dots, v_\ell \rangle$ joining $\sigma$ and $\alpha$ (respectively joining $\alpha$ and $\sigma'$). We can apply (1) to obtain two face-connected paths $\pi(\sigma, \alpha)$ and $\pi(\alpha, \sigma')$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$, and then a face connected path in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_\ell \rangle)$ joining $\sigma$ and $\sigma'$.

By induction on $\ell$, the property ($\mathcal{P}_\ell$) is true for any $\ell \in [1, n]$. $\square$

**Proof of Procedure 8.** Let $\ell \in [2, n]$, $v_{k+\ell} \in \mathcal{C}_{k+\ell}$ and $v_k \in \mathcal{D}_{F_L}^k(v_{k+\ell})$. Let $\sigma = \langle v_k, \dots, v_{k+\ell} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, \dots, v'_{k+\ell-1}, v_{k+\ell} \rangle$ be two $\ell$-simplices
of $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$. Let us prove property $(\mathcal{P}'_\ell)$: "there exists a face-connected path $\pi(\sigma, \sigma')$ of $\ell$-simplices in $\mathcal{A}_{P_S(I)}(\langle v_k, v_{k+\ell} \rangle)$ joining $\sigma$ and $\sigma''$.

Initialization ($\ell = 2$): The 2-simplices $\sigma = \langle v_k, v_{k+1}, v_{k+2} \rangle$ and $\sigma' = \langle v_k, v'_{k+1}, v_{k+2} \rangle$ share the 1-face $\langle v_k, v_{k+2} \rangle$.

Heredity ($\ell \in [3, n]$): we assume that $(\mathcal{P}'_\ell)$ is true for $m \in [2, \ell-1]$, and we want to prove that $(\mathcal{P}'_\ell)$ is true. By hypothesis, we have the four following $\ell$-simplices: $\sigma = \langle v_k, v_{k+1}, \dots, v_{j-1}, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$, $\alpha := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j, v_{j+1}, \dots, v_{k+\ell} \rangle$, $\alpha' := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v'_j, v_{j+1}, \dots, v_{k+\ell} \rangle$, $\sigma' = \langle v_k, v'_{k+1}, \dots, v'_{j-1}, v'_j, v_{j+1}, \dots, v_{k+\ell} \rangle$. Then $\alpha$ and $\alpha'$ share an $(\ell-1)$-face. Now, since $j$ belongs to $[k+1, k+\ell-1]$ then $j-k \le \ell-1$. From that, we can deduce by $(\mathcal{P}'_{j-k})$ that the $(j-k)$-simplices: $\mu := \langle v_k, v_{k+1}, \dots, v_{j-1}, v_j \rangle$ and $\mu' := \langle v_k, v''_{k+1}, \dots, v''_{j-1}, v_j \rangle$ are joined by a face-connected path $\pi(\mu, \mu')$ in $\mathcal{A}_{P_S(I)}^{(j-k)}(\langle v_k, v_j \rangle)$. By rewriting each $i^{th}$ element of $\pi(\mu, \mu')$ we can deduce the $i^{th}$ element of a new path $\pi(\sigma, \alpha)$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$ joining $\sigma$ and $\alpha$. We proceed similarly with $\alpha'$ and $\sigma'$ to obtain $\pi(\alpha', \sigma')$ in $\mathcal{A}_{P_S(I)}^{(\ell)}(\langle v_k, v_{k+\ell} \rangle)$. We finally obtain a face-connected path joining $\sigma$ and $\sigma'$ concatenating the previous paths.

By induction on $\ell \in [2, n]$, $(\mathcal{P}'_\ell)$ is true for any $\ell \in [2, n]$ and $k \in [0, n-\ell]$. $\square$

**Proof of Proposition 42.** First, since $v_\ell \in C_\ell$, there exists an $\ell$-simplex $\langle v_0, \dots, v_{\ell-1}, v_\ell \rangle$ in $P_S(I)$ by Proposition 40. Second, since $v_n \in \mathcal{E}_k \cap R$ and $v'_n \in \mathcal{A}_{F_j}(v_n)$, $v'_n \in \mathcal{E}_{k'} \cap R$ for some $k' \in [k+1, n]$ and $v_n = v'_n + \sum_{j \in [k+1, k]} \lambda_j^* e^{ij}$, where $\lambda_j^* \in \{\pm 2\}$ and $\{i_{k+1}^*, \dots, i_{k'}^*\} \subseteq \mathcal{O}_4(v'_n)$. There exist subindices $1 \le i_{k'+1} < \dots < i_n \le n$ and $1 \le i_{k+1} < \dots < i_{k'} \le n$ such that $\{i_{k'+1}, \dots, i_n\} = \mathcal{O}_4(v'_n)$ and $\{i_{k+1}, \dots, i_{k'}\} = \mathcal{O}_4(v_n) \cap \mathcal{O}_4(v'_n)$. Now, since $v_\ell \in \mathcal{D}_{F_L}(v_n) \cap \mathcal{D}_{F_L}(v'_n)$:

* If $v_\ell \in \mathcal{O}_\ell$ then $v_\ell = v'_n + \sum_{j \in [\ell+1, n]} \mu_j e^{ij}$ where: if $\ell \in [0, k-1]$ then $\mu_j \in \{\pm 1\}$ when $j \in [\ell+1, k] \cup [k'+1, n]$ and $\mu_j = \frac{1}{2}\lambda_j^*$ when $j \in [k+1, k]$; if $\ell \in [k, k'-1]$ then $\mu_j \in \{\pm 1\}$ when $j \in [k'+1, n]$ and $\mu_j = \frac{1}{2}\lambda_j^*$ when $j \in [\ell+1, k]$; if $\ell \in [k', n-1]$ then $\mu_j \in \{\pm 1\}$ when $j \in [\ell+1, n]$. From $j=n-1$ to $j=\ell+1$, let $v_j := v_{j+1} + \mu_{j+1} e^{ij+1}$.

* If $v_\ell \in \mathcal{E}_\ell$ then $v_\ell \notin R$ since $\ell < n$. Therefore, $\ell \in [0, k-1]$ and $v_\ell = v_n + \sum_{j \in [\ell+1, k]} \lambda_j e^{ij}$ where $\lambda_j \in \{\pm 2\}$ when $j \in [\ell+1, k]$. Additionally, there exist subindices $1 \le i_1 < \dots < i_\ell \le n$ such that $\{i_1, \dots, i_\ell\} = \mathcal{O}_4(v_\ell)$. For $j \in [\ell+1, k-1]$, let $w_j := v_n + \sum_{s \in [j+1, k]} \lambda_s^* e^{is}$, where $\lambda_s^* \in \{\pm 2\}$. Now, if $w_j \in C_j$, then $v_j := w_j$. Else $v_j := \sum_{s \in [\ell+1, k]} \frac{1}{2}\lambda_s^* e^{is} + \sum_{s \in [k'+1, n]} \mu_s e^{is}$, where $\mu_s \in \{\pm 1\}$. For $j \in [k, k'-1]$, let $v_j := \sum_{s \in [j+1, k]} \frac{1}{2}\lambda_s^* e^{is} + \sum_{s \in [k'+1, n]} \mu_s e^{is}$ where $\mu_s \in \{\pm 1\}$. For $j \in [k', n]$, let $v_j := \sum_{s \in [j+1, n]} \mu_s e^{is}$ where $\mu_s \in \{\pm 1\}$.

Then $\langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-1}, v_n \rangle$ and $\langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-1}, v'_n \rangle$ are two $n$-simplices incident to $v_\ell$ in $P_S(I)$ sharing a common $(n-1)$-face. $\square$
**Proof of Proposition 43.** Let $w_{n-1} := \frac{1}{2}(w_n + w'_n)$. Then $w_{n-1} \in \mathcal{E}_{n-1} \cap F_L$. We have to consider two cases:

If $w_{n-1} \notin R$ then $w_{n-1} \in \mathcal{C}_{n-1}$ and $\mathcal{D}_{F_L}(w_{n-1}) = \mathcal{D}_{F_J}(w_{n-1})$. Following the process given in Remark 24.(P1), one can compute an $(n-1)$-simplex $\mu := \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-2}, w_{n-1} \rangle \in P_S(I)$. Then $\mu$ is shared by the two $n$-simplices $\sigma = \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-2}, w_{n-1}, w_n \rangle$ and $\sigma' = \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-2}, w_{n-1}, w'_n \rangle$ in $\mathcal{A}_{P_S(I)}(\langle v_\ell \rangle)$. If $w_{n-1} \in R$ then $w_{n-1} \in \mathcal{C}_n$. Therefore:

* There exist two $n$-simplices, $\sigma$ (incident to $w_n$) and $\mu := \langle v_0, \dots, v_{\ell-1}, v_\ell, v_{\ell+1}, \dots, v_{n-1}, w_{n-1} \rangle$ (incident to $w_{n-1}$), in $\mathcal{A}_{P_S(I)}(\langle v_\ell \rangle)$ sharing a common $(n-1)$-face by Proposition 42.

* There exist two $n$-simplices, $\mu' := \langle v'_0, \dots, v'_{\ell-1}, v_\ell, v'_{\ell+1}, \dots, v'_{n-1}, w_{n-1} \rangle$ (incident to $w_{n-1}$) and $\sigma'$ (incident to $w'_n$), in $\mathcal{A}_{P_S(I)}(v_\ell)$ sharing a common $(n-1)$-face by Proposition 42.

* By Remark 41, there exists a face-connected path of $n$-simplices ($\mu^0 = \mu, \mu^1, \dots, \mu^{m-1}, \mu^m = \mu'$) in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v_\ell, w_{n-1} \rangle)$ joining $\mu$ and $\mu'$.

Finally, the face-connected path joining $\sigma$ (incident to $w_n$) and $\sigma'$ (incident to $w'_n$) in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v_\ell \rangle)$ is $(\sigma, \mu^0 = \mu, \dots, \mu^m = \mu', \sigma')$. $\square$

**Proof of Th. 44.** Let $v \in F_L$. We have $v \in \mathcal{C}_\ell$ for some $\ell \in [0, n]$. Let us prove property (P): $\sigma = \langle v_0, \dots, v_{\ell-1}, v, v_{\ell+1}, \dots, v_n \rangle$ and $\sigma' = \langle v'_0, \dots, v'_{\ell-1}, v, v'_{\ell+1}, \dots, v'_n \rangle$ are face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$. If $\ell = n$ then $\sigma$ and $\sigma'$ are face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$ by Procedure 7. Else, $\ell \in [0, n-1]$:

* If $v \in \mathcal{E}_\ell \setminus R$, then each $w \in \mathcal{A}_{F_L}^n(v)$ satisfies that $w \in \mathcal{E}_n \setminus R$. Therefore, there exists a 2n-path $\pi := (p^0 := v_n, p^1, \dots, p^{m-1}, p^m := v'_n)$ in $\mathcal{A}_{F_L}^n(v) \cap (\mathcal{E}_n \setminus R)$ joining $v_n$ and $v'_n$. If $v \in \mathcal{E}_\ell \setminus R$.

Since $v_n, v'_n \in \mathcal{A}_{F_L}^n(v)$ then $v_n \in \mathcal{E}_k \cap F_J$ and $v'_n \in \mathcal{E}_{k'} \cap F_J$ for some $k, k' \in [\ell+1, n]$.

Therefore, there exist $w_n, w'_n \in \mathcal{E}_n \cap F_J$ such that $v_n \in \mathcal{D}_{F_J}(w_n)$ and $v'_n \in \mathcal{D}_{F_J}(w'_n)$. Then $w_n, w'_n \in \mathcal{A}_{F_J}^n(v)$.

Since $v \in \mathcal{E}_\ell \setminus R$ then there exists a 2n-path $\pi := (p^0 := w_n, p^1, \dots, p^{m-1}, p^m := w'_n)$ in $\mathcal{A}_{F_J}^n(v)$ joining $w_n$ and $w'_n$.

By Prop. 42, 43 and Remark 41, one can find a face-connected path in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$ between $\sigma$ and $\sigma'$.

* Else, $v \in \mathcal{O}_\ell$. Let $\ell' := \text{Card}(\mathcal{O}_4(v))$. Then $v_n \in \mathcal{E}_k \cap R$, $v'_n \in \mathcal{E}_{k'} \cap R$ for some $k, k' \in [\ell', n]$ and there exists unique $w \in \mathcal{E}_{\ell'} \cap R$ such that $v \in S(w)$. Since $v \in \mathcal{D}_{F_L}(v_n) \cap \mathcal{D}_{F_L}(v'_n)$ then $w \in \mathcal{D}_{F_J}^+(v_n) \cap \mathcal{D}_{F_J}^+(v'_n)$. Let $\pi := (p^0 := v_n, p^1 := w, p^2 := v'_n)$.

Now, for $i \in [1, m]$:
• If $p^{i-1}, p^i$ are 2n-neighbors, then by Proposition 43 there exist simplices $\sigma^{(i-1,+)}$ (incident to $\langle p^{i-1} \rangle$) and $\sigma^{(i,-)}$ (incident to $\langle p^i \rangle$) that are face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$.

• If $p^{i-1} \in \mathcal{D}_{F_J}(p^i) \cap R$ or $p^{i-1} \in \mathcal{A}_{F_J}(p^i) \cap R$ then, by Proposition 42, there exist simplices $\sigma^{(i-1,+)}$ (incident to $\langle p^{i-1} \rangle$) and $\sigma^{(i,-)}$ (incident to $\langle p^i \rangle$) in $\mathcal{A}_{P_S(I)}(\langle v \rangle)$ sharing a common $(n-1)$-face.

Finally, let $\sigma^{(0,-)} := \sigma$ and $\sigma^{(m,+)} := \sigma'$. Then, each pair $(\sigma^{(i,-)}, \sigma^{(i,+)})$ for $i \in [0, m]$ is face-connected in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$ by Remark 41. Since $\mathcal{P}$ is true for any $v$ in $P_S(I)$ and $\sigma, \sigma'$ in $\mathcal{A}_{P_S(I)}^{(n)}(\langle v \rangle)$, then $P_S(I)$ is wWC. $\square$
<table><caption>Table 1: Notations used throughout the paper.</caption><thead><tr><th>NOTATION</th><th>DEFINITION/EXPLANATION</th></tr></thead><tbody><tr><td>|K|</td><td>Underlying polyhedron of the cell complex K</td></tr><tr><td>A<sub>K</sub><sup>(ℓ)</sup>(σ)</td><td>Set of ℓ-cells incident to the cell σ in K</td></tr><tr><td>σ * σ'</td><td>Cone join of the simplices σ and σ'</td></tr><tr><td>N<sub>M</sub>(p)</td><td>{i ∈ ⌊1, n⌋ : x<sub>i</sub> ≡ N mod M}</td></tr><tr><td>N<sub>2n</sub>(p)</td><td>{p ± 4e<sup>i</sup> : i ∈ ⌊1, n⌋}</td></tr><tr><td>N<sup>+</sup>(p)</td><td>{p + ∑<sub>j∈0<sub>2</sub>(p)</sub> λ<sub>j</sub> e<sup>j</sup> : λ<sub>j</sub> ∈ {0, ±1}</td></tr><tr><td>S-block S(p)</td><td>{p + ∑<sub>j∈2<sub>4</sub>(p)</sub> λ<sub>j</sub> e<sup>j</sup> : λ<sub>j</sub> ∈ {0, ±1}</td></tr><tr><td>B(z, F)</td><td>Block associated to the point z and the family of vectors F</td></tr><tr><td>I = (Z<sup>n</sup>, F<sub>I</sub>)</td><td>An nD binary image (called picture when F<sub>I</sub> ⊂ 4Z<sup>n</sup>)</td></tr><tr><td>Q(I)</td><td>Cubical complex associated to I</td></tr><tr><td>V</td><td>The set of critical vertices in Q(I)</td></tr><tr><td>Q<sub>S</sub>(I)</td><td>The simplicial subdivision of Q(I)</td></tr><tr><td>P<sub>S</sub>(I)</td><td>Weakly well-composed simplicial complex over the picture I</td></tr><tr><td>J = (Z<sup>n</sup>, F<sub>J</sub>)</td><td>nD binary image encoding the vertices of Q<sub>S</sub>(I) (i.e, the cells of Q(I))</td></tr><tr><td>R</td><td>The set of critical points in F<sub>J</sub> (which encode the critical cells of Q(I))</td></tr><tr><td>L = (Z<sup>n</sup>, F<sub>L</sub>)</td><td>nD binary image encoding the vertices of P<sub>S</sub>(I)</td></tr><tr><td>σ<sub>K</sub>(p)</td><td>simplex in K encoded by p (K = Q<sub>S</sub>(I), p ∈ F<sub>J</sub>; or K = P<sub>S</sub>(I), p ∈ F<sub>L</sub>)</td></tr><tr><td>E<sub>ℓ</sub></td><td>{p ∈ 2Z<sup>n</sup> : Card(0<sub>4</sub>(p)) is ℓ}, being ℓ ∈ ⌊0, n⌋</td></tr><tr><td>O<sub>ℓ</sub></td><td>{p ∈ Z<sup>n</sup> \ 2Z<sup>n</sup> : Card(0<sub>2</sub>(p)) is ℓ}, being ℓ ∈ ⌊0, n − 1⌋</td></tr><tr><td>C<sub>n</sub></td><td>(E<sub>n</sub> ∩ F<sub>L</sub>) ∪ R</td></tr><tr><td>C<sub>ℓ</sub></td><td>((E<sub>ℓ</sub> \ R) ∪ O<sub>ℓ</sub>) ∩ F<sub>L</sub>, being ℓ ∈ ⌊0, n − 1⌋</td></tr><tr><td>D<sup>+</sup><sub>F<sub>J</sub></sub>(p)</td><td>{p + ∑<sub>j∈0<sub>4</sub>(p)</sub> λ<sub>j</sub> e<sup>j</sup> : λ<sub>j</sub> ∈ {0, ±2}</td></tr><tr><td>A<sup>+</sup><sub>F<sub>J</sub></sub>(p)</td><td>{p + ∑<sub>j∈2<sub>4</sub>(p)</sub> λ<sub>j</sub> e<sup>j</sup> : λ<sub>j</sub> ∈ {0, ±2}</td></tr><tr><td>D<sup>+</sup><sub>F<sub>L</sub></sub>(p)</td><td>Set of points used for the construction of P<sub>S</sub>(I). See Definition 30</td></tr><tr><td>A<sup>+</sup><sub>F<sub>L</sub></sub>(p)</td><td>Set of points used to prove that P<sub>S</sub>(I) is weakly well-composed. See Definition 34</td></tr><tr><td>X<sub>(p)</sub></td><td>X<sup>+</sup>(p) \ {p} for X ∈ {N, D<sub>F<sub>J</sub></sub>, A<sub>F<sub>J</sub></sub>, D<sub>F<sub>L</sub></sub>, A<sub>F<sub>L</sub></sub>}</td></tr><tr><td>K<sub>D<sub>F<sub>J</sub></sub></sub>(p)</td><td>Subcomplex of Q<sub>S</sub>(I) formed by the simplices whose vertices lie in D<sub>F<sub>J</sub></sub>(p)</td></tr><tr><td>K<sub>D<sub>F<sub>L</sub></sub></sub>(p)</td><td>Subcomplex of P<sub>S</sub>(I) formed by the simplices whose vertices lie in D<sub>F<sub>L</sub></sub>(p)</td></tr></tbody></table>