# Convex and Concave Decomposition of Digitized Shapes Using Plane Probing and Visibility

Jacques-Olivier Lachaud, Tristan Roussillon

► To cite this version:

Jacques-Olivier Lachaud, Tristan Roussillon. Convex and Concave Decomposition of Digitized Shapes Using Plane Probing and Visibility. International Conference on Discrete Geometry and Mathematical Morphology, Wilkinson, M.H.F., Kosinka, J., Nov 2025, Groningen, Netherlands. pp.44-59, 10.1007/978-3-032-09544-2_4. hal-05373501

HAL Id: hal-05373501

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

Submitted on 19 Nov 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Convex and Concave Decomposition of Digitized Shapes Using Plane Probing and Visibility

Jacques-Olivier Lachaud<sup>1,2[0000-0003-4236-2133]</sup> and Tristan Roussillon<sup>2[0000-0003-2524-3685]</sup>

<sup>1</sup> Université Savoie Mont Blanc, CNRS, LAMA, F-73000 Chambéry, France
jacques-olivier.lachaud@univ-smb.fr

<sup>2</sup> Université Lyon, CNRS, INSA, LIRIS, F-69000 Lyon, France
tristan.roussillon@liris.cnrs.fr

**Abstract.** In this paper, we consider the geometrical analysis of oriented digital surfaces, which form the boundary of connected voxel sets. We present a method for the detection and reconstruction of its convex and concave parts. The proposed method composes two tools: the first one is a probing approach for the extraction of locally extremal points, the second one, based on the notion of visibility, joins some pairs of points whenever the straight segment between them stays sufficiently close to the input surface without crossing it. Finally, outer and inner candidate segments are assembled separately into facets, thus building polyhedral approximations of the local convex and concave zones.

**Keywords:** surface approximation · digital geometry · digital convexity

## 1 Introduction

Numerous studies focus on capturing the geometry of 3D shapes based on sampled data, whether in the form of point clouds, polygonal meshes, or digital surfaces. In this paper, we consider digital surfaces, defined as boundaries of connected voxel sets. They may be seen as closed, oriented, quadrangular meshes with vertices of integer coordinates.

Given a digital surface, we present a method for the detection and reconstruction of its convex and concave parts. The geometry of the convex hull is exactly recovered when the input data is digitally convex. This is therefore a first step towards a polygonal reconstruction that respects the convex and concave parts, which would be useful for many tasks in geometry processing.

Several methods could be considered for our purposes. Global approaches, e.g., based on the α-shape [2,11] or on a decimation strategy [5], are not expected to better capture the local geometry of the surface than local approaches. In the field of digital geometry, numerous works focus on the recognition of planar parts (see, e.g., [1]). In particular, one may use a plane-probing algorithm [10] to extract some tangent triangles. However, even when the input data is digitally convex, this approach is not able to recover all facets of the convex hull. Alternatively, we propose in this paper a probing algorithm to address the different problem of deciding whether a point is extremal or not.
In 2D, very good polygonal reconstructions of digital curves are obtained by local convex hull computations, done either explicitly [14,4,15] or implicitly [6,9,12]. We know only one attempt to extend this approach to 3D [13], but the proposed algorithm only works for a limited class of input. We go further in this direction, using the more recent notion of full convexity and tangency [7,8].

The outline is as follows. Section 2 defines the notion of convex and concave visibilities along a digital surface and establishes their links to convexity. Section 3 presents a probing approach to speed up the detection of convex and concave vertices. Section 4 explains the global reconstruction algorithm of convex and concave zones. Section 5 concludes the paper and offers some perspectives.

## 2 Convex and Concave Visibility

The input data is a set $K$ of $d$-dimensional cells, i.e. *voxels*. Our objective is to identify the convex and concave zones of the digital boundary of $K$, which is an oriented digital surface.<fnref n="3" /> We introduce the concept of *visibility* within exterior and interior parts of the digital surface, a kind of oriented alternative to the *tangency* to a digital set [8, Definition 4]. Remarkably, Theorem 2 shows that convex hull edges and facets of $K$ are indeed visible when $K$ is digitally convex.

*Background definitions.* There is a natural grid cell decomposition of the Euclidean space $\mathbb{R}^n$ with open unit cells (segments, squares, cubes, etc) such that their vertices are exactly the digital space $\mathbb{Z}^d$. We denote this cubical complex $C^d$, while its $k$-dimensional cells are denoted by $C_k^d$. For any subset $Y$ of $\mathbb{R}^d$, the *star* of $Y$ is $\text{Star}(Y) := \{c \in C^d, \bar{c} \cap Y \neq \emptyset\}$, where $\bar{c}$ is the topological closure of $c$. The *cover* of $Y$ is $\text{Cover}(Y) := \{c \in C^d, c \cap Y \neq \emptyset\}$. Obviously the cover of a set is included in its star. The 0-dimensional cells of $C^d$ are identified with $\mathbb{Z}^d$ and are called (lattice) points, or often *pointels* in the literature when thought of as vertices of higher dimensional cells. Given a subset $Y$ of $\mathbb{R}^d$, its *convex hull* is denoted by $\text{CvxH}(Y)$. The *set of extremal points* of a convex set $C$ is denoted by $\text{Extr}(C)$ (when $C$ is a polytope, they are often called *vertices*). For a grid cell $c$, which is a convex set, we have $\text{Extr}(c) = \{\bar{c} \cap \mathbb{Z}^d\}$. We recall one characterization of full convexity [7,8], and the related notion of tangency:

**Definition 1.** A digital set $X \subset \mathbb{Z}^d$ is digitally convex *iff* $\text{CvxH}(X) \cap \mathbb{Z}^d = X$. It is fully convex *iff* $\text{Star}(\text{CvxH}(X)) = \text{Star}(X)$. A digital subset $A \subset X \subset \mathbb{Z}^d$ is tangent to $X$ whenever $\text{Star}(\text{CvxH}(A)) \subset \text{Star}(X)$. The elements of $A$ are called cotangent in $X$.

Otherwise said, if we consider two pointels $A = \{p, q\}$ of the digital surface, with $X$ its set of pointels, they are cotangent in $X$ whenever the straight line segment $[pq]$ touches cells that are also touched by $X$. Tangency defines a kind of visibility, since $p$ and $q$ can “see” each other if and only if their line of sight

<footnote n="3">³ A more generic definition of oriented surface could be used [3], but the presentation is made easier if we consider the surface to be the boundary of a set of cells.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: Decomposition of the cellular grid $C^d$ into disjoint set of cells and illustration of tangency and visiblity. The input of set of voxels K are hatched as $\square$, and $C^d = \text{Outer}(K) \cup \text{Out}(K) \cup \text{Bd}(K) \cup \text{In}(K) \cup \text{Inner}(K)$. The set $X_K$ of 0-cells of $\text{Cl}(K)$ is decomposed into the inner pointels $I_K$ (the 0-cells of $\text{Inner}(K)$) and the boundary pointels $Z_K$ (the 0-cells of $\text{Bd}(K)$).</figcaption></figure>

stays close to the input digital surface. However this line of sight may cross the digital surface. Therefore we exploit the fact that we know where is the interior of the surface (the input set of interior voxels K), to keep this line of sights either exterior or interior. Convex vertices (resp. concave vertices) are visible to each other in the exterior (resp. interior) of the surface.

Let $K \subset C^d$ be the input set of interior voxels to the surface. For any subset $L$ of $C^d$, its (combinatorial) closure $\text{Cl}(L)$ is $\{c \in C^d, \text{Star}(c) \cap L \neq \emptyset\}$. For simplicity, the $k$-dimensional cells of a subset $L$ of $C^d$ are denoted by $L_k$. We denote by $X_K$ the 0-cells of $\text{Cl}(K)$. The digital set $X_K$ is subdivided into two disjoint subsets: the set of inner pointels $I_K$ is defined as $\{x \in X_K, \text{Star}(x) \subset \text{Cl}(K)\}$ and the set of boundary pointels $Z_K$ is $X_K \setminus I_K$. We subdivide the regular grid complex $C^d$ into several disjoint subsets (see Fig. 1)

$$ \text{Outer}(K) := \{c \in C^d, \text{Extr}(c) \subset (\mathbb{Z}^d \setminus X_K)\}, $$

$$ \text{Out}(K) := \{c \in C^d, \text{Extr}(c) \cap (\mathbb{Z}^d \setminus X_K) \neq \emptyset \text{ and } \text{Extr}(c) \cap (Z_K) \neq \emptyset\}, $$

$$ \text{Bd}(K) := \{c \in C^d, \text{Extr}(c) \subset Z_K\}, $$

$$ \text{In}(K) := \{c \in C^d, \text{Extr}(c) \cap (Z_K) \neq \emptyset \text{ and } \text{Extr}(c) \cap I_K \neq \emptyset\}, $$

$$ \text{Inner}(K) := \{c \in C^d, \text{Extr}(c) \subset I_K\}. $$

The analogy of $\text{Bd}(K)$ with the topological boundary is clear, since it represents the cells whose neighborhood touches K and the complementary of K.

*Visibility and local convexity/concavity.* As said above, tangency is not restricted enough to capture local convex edges and facets of a digital set. We introduce convex/concave visibility for this more specific purpose (see also Fig. 1).
**Definition 2.** The elements of a non-empty set of points $A := \{p_1, \dots, p_n\}$ of $Z_K$ are convex (resp. concave) $K$-visible if and only if Cover $(\mathrm{CvxH}(A)) \subset \mathrm{Out}(K) \cup \mathrm{Bd}(K)$ (resp. Cover $(\mathrm{CvxH}(A)) \subset \mathrm{In}(K) \cup \mathrm{Bd}(K)$).

The convex hull of the points visible from a point $x$ of $Z_K$ tells if $x$ is salient:

**Definition 3.** Let $x \in Z_K$. The point $x$ is a convex (resp. concave) corner iff exactly one cell of $K$ (resp. exactly one cell of $C_d^d \setminus K$) is incident to $x$. The convex visibility cone $V_K^{\mathrm{Out}}(x)$ of $x$ is the set of points $y$ of $Z_K$ such that $x, y$ are convex $K$-visible. The concave visibility cone $V_K^{\mathrm{In}}(x)$ of $x$ is the set of points $y$ of $Z_K$ such that $x, y$ are concave $K$-visible. The point $x$ is locally convex (resp. concave) on the boundary of $K$ iff $x \in \mathrm{Extr}(\mathrm{CvxH}(V_K^{\mathrm{Out}}(x)))$ and $x$ is a convex corner, resp. $x \in \mathrm{Extr}(\mathrm{CvxH}(V_K^{\mathrm{In}}(x)))$ and $x$ is a concave corner.

In the following, we focus on convex definitions and properties, but analogous results hold by replacing convex with concave. The requirement of being a corner is not limitative since when not satisfied the point cannot be locally convex. We assemble the local convex points into polyhedral objects as follows.

**Definition 4.** Let $A \subset Z_K$. The set $\mathrm{CvxH}(A)$ is called a locally convex face of $K$ whenever $\mathrm{CvxH}(A)$ is face of $\mathrm{CvxH}(\cup_{a \in A} V_K^{\mathrm{Out}}(a))$.

Lemma 2 (in Appendix A, page 13) shows that incident vertices, edges, etc, to a locally convex face are also locally convex. It is clear that the locally convex vertices and faces of $K$ form a disjoint set with the locally concave vertices and faces of $K$, since their extrema must belong to either the convex corners or the concave corners. The following theorem justifies this definition of local convexity, since it coincides with the convex hull of $Z_K$ when $X_K$ is fully convex.

**Theorem 1.** Let $K \subset C_d^d$ and $X_K$ fully convex. The vertices and the faces of $\mathrm{CvxH}(Z_K)$ are locally convex vertices and locally convex faces of $K$.

*Proof.* First it is clear that any vertex of $\mathrm{CvxH}(Z_K)$ must be a convex corner of $K$ and is also convex $K$-visible (belonging to $\mathrm{Bd}(K)$). We use here Theorem 2 (Appendix A, page 14), which tells that any vertex and face of $\mathrm{CvxH}(Z_K)$ are convex $K$-visible. Now, let $A \subset Z_K$ be such that $F := \mathrm{CvxH}(A)$ is a face of $\mathrm{CvxH}(Z_K)$. So $F \subset \partial\mathrm{CvxH}(Z_K)$ and any $a \in A$ is a vertex of $\mathrm{CvxH}(Z_K)$. Clearly $V_K^{\mathrm{Out}}(a) \subset Z_K$ so $\mathrm{CvxH}(V_K^{\mathrm{Out}}(a)) \subset \mathrm{CvxH}(Z_K)$. If $a$ is not locally convex, then it is a convex combination of points of $V_K^{\mathrm{Out}}(a) \subset \mathrm{CvxH}(Z_K)$, and it cannot be a vertex of $\mathrm{CvxH}(Z_K)$, a contradiction. Thus $a$ is locally convex.

The face $F = \mathrm{CvxH}(A)$ is a subset of each $\mathrm{CvxH}(V_K^{\mathrm{Out}}(a))$ for $a \in A$ (since any subset of its vertices are convex visible according to Theorem 2). So $F \subset \cup_{a \in A} \mathrm{CvxH}(V_K^{\mathrm{Out}}(a)) \subset \mathrm{CvxH}(\cup_{a \in A} V_K^{\mathrm{Out}}(a))$.

If we assume that there is a $y \in F$ with $y \in \mathrm{int}(\mathrm{CvxH}(\cup_{a \in A} V_K^{\mathrm{Out}}(a)))$. Then it follows that $y \in \mathrm{int}(\mathrm{CvxH}(Z_K))$ since any point of $V_K^{\mathrm{Out}}(a)$ belongs to $Z_K$. But this is a contradiction to $F$ being a face of $\mathrm{CvxH}(Z_K)$. So either $y \in \partial\mathrm{CvxH}(\cup_{a \in A} V_K^{\mathrm{Out}}(a))$ or $y$ is outside this convex set. The second case is impossible since $F \subset \mathrm{CvxH}(\cup_{a \in A} V_K^{\mathrm{Out}}(a))$ as shown above. So $F$ lies in the
<figure><img src="image_3.png" /><figcaption>Fig. 2: Z is the set of points of a digital surface, denoted by $Z_K$ in Section 2 and shown in gray colors in (a). $CvxH(Z)$ is shown in (b). An initial tetrahedron is shown in (c). In this case, the algorithm finds a point alignment (in red) after one update and the starting point is thus labelled as not extremal. An execution from a vertex of $CvxH(Z)$ is shown from (e) to (h). The base facet of the tetrahedron aligns with a supporting plane after eight iterations and the starting point is labelled as locally extremal (Theorem 3).</figcaption></figure>

boundary of $CvxH(\cup_{a \in A} V_K^{\text{Out}}(a))$. A convex set lying on the boundary of a convex set $Y$ such that each of its extremal points are extremal points of $Y$ is defined by the equation of $Y$. So $F$ is a locally convex face of $K$. $\square$

Note that we can prove analogously that when the complement $K'$ of $K$ induces a fully convex set $X_{K'}$, then the vertices and faces of $CvxH(Z_{K'})$ are locally concave in $K'$. The converse of Theorem 1 is also reachable, but we leave it for a further extension because of space constraints.

## 3 Extremal Point Detection

In this section, we consider a digital set $Z \subset \mathbb{Z}^3$. The dimension of the space is restricted to $d=3$ to better align with the illustrations, but it can be extended to arbitrary $d$ without difficulty. A point $z \in Z$ is extremal if and only if $z \in \text{Extr}(\text{CvxH}(Z))$. In addition, $z \in Z$ is locally extremal if and only if it is extremal for the convex hull of some non-empty subset $Z' \subseteq Z$ containing $z$.

We propose a probing algorithm that labels a point $z \in Z$ as locally extremal or not extremal. Informally, the algorithm starts with an initial tetrahedron. The apex is placed at $z$ and the opposite triangular face stands below it. The triangle is then iteratively updated with elementary vector operations using only queries “is $x$ in $Z$?” (see Fig. 2). The algorithm stops if it detects a point alignment that makes $z$ not extremal or if the normal vector to the triangle gives a direction for which $z$ is extremal with respect to the visited points, thus locally extremal. It is very similar to the H-algorithm [10] but solves a different problem.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Illustration of Definition 5 (a) and Definition 7 (b-d). Points in (resp. not in) Z are depicted with black (resp. white) disks. A valid tetrahedron is shown in (a). Among the six possible operations, depicted with crosses in (b), a valid one is shown in (c). Having applied this operation, the resulting tetrahedron is shown in (d). One can check that it is valid.</figcaption></figure>

In more details, by translation, we assume with no loss of generality that the point to consider is the origin **0**. The tetrahedron is then conveniently represented by a 3 × 3 matrix **M** with integer coefficients, where the three column vectors are denoted by **m**₁, **m**₂, **m**₃. See Fig. 3 (a) and Definition 5.

**Definition 5 (Fig. 3 (a)).** Let $Z \subset \mathbb{Z}^3$ be a digital set containing **0**. A tetrahedron is a matrix $\mathbf{M} \in \mathbb{Z}^{3 \times 3}$, which is valid if

$$-\mathbf{m}_1, -\mathbf{m}_2, -\mathbf{m}_3 \in Z, \quad \mathbf{m}_1, \mathbf{m}_2, \mathbf{m}_3 \notin Z, \quad \det(\mathbf{M}) = 1. \quad (1)$$

The update of the tetrahedron is conveniently represented by a 3 × 3 matrix with integer coefficients taken from a set of six matrices with determinant 1:

**Definition 6.** Let $\Sigma$ be the set of all permutations over $\{1, 2, 3\}$. For a permutation $\sigma \in \Sigma$, let $U_\sigma$ be a 3 × 3 matrix having −1 at the intersection between the $\sigma(1)$-th column and the $\sigma(2)$-th row and the same entries as **I**, the 3 × 3 identity matrix, elsewhere. Let $\cup$ be the set $\{U_\sigma | \sigma \in \Sigma\}$.

Note that computing $MU_\sigma$ amounts to subtracting the $\sigma(2)$-th column of $\mathbf{M}$ to the $\sigma(1)$-th column. As shown in Fig. 3 (b), the six possible results (determined by the six permutations $\sigma \in \Sigma$) form the vertices of an hexagon around the origin. Any such operation is possible if the resulting tetrahedron is valid.

**Definition 7 (Fig. 3 (c-d)).** Let $Z \subset \mathbb{Z}^3$ be a digital set containing **0** and let $\mathbf{M} \in \mathbb{Z}^{3 \times 3}$ be a valid tetrahedron. An operation is a function $f: \mathbb{Z}^{3 \times 3} \to \mathbb{Z}^{3 \times 3}$ such that given $\mathbf{M}' = f(\mathbf{M})$, there exists a matrix $U_\sigma \in \cup$ that satisfies $\mathbf{M}' = MU_\sigma$. Moreover, $f$ is valid if $\mathbf{M}'$ is valid, i.e., if

$$-\mathbf{m}_{\sigma(1)} + \mathbf{m}_{\sigma(2)} \in Z, \quad \mathbf{m}_{\sigma(1)} - \mathbf{m}_{\sigma(2)} \notin Z. \quad (2)$$

The algorithms halts if there is no valid operation, but also whenever two points symmetric with respect to **0** are in Z. Otherwise it continues to probe:

**Definition 8.** Let $Z \subset \mathbb{Z}^3$ be a digital set containing **0** and let $\mathbf{M} \in \mathbb{Z}^{3 \times 3}$ be a valid tetrahedron. The state $\text{STATE}(\mathbf{M})$ of $\mathbf{M}$ is defined as:
<figure><img src="image_5.png" /></figure>

Finally, our algorithm `IsEXTREMAL` reads as follows:

**Input:** a digital set Z containing **0**, a valid tetrahedron **M**.

**while** `STATE(M) = PROBING do`

Find a valid operation *f* and apply it: $M \leftarrow f(M)$

**return** `STATE(M)`

The initial tetrahedron is usually a (positively oriented) orthonormal basis. By rotations, we can assume it is **I** with no loss of generality.

If the algorithm terminates, the output is either `NO` or `YES`. In the former case, **0** is not extremal because it lies in a segment joining two other points of Z. In the latter case, **0** is locally extremal and more precisely, extremal with respect to the set of visited points. We can show that the algorithm indeed terminates for any finite Z and that it returns `YES` if **0** is a vertex of `CvxH(Z)` (see Theorem 3 and Theorem 4 in Appendix B, page 14).

Note that finding a valid operation is quite easy: we have to check if there exists $\sigma \in \Sigma$ such that $-\mathbf{m}_{\sigma(1)} + \mathbf{m}_{\sigma(2)} \in Z$ and $\mathbf{m}_{\sigma(1)} - \mathbf{m}_{\sigma(2)} \notin Z$. This can be done by at most six calls to a set-membership predicate. There are usually several valid operations. The theoretical termination results presented in the Appendix do not depend on a particular choice. In some cases, however, the way we choose the operations may change the final answer. In the experiments, we follow the approach previously used in plane-probing algorithms: we use an in-sphere criterion and, if several points are in a cospherical position, we resort to a lexicographic order (see H-algorithm [10]).

Algorithm `IsEXTREMAL` provides in practice a fast way to discard a large amount of non-extremal points, especially along digitizations of smooth surfaces. As an example, the ellipsoid $x^2 + 25y^2 + 25z^2 - 90 \le 0$ is digitized at grid steps 0.5, 0.1, 0.05 and 0.01 to obtain four sets of voxels. For each one, we have processed the set of boundary pointels Z after surface tracking. The results are reported in the table below, where $n_c$ denotes the number of corners, i.e., points $\mathbf{z} \in Z$ such that $\forall k \in \{1, 2, 3\}, \mathbf{z} \pm \mathbf{e}_k \in Z, \mathbf{z} \mp \mathbf{e}_k \notin Z$, from where the algorithm is initialized, and $n_e$ is the number of points detected as locally extremal. Note that $n_c \ge n_e$ by definition and $n_e \ge |\text{CvxH}(Z)|$ by Theorem 3. Experimentally, $n_e$ is equal or slightly greater than $|\text{CvxH}(Z)|$, while it is far less than $n_c$.

<table><thead><tr><th>grid step</th><th>|Z|</th><th>n<sub>c</sub></th><th>n<sub>e</sub></th><th>|CvxH(Z)|</th></tr></thead><tbody><tr><td>0.5</td><td>984</td><td>112</td><td>112</td><td>112</td></tr><tr><td>0.1</td><td>24.808</td><td>2.032</td><td>1.128</td><td>1.128</td></tr><tr><td>0.05</td><td>99.448</td><td>7.784</td><td>3.064</td><td>3.064</td></tr><tr><td>0.01</td><td>2.488.104</td><td>186.664</td><td>33.864</td><td>33.784</td></tr></tbody></table>
**Algorithm 1:** Given the interior voxels *K*, returns a surface meshing of the convex zones as a pair of vertices and faces joining them.

**Function** `BUILDLOCALLYCONVEXZONES`(**In K**: subset of $C_d^d$) : Mesh;
**begin**
  $E \leftarrow \emptyset$; // (I)
  $Z \leftarrow \text{Cl}(K) \cap \mathbb{Z}^d$;
  **foreach** convex corner $z$ of $K$ **do**
    $M \leftarrow \text{GETVALIDTETRAHEDRON}(z, Z)$;
    **if** `IsEXTREMAL`($M$, $Z-z$) **then** $E \leftarrow E \cup \{z\}$;
    $V \leftarrow \text{GETVISIBILITYPAIRS}(K, E)$; // (II)
    $(C_v, C_e) \leftarrow \text{GETLOCALLYCONVEXVERTICESANDEDGES}(E, V)$; // (III)
    $C_f \leftarrow \text{GETLOCALLYCONVEXFACETS}(C_v, C_e, V)$; // (IV)
  **return** $(C_v, C_f)$
**end**

**Algorithm 2:** Given the interior voxels *K* and extremal convex corners *E*, returns all the visible *K*-convex pairs.

**Function** `GETVISIBILITYPAIRS`(**In K**: voxels, **In E**: points) : set of
(point,point);
**begin**
  $R \leftarrow \emptyset$;
  **foreach** $(p, q) \in E \times E$ **do**
    **if** $p \neq q$ and Cover($CvxH(\{p, q\}) \subset Bd(K) \cup Out(K)$) **then**
      $R \leftarrow R \cup \{(p, q)\}$;
  **return** $R$

# 4 Reconstruction of Locally Convex and Concave Zones

*General presentation.* Algorithm 1 provides the general algorithm for reconstructing the locally convex zones along the boundary of a set of interior voxels *K*. It is composed of 4 stages:

(I) Filtering the convex corners with the probing algorithm `IsEXTREMAL`

(II) Computing the convex visibility between these points (Algorithm 2)

(III) Extracting the locally convex vertices and edges among them (Algorithm 3)

(IV) Extracting the locally convex facets between them (Algorithm 4)

Computing the locally concave zones is a completely symmetric algorithm and is not detailed here (just starts from concave corners). Note that the true C++ implementation uses indices instead of sets to speed up computations.

*Computational considerations.* Note that more than 95% of the computation time is related to stage (II), the computation of all the visible pairs. Its complexity grows quadratically with the number of candidate extremal points. This is why it is crucial to filter the convex corners as most as possible and this is
**Algorithm 3:** Given points *E* and their visibility *V*, filters them to return the locally convex vertices and edges.

**Function GETLOCALLYCONVEXVERTICESANDEDGES( In E:** points, **In V:** set of (point,point) ) : (points, set of (point,point)) ;

**Var** *M*: map point to bool, *N*: map (point,point) to bool;

begin

S ← ∅ ; // set of candidate convex edges

foreach p ∈ E do M[p] ← true;

foreach (p, q) ∈ V do N[(p, q)] ← false;

foreach p ∈ E do

Q ← CONVEXHULL({p} ∪ {q ∈ E, (p, q) ∈ V });

if Q is not full dimensional or p ∉ Extr (Q) then

M[p] ← false;

continue;

foreach facet f = (p₀, ..., pₖ₋₁) of Q do

if ∃i ∈ {0, ..., k − 1}, pᵢ = p then

S ← S ∪ {(p, pᵢ₋₁)} ∪ {(p, pᵢ₊₁)} ; // indices modulo k

foreach (p, q) ∈ V do

if (p, q) ∉ S or (q, p) ∉ S then continue;

L ← {r ∈ E, (p, r) ∈ V and (p, r) ∈ S and (r, p) ∈ S};

L ← L ∪ {r ∈ E, (q, r) ∈ V and (q, r) ∈ S and (r, q) ∈ S};

Q ← CONVEXHULL(L);

if (p, q) is an edge of Q then N[(p, q)] ← true;

C_v ← {p ∈ E, M[p] = true};

C_e ← {(p, q) ∈ V, N[(p, q)] = true};

return (C_v, C_e)

exactly what does the probing algorithm ISEXTREMAL. Furthermore, many of
the visibility tests are done between candidate points that are very far away from
each other and probably unrelated. Instead of using a heuristic (like assuming
that points further away from a given distance are not visible), we use a coarse-
to-fine pyramid approach to check covering and tangency, that can be proven to
be exact. We do not have the place to develop it here, but we achieve between
10× to 200× speed-up with this technique.

*Results and timings.* We have tested our method on a large amount of digital surfaces. Some results are shown in Fig. 4 and Table 1 (computations made on a Macbook Pro, apple M2 Max, 64 Go RAM). The convex and concave parts are accurately detected, and their polyhedral reconstruction closely matches the convex hull in the most salient regions as shown in Fig. 4 (d) and (g). Remarkably, the columns *n*<sub>e</sub> and *n*<sub>v</sub> are identical, which means that the probing algorithm ISEXTREMAL identifies all the locally convex and concave vertices. Thanks to algorithm ISEXTREMAL and the above-mentioned additional optimization tricks, our method achieves low running times relative to the difficulty
**Algorithm 4:** Given the locally convex vertices $C_v$ and edges $C_e$, the visibility $V$, returns the locally convex facets joining them.

**Function GETLOCALLYCONVEXFACETS( In $C_v$: points, In $C_e$, V: set of (point,point) ): set of facets;**
**begin**

$F \leftarrow \emptyset$;
**foreach** $p \in C_v$ **do**
  $Q \leftarrow \text{CONVEXHULL}(\{p\} \cup \{q \in C_v, (p, q) \in V\})$;
  **foreach** facet $f \in Q$ **do**
    **if** $p \in \text{Extr}(f)$ and every edge of $f$ is in $C_e$ **then**
      **//** Some faces may be present several times
      $f' \leftarrow \text{LOWESTCIRCULARPERMUTATION}(f)$;
      $F \leftarrow F \cup \{f'\}$; 
      **//** (3, 1, 6) $\rightarrow$ (1, 6, 3)
  **return** $F$

<table><caption>Table 1: For each digital surface of Fig. 4, we provide the overall running time together with the number of input points (|Z_k|), corners (n_c), extremal points (n_e), locally convex/concave points and faces (n_v and n_f).</caption><thead><tr><th rowspan="2">shape</th><th rowspan="2">|Z<sub>k</sub>|</th><th colspan="4">convex zones</th><th colspan="4">concave zones</th><th rowspan="2">time (s)</th></tr><tr><th>n<sub>c</sub></th><th>n<sub>e</sub></th><th>n<sub>v</sub></th><th>n<sub>f</sub></th><th>n<sub>c</sub></th><th>n<sub>e</sub></th><th>n<sub>v</sub></th><th>n<sub>f</sub></th></tr></thead><tbody><tr><td>twospheres</td><td>21.758</td><td>3.258</td><td>1.580</td><td>1.580</td><td>1.339</td><td>2.664</td><td>0</td><td>0</td><td>0</td><td>5</td></tr><tr><td>torusknot</td><td>96.622</td><td>15.196</td><td>2.930</td><td>2.930</td><td>2.765</td><td>13.347</td><td>5</td><td>5</td><td>0</td><td>31</td></tr><tr><td>sharpsphere</td><td>119.846</td><td>16.715</td><td>3.111</td><td>3.111</td><td>2.546</td><td>15.011</td><td>412</td><td>412</td><td>271</td><td>40</td></tr><tr><td>goursat</td><td>104.984</td><td>7.776</td><td>2.160</td><td>2.160</td><td>2.408</td><td>7.376</td><td>288</td><td>288</td><td>246</td><td>24</td></tr><tr><td>leopold</td><td>144.440</td><td>33.672</td><td>1.664</td><td>1.664</td><td>1.538</td><td>32.256</td><td>856</td><td>856</td><td>744</td><td>19</td></tr></tbody></table>

of the problem. Note that the concave parts are located inside the volume and are thus not visible on Fig. 4 (c), (e) and (h). Many parts are of course neither convex nor concave and addressing them remains a key direction for future work.

# 5 Conclusion

In this paper we have proposed an original definition of local convexity and con-cavity along a digital surface. The definition, based on the notion of visibility, is sound in the sense that it matches the convex hull when the digital surface is digitally (fully) convex. Computing local convexity/concavity requires the iden-tification of extremal points. We have proposed a fast probing-based algorithm that quickly prune corners to retain extremal points. The computation of visi-bilities between extremal points is thus greatly reduced. Locally convex/concave edges and faces are then quickly determined with local convex hull computa-tions. Experiments illustrate that the decomposition of the digital surface into convex and concave zones is exact and not approximate.
<figure><img src="image_6.png" /><figcaption>Fig. 4: Reconstructions of twospheres, torusknot, sharpsphere, goursat and leopold are respectively shown in (a), (b), (c), (d)-(f) and (g)-(i). The digital surface, the convex hull, the convex and concave parts are respectively colored in grey, yellow, blue and pink. Statistics and timings are collected in Table 1.</figcaption></figure>

One of the limitation of the work is the computation of visibility between all pairs of extremal points. A pyramid approach is used to speed up these computations, but computing visibility remains the bottleneck of the method. We are currently investigating “compatibility criteria” between extremal points to prune further the number of tested pairs. Our final objective remains the full polyhedral decomposition of the digital surface into convex, concave, and saddle parts. A plane-probling variant could be able to detect potential saddle zones. It remains to understand how to combine this information to triangulate these zones in a deterministic way.

**Acknowledgments.** This work is partially supported by the French National Research Agency within the StableProxies project (ANR-22-CE46-0006).
References

1. Brimkov, V., Coeurjolly, D., Klette, R.: Digital planarity – a review. Discrete Applied Mathematics **155**(4), 468–495 (2007)

2. Edelsbrunner, H., Mücke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graph. **13**(1), 43–72 (Jan 1994). https://doi.org/10.1145/174462.156635

3. Herman, G.T.: Oriented surfaces in digital spaces. CVGIP: Graphical models and image processing **55**(5), 381–396 (1993)

4. Klette, G.: Recursive calculation of relative convex hulls. In: Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P. (eds.) Discrete Geometry for Computer Imagery. pp. 260–271. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

5. Kobbelt, L., Campagna, S., Seidel, H.P.: A general framework for mesh decimation. In: Proceedings of the Graphics Interface 1998 Conference, June 18-20, 1998, Vancouver, BC, Canada. pp. 43–50 (June 1998), http://graphicsinterface.org/wp-content/uploads/gi1998-6.pdf

6. Lachaud, J.O., Provençal, X.: Two linear-time algorithms for computing the minimum length polygon of a digital contour. Discrete Applied Mathematics **159**(18), 2229–2250 (2011). https://doi.org/10.1016/j.dam.2011.08.002

7. Lachaud, J.O.: An alternative definition for digital convexity. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) Discrete Geometry and Mathematical Morphology - First International Joint Conference, DGMM 2021, Uppsala, Sweden, May 24-27, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12708, pp. 269–282. Springer (2021). https://doi.org/10.1007/978-3-030-76657-3_19

8. Lachaud, J.O.: An alternative definition for digital convexity. J. Math. Imaging Vis. **64**(7), 718–735 (2022). https://doi.org/10.1007/s10851-022-01076-0

9. Lachaud, J.O., Provençal, X.: Dynamic minimum length polygon. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds.) Combinatorial Image Analysis. pp. 208–221. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

10. Lachaud, J.O., Provençal, X., Roussillon, T.: Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital Plane. Journal of Mathematical Imaging and Vision **59**(1), 23 – 39 (Sep 2017). https://doi.org/10.1007/s10851-017-0704-x

11. Portaneri, C., Rouxel-Labbé, M., Hemmer, M., Cohen-Steiner, D., Alliez, P.: Alpha wrapping with an offset. ACM Transactions on Graphics (TOG) **41**(4), 1–22 (2022)

12. Roussillon, T., Sivignon, I.: Faithful polygonal representation of the convex and concave parts of a digital curve. Pattern Recognition **44**(10-11), 2693–2700 (Nov 2011), https://hal.archives-ouvertes.fr/hal-00643573

13. Schulz, H.: Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets. Discrete Applied Mathematics **157**(16), 3485–3493 (2009). https://doi.org/10.1016/j.dam.2009.04.008, combinatorial Approach to Image Analysis

14. Sklansky, J., Chazin, R.L., Hansen, B.J.: Minimum-perimeter polygons of digitized silhouettes. IEEE Transactions on Computers **21**(3), 260–268 (1972)

15. Wiederhold, P.: Computing the minimal perimeter polygon for sets of rectangular tiles based on visibility cones. Journal of Mathematical Imaging and Vision **66**(5), 873–903 (2024). https://doi.org/10.1007/s10851-024-01203-z
A Properties related to visibility

We gather here some properties related to visibility and necessary to give some
theoretical guarantees for local convexity.

We first state without proof a few elementary properties of the sets defined
in Section 2.

**Lemma 1.** For any $K \subset C_d^d$, the set of cells $C^d$ is the disjoint union of
Outer($K$), Out($K$), Bd($K$), In($K$), Inner($K$). Furthermore Outer($K$), Bd($K$)
and Inner($K$) are closed. Out($K$) and In($K$) are open.

The next lemma tells that the definition of locally convex face is sound, i.e.,
all faces incident to a locally convex face are also locally convex.

**Lemma 2.** For any $\emptyset \neq A' \subset A \subset Z_K$, if $\text{CvxH}(A)$ is a locally convex face of $K$, then $\text{CvxH}(A')$ is a locally convex face of $K$ too.

*Proof.* Assume $\text{CvxH}(A)$ is a locally convex face of $K$. Let $C := \text{CvxH}(\cup_{a \in A} \text{V}_K^{\text{Out}}(a))$ and $C' := \text{CvxH}(\cup_{a \in A'} \text{V}_K^{\text{Out}}(a))$. We have $\text{CvxH}(A') \subset C'$. If $\text{CvxH}(A') \not\subset \partial C'$ then $\text{CvxH}(A') \cap \text{int}(C') \neq \emptyset$ (it must cross its interior). But obviously $C' \subset C$, which implies $\text{int}(C') \subset \text{int}(C)$. It follows that $\text{CvxH}(A') \cap \text{int}(C) \neq \emptyset$. This contradicts $\text{CvxH}(A') \subset \text{CvxH}(A) \subset \partial C$ ($\text{CvxH}(A)$ is a face of $C$) since $\partial C$ and $\text{int}(C)$ are disjoint. $\square$

We show below that the pointels $I_K$ are indeed interior points as they belong
to the interior of the convex hull of $X_K$.

**Lemma 3.** Let $K \subset C_d^d$ non-empty. Then $X_K$ and $Z_K$ have the same convex hull (i.e. $\text{CvxH}(Z_K) = \text{CvxH}(X_K)$). Furthermore $\text{CvxH}(Z_K)$ is full dimensional, and $I_K$ belongs to $\text{int}(\text{CvxH}(Z_K))$, which is not empty.

*Proof.* Since the convex hull is an increasing operator and $Z_K \subset X_K$, we have $\text{CvxH}(Z_K) \subset \text{CvxH}(X_K)$. To show the reverse inclusion, $X_K$ being finite, the extremal points $V$ of $\text{CvxH}(X_K)$ form a subset of $X_K$. Let $v \in V$. Let $i$ be an arbitrary direction. If $v + e_i \in X_K$ and $v - e_i \in X_K$, it means that $v$ is a linear combination of two points of $X_K$ and cannot be an extremal point of $\text{CvxH}(X_K)$. So either $v^+ := v + e_i$ or $v^- := v - e_i$ or both are not in $X_K$. Assume it is $v^+$ wlog. So the 1-cell $c^+$ of boundary $\{v, v^+\}$ must be in Out($K$) and $v$ must belong to $Z_K$. Therefore, $V \subset Z_K$ and we conclude that $\text{CvxH}(X_K) = \text{CvxH}(V) \subset \text{CvxH}(Z_K)$.

Besides, if $x \in I_K$, it follows that all neighbors $N := (x \pm e_i)_{i \in \{1, \dots, d\}}$ are in $X_K$ too. Since $\text{CvxH}(N)$ is full dimensional, $x \in \text{int}(\text{CvxH}(N)) \subset \text{int}(\text{CvxH}(X_K)) = \text{int}(\text{CvxH}(Z_K))$. $\square$

It is quite intuitive that the boundary of the convex hull of a digitally convex
digital set should be close to the boundary points of this digital set. However this
result if false if we consider classical digital convexity. For instance just pick two
points separated by a primitive lattice vector of $\infty$-norm strictly greater than 1.
The full convexity is thus necessary in the following property:
**Theorem 2.** Let $K \subset C_d^d$. If $X_K$ is fully convex, then Cover $(\partial \mathrm{CvxH}(Z_K)) \subset \mathrm{Out}(K) \cup \mathrm{Bd}(K)$. Hence any edge or facet of $\mathrm{CvxH}(Z_K)$ are convex $K$-visible.

*Proof.* Let $F$ be any facet of $\mathrm{CvxH}(X_K)$, which is also a facet of $\mathrm{CvxH}(Z_K)$ by Lemma 3. Hence $F \subset \partial \mathrm{CvxH}(Z_K)$. Let $c \in \mathrm{Cover}(F)$, so $c \cap F \neq \emptyset$, and let $y \in c \cap F$. Let $V := \mathrm{Extr}(c)$ be the vertices of $c$.

Since $y \in F$, we have $y \in \partial \mathrm{CvxH}(Z_K) = \mathrm{CvxH}(Z_K) = \mathrm{CvxH}(X_K)$. So $\mathrm{Star}(y) = \{c\} \subset \mathrm{Star}(\mathrm{CvxH}(X_K)) = \mathrm{Star}(X_K)$, the latter equality coming from full convexity of $X_K$. At least one of the extremal point of $c$ must belong to $X_K$, and $c$ cannot be in $\mathrm{Outer}(K)$.

We show now that no point of $V$ can be in $I_K$. Assume there is some $x \in V$ with $x \in I_K$. Then $c \in \mathrm{Inner}(K)$ or $c \in \mathrm{In}(K)$. If $c \in \mathrm{Inner}(K)$, then $V \subset I_K$. By Lemma 3, we know that $I_K \subset \mathrm{int}(\mathrm{CvxH}(Z_K))$. Hence $\mathrm{CvxH}(V) \subset \mathrm{CvxH}(\mathrm{int}(\mathrm{CvxH}(Z_K))) = \mathrm{int}(\mathrm{CvxH}(Z_K))$. It follows that $c$ lies entirely in the interior of $\mathrm{CvxH}(Z_K)$, which is a contradiction with $y \in \partial \mathrm{CvxH}(Z_K)$.

If $c \in \mathrm{In}(K)$, then $\mathrm{Star}(c) \subset \mathrm{In}(K)$ since $\mathrm{In}(K)$ is open (see Lemma 1). Now $\mathrm{In}(K) \subset \mathrm{Cl}(K)$. It follows that:

$$ \begin{align*} & \mathrm{CvxH}(\mathrm{Star}(c)) \subset \mathrm{CvxH}(\mathrm{Cl}(K)) = \mathrm{CvxH}(Z_K) \quad (\mathrm{CvxH}(\cdot) \text{ is increasing}) \\ \Rightarrow \quad & \mathrm{int}(\mathrm{CvxH}(\mathrm{Star}(c))) \subset \mathrm{int}(\mathrm{CvxH}(Z_K)) \quad (\text{Taking their interior}) \\ \Rightarrow \quad & \mathrm{CvxH}(\mathrm{Star}(c)) \subset \mathrm{int}(\mathrm{CvxH}(Z_K)) \quad (\text{since } \mathrm{Star}(c) \text{ is open}) \\ \Rightarrow \quad & c \subset \mathrm{int}(\mathrm{CvxH}(Z_K)) \quad (\text{since } c \in \mathrm{Star}(c)) \end{align*} $$

There is again a contradiction since $y \in c$ and $y \in \partial \mathrm{CvxH}(Z_K)$.

We have just shown that $\mathrm{Cover}(F) \subset (C^d \setminus (\mathrm{Outer}(K) \cup \mathrm{In}(K) \cup \mathrm{Inner}(K)))$, hence $\mathrm{Cover}(F) \subset (\mathrm{Out}(K) \cup \mathrm{Bd}(K))$ by Lemma 1. Furthermore, $\partial \mathrm{CvxH}(Z_K)$ is the union of finitely many convex facets ($F_j$). Thus $\mathrm{Cover}(\partial \mathrm{CvxH}(Z)) = \mathrm{Cover}(\cup_j F_j) = \cup_j \mathrm{Cover}(F_j) \subset \mathrm{Out}(K) \cup \mathrm{Bd}(K)$. $\square$

It immediately implies the tangency of convex hull facets.

**Corollary 1.** Let $K \subset C_d^d$. If $X_K$ is fully convex, then the vertices of any facet of $\mathrm{CvxH}(Z_K)$ are cotangent in $Z_K$ (i.e. $\mathrm{Star}(\partial \mathrm{CvxH}(Z_K)) \subset \mathrm{Star}(Z_K)$).

*Proof.* It suffices to notice than $\mathrm{Star}(Z_K) = \mathrm{Out}(K) \cup \mathrm{Bd}(K) \cup \mathrm{In}(K)$. $\square$

## B Properties related to probing

In this section, we focus on the termination of algorithm `IsEXTREMAL`. We first show that it returns `YES` if `0` is a vertex of $\mathrm{CvxH}(Z)$ and then show that it terminates for any finite $Z$, whatever the relative position of `0`.

**Theorem 3.** Let $Z \subset \mathbb{Z}^3$ be a digital set containing `0` and let `I` be a valid initial tetrahedron. If `0` is a vertex of $\mathrm{CvxH}(Z)$, Algorithm `IsEXTREMAL` returns `YES` after a number of iterations bounded from above by $2\sqrt{3}$ times the total area of the facets of $\mathrm{CvxH}(Z)$ incident to `0`.
**Proof.** Every facet $\mathcal{F}$ of CvxH($Z$) incident to $0$ has an orthogonal vector $\mathbf{v}_{\mathcal{F}} \in \mathbb{Z}^3$ and an area $a_{\mathcal{F}}$ that satisfy $\|\mathbf{v}_{\mathcal{F}}\|_2 \le 2a_{\mathcal{F}}$. Denoting by $\mathbf{v}$ (resp. $a$), the sum of $\mathbf{v}_{\mathcal{F}}$ (resp. $a_{\mathcal{F}}$) over all facets $\mathcal{F}$ incident to $0$, we have again $\|\mathbf{v}\|_2 \le 2a$. Therefore, $\|\mathbf{v}\|_1 \le \sqrt{3}\|\mathbf{v}\|_2 \le 2\sqrt{3}a$.

We denote by $\mathcal{H}(\mathbf{v})$ the half-space $\{\mathbf{x} \in \mathbb{R}^3 | \mathbf{x} \cdot \mathbf{v} < 0\}$. By construction, $\mathcal{H}(\mathbf{v})$ contains CvxH($Z$) $\setminus \{0\}$, therefore $Z \setminus \{0\}$. Note that two nonzero points $\mathbf{x}, -\mathbf{x}$ cannot be both in $\mathcal{H}(\mathbf{v})$, therefore cannot be both in $Z$. Consequently, algorithm ISEXTREMAL, if it terminates, cannot return NO but only YES in that case.

The algorithm will stop before crossing the boundary of $\mathcal{H}(\mathbf{v})$, while the maximum number of iterations to reach it can be determined through a decreasing sequence of integers (see also [10, Lemma 5, Lemma 6, Theorem 1]).

More formally, we denote by $\mathbf{M}$ the current tetrahedron and $c_1, c_2, c_3$ the entries of $\mathbf{v}^\top \mathbf{M}$. At initialization, $\mathbf{M} = \mathbf{I}$ and $c_1, c_2, c_3$ are just the coordinates of $\mathbf{v}$. Since $\mathbf{M}$ is a valid tetrahedron (1), we have for all $k \in \{1, 2, 3\}$, $-\mathbf{m}_k \in Z$, which implies $-\mathbf{m}_k \in \mathcal{H}(\mathbf{v})$. Therefore, $(-\mathbf{m}_k) \cdot \mathbf{v} < 0$ and, equivalently, $c_k > 0$.

If there is a valid operation $f$, we denote by $\mathbf{M}' := f(\mathbf{M})$ the new tetrahedron. There is a matrix $U_\sigma$ such that $\mathbf{M}' = \mathbf{M}U_\sigma$ and by permutations, we assume with no loss of generality that $\sigma$ is the identity. We thus have $\mathbf{v}^\top \mathbf{M}' = (c_1 - c_2, c_2, c_3)$. In addition, since $f$ is valid (2), we have $-\mathbf{m}_1 + \mathbf{m}_2 \in Z$, which implies $-\mathbf{m}_1 + \mathbf{m}_2 \in \mathcal{H}(\mathbf{v})$. Therefore, $(-\mathbf{m}_1 + \mathbf{m}_2) \cdot \mathbf{v} < 0$ and, equivalently, $c_2 - c_1 > 0$. In other words, the entries $c_1, c_2, c_3$ are strictly positive integers and their sum is strictly decreasing from $\|\mathbf{v}\|_1$ at every iteration. As a consequence, the number of iterations is less than $\|\mathbf{v}\|_1$, which concludes the proof. $\square$

**Theorem 4.** Let $Z \subset \mathbb{Z}^3$ be a finite digital set containing $0$ and let $\mathbf{M}$ be a valid initial tetrahedron. Algorithm ISEXTREMAL terminates after a finite number of iterations.

**Proof.** Let $C_{\mathbf{M}}$ be the cone formed by all convex combinations of $-\mathbf{m}_1, -\mathbf{m}_2, -\mathbf{m}_3$, i.e., $\{-\sum_{k \in \{1, 2, 3\}} c_k \mathbf{m}_k | c_1, c_2, c_3 \in \mathbb{R}_{\ge 0}\}$. If there is a valid operation $f$, we denote by $\mathbf{M}' := f(\mathbf{M})$ the new tetrahedron. There is a matrix $U_\sigma$ such that $\mathbf{M}' = \mathbf{M}U_\sigma$ and by permutations, we assume with no loss of generality that $\sigma$ is the identity.

For all $\mathbf{x} \in C_{\mathbf{M}}$, we have by definition $\mathbf{x} = -c_1\mathbf{m}_1 - c_2\mathbf{m}_2 - c_3\mathbf{m}_3$ with nonnegative $c_1, c_2, c_3$. We can write also

$$ 
\begin{aligned}
\mathbf{x} &= -c'_1 \mathbf{m}'_1 - c'_2 \mathbf{m}'_2 - c'_3 \mathbf{m}'_3 \\
&= -c'_1 (\mathbf{m}_1 - \mathbf{m}_2) - c'_2 \mathbf{m}_2 - c'_3 \mathbf{m}_3 \\
&= -c'_1 \mathbf{m}_1 - (c'_2 - c'_1) \mathbf{m}_2 - c'_3 \mathbf{m}_3,
\end{aligned}
$$

for any $c'_1, c'_2, c'_3 \in \mathbb{R}$. The nonnegativity of $c_1, c_2, c_3$ implies $c'_1, c'_3 \ge 0$ and $c'_2 \ge c'_1 \ge 0$, i.e. the nonnegativity of $c'_1, c'_2, c'_3$. Thus, $\mathbf{x} \in C_{\mathbf{M}}$.

As a result, $C_{\mathbf{M}}$ contains $C_{\mathbf{M}}$. By induction, the new cone $C_{\mathbf{M}}$ also contains all past cones and therefore, all vertices of past tetrahedra. Consequently, Algorithm ISEXTREMAL selects at every iteration a point $z \in Z$ to be a vertex of the next tetrahedron and this point cannot be selected again afterwards. Since $Z$ is finite, Algorithm ISEXTREMAL terminates after a finite number of iterations. $\square$