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

HAL
open science

# Delaunay property and proximity results of the L-algorithm for digital plane probing

Jui-Ting Lu, Tristan Roussillon, Jacques-Olivier Lachaud, David Coeurjolly

► To cite this version:

Jui-Ting Lu, Tristan Roussillon, Jacques-Olivier Lachaud, David Coeurjolly. Delaunay property and proximity results of the L-algorithm for digital plane probing. Theoretical Computer Science, 2024, 1011, 10.1016/j.tcs.2024.114719. hal-04671533

HAL Id: hal-04671533

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

Submitted on 15 Aug 2024

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
<figure><img src="image_3.png" /></figure>

ELSEVIER

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

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

# Delaunay property and proximity results of the L-algorithm for digital plane probing ⭐

Jui-Ting Lu<sup>a,*</sup>, Tristan Roussillon<sup>a</sup>, Jacques-Olivier Lachaud<sup>b</sup>, David Coeurjolly<sup>a</sup>

## ARTICLE INFO

Communicated by M.J. Golin

**Keywords:**

Digital plane recognition
Plane-probing algorithms
Delaunay property

## ABSTRACT

When processing the geometry of digital surfaces (boundaries of voxel sets), linear local structures such as pieces of digital planes play an important role. To capture such geometrical features, plane-probing algorithms have demonstrated their strength: starting from an initial triangle, the digital structure is locally probed to expand the triangle approximating the plane parameters more and more precisely (converging to the exact parameters for infinite digital planes). Among the different plane-probing algorithms, the L-algorithm is a plane-probing algorithm variant which takes into account a generally larger neighborhood of points for its update process. We show in this paper that this algorithm has the advantage to guarantee the so-called *Delaunay property* of the set of probing points, which has interesting consequences: it provides a minimal basis of the plane and guarantees an as-local-as-possible computation.

## 1. Introduction

In digital geometry, a digital surface is a quadrangular mesh that corresponds to the boundary of a union of regularly spaced unit cubes. The digital nature of such surfaces is a great advantage for computations in many material sciences or medical imaging applications (e.g., [1–3]). However, the local geometry is very poor and difficult to analyze since the cubes provide at most six different normal directions. In order to estimate the geometry of the digital surfaces, an approach is to analyze locally the digital surface within a given neighborhood. The size of the neighborhood should be chosen carefully, because we risk blurring sharp features if the neighborhood is too large. The challenge is to seek the right trade-off between finding an appropriate geometrical estimation and preservation of sharp features.

Purely digital methods have thus emerged and try to perform digital surface analysis. Geometrical properties of continuous planes are translated into digital planes [4]. For example, [5] introduces the concepts of leaning points and leaning plane for digital plane recognition. Other works propose digital plane recognition algorithms with low complexity from a finite subset of three-dimensional integer points, e.g., [6,7]. To estimate differential quantities, there exist methods that require user-defined parameters such as Voronoi-based methods [8] and integral invariant methods [9]. In this context, plane-probing algorithms could lead to normal vector estimators without the need of external parameters.

<footnote><sup>a</sup> INSA Lyon, CNRS, Université Claude Bernard Lyon 1, LIRIS, UMR 5205, F-69622, France</footnote>

<footnote><sup>b</sup> Université Savoie Mont Blanc, CNRS, LAMA, F-73000 Chambéry, France</footnote>

<footnote>☆ This article belongs to Section A: Algorithms, automata, complexity and games, Edited by Paul Spirakis.</footnote>

<footnote>* Corresponding author.
E-mail address: jui-ting.lu@liris.cnrs.fr (J.-T. Lu).</footnote>
<figure><img src="image_6.png" /><figcaption>Fig. 1. The evolution (from left to right) of a tetrahedra-based plane-probing algorithm on a digital plane of normal (1, 2, 5).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 2. The evolution for normal (1, 73, 100) with H-algorithm (a) and R-algorithm (b). Here, L-algorithm has the same output as the R-algorithm. Every triangle of the evolution is superimposed. The initial triangle is blue. The last one is red. (For interpretation of the colors in the figure(s), the reader is referred to the web version of this article.)</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 3. The evolution for normal (2, 5, 156) with H-algorithm (a), R-algorithm (b) and L-algorithm (c). The notations are the same as Fig. 2.</figcaption></figure>

Plane-probing algorithms are methods which adapt the neighborhood progressively. The first plane-probing algorithm was proposed in [10]. It probes some points in the digital surface and the output represents locally an approximation of the digital surface. Other plane-probing algorithms were proposed later [11,12]. They consider a tetrahedron whose apex is outside the digital surface and a triangle formed of three points that belong to the digital surface. The apex of the tetrahedron always stays in the same position so that one can focus on the movement of the triangle. See Fig. 1 for an example on a digital plane.

Despite the fact that plane-probing algorithms can return the exact normal on an infinite digital plane determined by a rational normal vector, they may encounter difficulties with non-planar surfaces [12]. Probing for points not too far away from the initial point can alleviate those difficulties. That is why, we wish here to estimate a minimal neighborhood that provides a good normal estimation.

There are mainly three types of tetrahedron-based plane-probing algorithms: H-algorithm and R-algorithm, first introduced in [12], and L-algorithm [13]. The primary difference between those algorithms is the considered candidate set of points at each iteration. Sometimes, one can observe that the R-algorithm probes points more locally than the H-algorithm (see Fig. 2 and Fig. 3). Furthermore, one can observe that the L-algorithm usually takes fewer steps than the two other algorithms (see Fig. 4). Nevertheless, in practice, the R-algorithm and the L-algorithm always return the same triangle in the end and that final triangle has only acute or right angles. It is not trivial at all to give a proof of that fact because the triangles may have an obtuse angle throughout the iterations.

In order to find an invariant, we focus in this paper on pairs of consecutive triangles. For all three above-mentioned algorithms, two consecutive triangles share two common vertices and with the two other distinct vertices one can define a unique circumscribing ball. These balls have very strong and interesting properties in the case of the L-algorithm. For example, the radius of the balls is strictly increasing (see Fig. 4). In addition, the interior of the balls does not include any point of the digital plane. For normal vectors between (1, 1, 1) and (80, 80, 80), we have counted the number of points which lie in both the plane and the ball circumscribing two consecutive triangles. There are in total 75235972 points detected in balls for the H-algorithm; 424 points are detected for the R-algorithm; while no points for the L-algorithm. We name this invariant property the *Delaunay property* after the empty-circle condition used to define the Delaunay triangulation of a set of points in computational geometry. In particular, all the triangular facets whose
<figure><img src="image_9.png" /><figcaption>Fig. 4. Evolution of the radius of the balls circumscribing two consecutive triangles for a digital plane of normal (2, 5, 156) with H-algorithm (green), R-algorithm (blue) and L-algorithm (red). Only L-algorithm has non-decreasing variation.</figcaption></figure>

circumcircle contains none of the points of a digital segment have been characterized in [14]. This work can be thought of a partial 3D extension of that result.

Indeed, our objective is to demonstrate that the Delaunay property holds for the L-algorithm and to provide a theoretical upper bound for the position of the final triangle. The Delaunay property is also useful for an optimized implementation of the L-algorithm [13].

The outline of the paper is as follows: we start by introducing the general framework of plane-probing algorithms and the L-algorithm in sec. 2. The main theorem that mentions the Delaunay property is announced in sec. 3, followed by some proximity results for the L-algorithm. We complete the paper with two sections: in sec. 4, we prove the important Lemma 7 leaving the technical details to sec. 5, which is arranged into three categories: projection-based-results (5.1), circumsphere-based-results (5.2), and proximity results (5.3).

## 2. Digital plane probing and the L-algorithm

A digital plane is an infinite digital set defined by a normal $N \in \mathbb{Z}^3 \setminus \{0\}$, a shift value $\mu \in \mathbb{Z}$ and a thickness $\omega \in \mathbb{Z}$ as follows [15]:

$$ \mathbf{P}_{\mu,N} := \{ \mathbf{x} \in \mathbb{Z}^3 \mid \mu \le \mathbf{x} \cdot \mathbf{N} < \mu + \omega \}. \quad (1) $$

In this paper, we set $\omega := \|N\|_1$ and we assume w.l.o.g. that $\mu = 0$ and that the components of $N$ are non-negative but not all zero, i.e., $N \in \mathbb{N}^3 \setminus \{0\}$. Given a digital plane $\mathbf{P} \in \{\mathbf{P}_{0,N} | N \in \mathbb{N}^3 \setminus \{0\}\}$ of unknown normal vector, a plane-probing algorithm computes the normal vector $N$ of $\mathbf{P}$ by sparsely probing it with the predicate “is $\mathbf{x}$ in $\mathbf{P}$?”. We describe below a specific plane-probing algorithm, called L-algorithm (see Algorithm 1). An extensive description of the L-algorithm and its properties is provided in [13]. For the sake of clarity, we briefly describe its critical steps below.

### Algorithm 1: L-algorithm.

**Input:** The predicate InPlane := “Is a point $\mathbf{x} \in \mathbf{P}$?”, a point $\mathbf{o} \in \mathbf{P}$

**Output:** A normal vector $\hat{\mathbf{N}}$ and a basis of the translated lattice $\{\mathbf{x} | \mathbf{x} \cdot \hat{\mathbf{N}} = \omega - 1\}$.

1 $\mathbf{q} \leftarrow \mathbf{o} + \sum_k \mathbf{e}_k$; $(\mathbf{v}_k^{(0)})_{k \in \mathbb{Z}/3\mathbb{Z}} \leftarrow (\mathbf{q} - \mathbf{e}_k)_{k \in \mathbb{Z}/3\mathbb{Z}}$; // initialization

2 $i \leftarrow 0$;

3 while $\{\mathbf{x} \in \mathbb{N}^{(i)} | \text{InPlane}(\mathbf{x})\} \neq \emptyset$ do
4   Let $(k, \alpha, \beta)$ be such that, for all $\mathbf{y} \in \{\mathbf{x} \in \mathbb{N}^{(i)} | \text{InPlane}(\mathbf{y})\}$, $\mathbf{v}_k^{(i)} + \alpha(\mathbf{q} - \mathbf{v}_{k+1}^{(i)}) + \beta(\mathbf{q} - \mathbf{v}_{k+2}^{(i)}) \le \mathbf{r}$; // equation (3)

5   $\mathbf{v}_k^{(i+1)} \leftarrow \mathbf{v}_k^{(i)} + \alpha(\mathbf{q} - \mathbf{v}_{k+1}^{(i)}) + \beta(\mathbf{q} - \mathbf{v}_{k+2}^{(i)})$; // equation (4)

6   $\forall l \in \{0, 1, 2\} \setminus k$, $\mathbf{v}_l^{(i+1)} \leftarrow \mathbf{v}_l^{(i)}$;

7 $i \leftarrow i + 1$;

8 $\mathbf{B} \leftarrow \{\mathbf{v}_0^{(i)} - \mathbf{v}_1^{(i)}, \mathbf{v}_1^{(i)} - \mathbf{v}_2^{(i)}, \mathbf{v}_2^{(i)} - \mathbf{v}_3^{(i)}\}$;

9 Let $\mathbf{b}_1$ and $\mathbf{b}_2$ be the shortest and second shortest vectors of $\mathbf{B}$;

10 return $\mathbf{b}_1 \times \mathbf{b}_2$, $(\mathbf{b}_1, \mathbf{b}_2)$; // x denotes the cross product

We call the set $\{\mathbf{x} | \mathbf{x} \cdot \hat{\mathbf{N}} = \omega - 1\}$ a translated lattice because it is a translation of the lattice $\{\mathbf{x} | \mathbf{x} \cdot \hat{\mathbf{N}} = 0\}$ and they share the same bases.

## 2.1. Description of the L-algorithm

**Initialization** Let $(\mathbf{e}_0, \mathbf{e}_1, \mathbf{e}_2)$ be the canonical basis of $\mathbb{Z}^3$. Given a starting point $\mathbf{o} \in \mathbf{P}$, let $\mathbf{q}$ be equal to $\mathbf{o} + \sum_k \mathbf{e}_k$ ($\mathbf{q}$ is by definition not in $\mathbf{P}$) and let $\mathbf{v}_k^{(0)}$ be equal to $\mathbf{q} - \mathbf{e}_k$ for all $k \in \mathbb{Z}/3\mathbb{Z}$. We define the initial triangle as $\mathbf{T}^{(0)} := (\mathbf{v}_k^{(0)})_{k \in \mathbb{Z}/3\mathbb{Z}}$ provided that $\mathbf{T}^{(0)} \subset \mathbf{P}$.
<figure><img src="image_10.png" /><figcaption>Fig. 5. Illustration of the neighborhood $\mathcal{N}^{(i)}$ (marked with hollow diamonds).</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 6. Illustration of the balls $\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x}')$ (purple) and $\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x})$ (blue). Since $(\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x}') \cap \mathcal{H}_{+}^{(i)}) \in (\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x}) \cap \mathcal{H}_{+}^{(i)})$, we have $\mathbf{x}' \le_{\mathbf{T}} \mathbf{x}$.</figcaption></figure>

**Candidate set** At each step $i \in \mathbb{N}$, the triangle $\mathbf{T}^{(i)} = (\mathbf{v}_{k}^{(i)})_{k \in \mathbb{Z}/3\mathbb{Z}}$ represents the current approximation of the plane $\mathbf{P}$. The L-algorithm updates one vertex of $\mathbf{T}^{(i)}$ per iteration. That vertex is replaced with a point of $\mathbf{P}$ from a candidate set defined as follows:

$$ \mathcal{N}^{(i)} := \{ \mathbf{v}_{k}^{(i)} + \alpha(\mathbf{q} - \mathbf{v}_{k+1}^{(i)}) + \beta(\mathbf{q} - \mathbf{v}_{k+2}^{(i)}) \mid k \in \mathbb{Z}/3\mathbb{Z}, (\alpha, \beta) \in \mathbb{N}^2 \setminus \{(0,0)\} \}. \quad (2) $$

(See Fig. 5.)

At each step $i \in \mathbb{N}$, let $\mathcal{H}_{+}^{(i)}$ (resp. $\mathcal{H}_{-}^{(i)}$) be the open half-space bounded by the plane passing by $\mathbf{T}^{(i)}$ and containing $\mathbf{q}$ (resp. not containing $\mathbf{q}$). Let us consider the ball $\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x})$ circumscribing $\mathbf{T}^{(i)}$ and a point $\mathbf{x} \in \mathcal{H}_{+}^{(i)}$. It induces a total preorder on $\mathcal{H}_{+}^{(i)}$ through the inclusion relation (see Appendix A). For any pair $\mathbf{x}, \mathbf{x}' \in \mathcal{H}_{+}^{(i)}$, we say that $\mathbf{x}'$ is closer to $\mathbf{T}^{(i)}$ than $\mathbf{x}$, denoted by $\mathbf{x}' \le_{\mathbf{T}} \mathbf{x}$, if and only if $(\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x}') \cap \mathcal{H}_{+}^{(i)}) \subseteq (\mathcal{B}(\mathbf{T}^{(i)}, \mathbf{x}) \cap \mathcal{H}_{+}^{(i)})$ (see Fig. 6).

The L-algorithm updates a vertex of $\mathbf{T}^{(i)}$ with a point of the set $\mathcal{N}^{(i)} \cap \mathbf{P}$ that is a closest one according to $\le_{\mathbf{T}}$ (note that this is a finite set, see sec. 2.2). More precisely, if $\mathcal{N}^{(i)} \cap \mathbf{P} \neq \emptyset$, there is an index $k \in \mathbb{Z}/3\mathbb{Z}$ and there are numbers $(\alpha, \beta) \in \mathbb{N}^2 \setminus \{(0,0)\}$ such that

$$ \forall \mathbf{x} \in \mathcal{N}^{(i)} \cap \mathbf{P}, \mathbf{v}_{k}^{(i)} + \alpha(\mathbf{q} - \mathbf{v}_{k+1}^{(i)}) + \beta(\mathbf{q} - \mathbf{v}_{k+2}^{(i)}) \le_{\mathbf{T}} \mathbf{x}. \quad (3) $$

Note that the triple $(k, \alpha, \beta)$ may not be unique when several points are in a cospherical position and in this case any triple could be picked for the next iteration.
Once a triple $(k, \alpha, \beta)$ has been selected, the update rule is:

$$ egin{cases} 
\mathbf{v}_k^{(i+1)} := \mathbf{v}_k^{(i)} + \alpha(\mathbf{q} - \mathbf{v}_{k+1}^{(i)}) + \beta(\mathbf{q} - \mathbf{v}_{k+2}^{(i)}), \\
\mathbf{v}_{k+1}^{(i+1)} := \mathbf{v}_k^{(i)}, \\
\mathbf{v}_{k+2}^{(i+1)} := \mathbf{v}_{k+2}^{(i)}.
\end{cases} 
\quad (4) $$

As shown in Algorithm 1, lines 4 to 6, equations (3) and (4) are used to update the current triangle.

**Termination** The algorithm terminates at a step $n$, when the neighborhood has an empty intersection with the plane, i.e., when $\mathcal{N}^{(n)} \cap \mathbf{P} = \emptyset$ (Algorithm 1, line 3). The number of steps, $n$, is less than or equal to $\omega - 3$, which is a tight bound reached for any normal of components $(1, 1, r)$ with $r \in \mathbb{N} \setminus \{0\}$. This result can be found in [12, Theorem 1]. Slightly different candidate sets are introduced in [12]. However, they are included in $\mathcal{N}^{(i)}$ by definition for all steps $i \in \{0, ..., n\}$ and all mentioned results were actually already proved in [12] for the larger candidate set $\mathcal{N}^{(i)}$ we consider in this paper. In addition, if $\mathbf{o}$ is one of the lowest point in $\mathbf{P}$, i.e., $\mathbf{o} \cdot \mathbf{N} = 0$, $\mathbf{T}^{(n)}$ lines up with $\mathbf{P}$, as recalled in the following theorem:

**Theorem 1** ([12], Corollary 5). If $\mathbf{o}$ is a lower leaning point i.e., $\mathbf{o} \cdot \mathbf{N} = 0$, the normal of $\mathbf{T}^{(n)}$ is equal to $\mathbf{N}$ and any two edges form a basis of the translated lattice of upper leaning points, i.e., $\{\mathbf{x} \in \mathbb{Z}^3 | \mathbf{x} \cdot \mathbf{N} = \omega - 1\}$.

The condition $\mathbf{o} \cdot \mathbf{N} = 0$ is crucial for the correctness of the output of the algorithm. If $\mathbf{o}$ is not a lower leaning point, we cannot ensure the accuracy of the output. However, there are two practical solutions to cope with this problem. The first solution involves running the algorithm from all corner points and then applying a fast post-filtering procedure to determine the relevant starting corners and results (see Sec. 5 and Algorithm 5 in [12]). The second solution is to encapsulate the tetrahedron-based plane-probing algorithms within a more general framework based on a parallelepiped and a modified probing procedure [16].

## 2.2. Basic properties

We gather in this section the main properties that the L-algorithm shares with its predecessors studied in [12]. The following results involve these vectors:

$$ \forall i \in \{0, ..., n\}, \forall k \in \mathbb{Z}/3\mathbb{Z}, \mathbf{m}_k^{(i)} := \mathbf{q} - \mathbf{v}_k^{(i)}. \quad (5) $$

**Theorem 2** ([12], Lemma 3). For all $i \in \{0, ..., n\}$, $\det(\mathbf{m}_0^{(i)}, \mathbf{m}_1^{(i)}, \mathbf{m}_2^{(i)}) = 1$.

This shows that, for all steps $i \in \{0, ..., n\}$, $\{\mathbf{m}_0^{(i)}, \mathbf{m}_1^{(i)}, \mathbf{m}_2^{(i)}\}$ is a basis of $\mathbb{Z}^3$, which is especially useful in sec. 4.

**Theorem 3** ([12], Lemma 5). For all $i \in \{0, ..., n\}$, $\forall k \in \mathbb{Z}/3\mathbb{Z}$, $\mathbf{m}_k^{(i)} \cdot \mathbf{N} > 0$.

If $\mathbf{v}_k^{(i+1)} = \mathbf{v}_k^{(i)} + \alpha(\mathbf{m}_{k+1}^{(i)}) + \beta(\mathbf{m}_{k+2}^{(i)})$, then we have $\mathbf{v}_k^{(i+1)} \cdot \mathbf{N} > \mathbf{v}_k^{(i)} \cdot \mathbf{N}$ by Theorem 3. In other words, the algorithm always replaces a vertex with a higher candidate point in direction $\mathbf{N}$. That property is a key point in the proof of Theorem 1. It also implies that the set $\mathcal{N}^{(i)} \cap \mathbf{P}$ is always finite. Indeed, the scalar product $(\mathbf{v}_k^{(i)} + \alpha(\mathbf{m}_{k+1}^{(i)}) + \beta(\mathbf{m}_{k+2}^{(i)})) \cdot \mathbf{N}$ tends to infinity when $\alpha$ or $\beta$ (or both) tend to infinity. That is to say, when $\alpha$ or $\beta$ is large enough, the point $\mathbf{v}_k^{(i)} + \alpha(\mathbf{m}_{k+1}^{(i)}) + \beta(\mathbf{m}_{k+2}^{(i)})$ does not belong to $\mathbf{P}$. As a consequence, Algorithm 1 can be implemented naively by visiting every point in the set $\mathcal{N}^{(i)} \cap \mathbf{P}$ on lines 4 and 5. A more efficient algorithm is proposed in [13], where a smaller subset is shown to be enough to find a closest point.

In addition, we can derive the following small lemma which is needed in sec. 4.

**Lemma 4.** For all $i \in \{0, ..., n\}$, $\mathbf{p}^{(i)} \cdot \mathbf{N} \ge 0$, with $\mathbf{p}^{(i)} := \mathbf{q} - \sum_k \mathbf{m}_k^{(i)}$.

**Proof.** By definition $\mathbf{p}^{(0)} = \mathbf{o}$ and $\mathbf{o}$ is assumed to belong to $\mathbf{P}$. As a consequence, $\mathbf{p}^{(0)} \cdot \mathbf{N} \ge 0$.

For any $i \in \{1, ..., n-1\}$, there is $(k, \alpha, \beta)$ such that $\mathbf{m}_k^{(i+1)} = \mathbf{m}_k^{(i)} - \alpha\mathbf{m}_{k+1}^{(i)} - \beta\mathbf{m}_{k+2}^{(i)}$, $\mathbf{m}_{k+1}^{(i+1)} = \mathbf{m}_{k+1}^{(i)}$ and $\mathbf{m}_{k+2}^{(i+1)} = \mathbf{m}_{k+2}^{(i)}$ by (4). Then, we remark that $\mathbf{p}^{(i+1)} \cdot \mathbf{N} - \mathbf{p}^{(i)} \cdot \mathbf{N} = \alpha\mathbf{m}_{k+1}^{(i)} \cdot \mathbf{N} + \beta\mathbf{m}_{k+2}^{(i)} \cdot \mathbf{N}$, which is positive by Theorem 3. We can therefore conclude by induction. $\square$

## 3. Main results

For convenience let $\mathbf{T}^{(-1)}$ denotes the degenerated triangle whose three vertices are all at $\mathbf{o}$. At each step $i \in \mathbb{N}$, let $\mathcal{B}^{(i)}$ be the ball uniquely determined by the four distinct points of $\mathbf{T}^{(-1)} \cup \mathbf{T}^{(i)}$. We have experimentally observed that the following property is verified by the L-Algorithm, but neither by the H-Algorithm, nor by the R-Algorithm:
<figure><img src="image_12.png" /><figcaption>**Fig. 7.** The point $\mathbf{x}^* \in \mathbf{T}^{(i+1)} \setminus \mathbf{T}^{(i)}$ has been chosen by the algorithm to update $\mathbf{T}^{(i)}$. The ball $\mathcal{B}^{(i+1)}$ is defined from $\mathbf{T}^{(i)} \cup \{\mathbf{x}^*\}$. The easy part of the proof of Theorem 6 is based on the fact that $(\mathcal{B}^{(i+1)} \cap \mathcal{H}^{(i)}) \subseteq (\mathcal{B}^{(i)} \cap \mathcal{H}^{(i)})$. The hard part is the proof of Lemma 7.</figcaption></figure>

**Property 5 (Delaunay property for plane-probing algorithms).** For all $i \in \{0, \dots, n\}$, the ball $\mathcal{B}^{(i)}$ does not contain any point of $\mathbf{P}$ in its interior.

If we randomly pick a point from the set $\mathcal{N}^{(i)} \cap \mathbf{P}$ at each iteration, our procedure would still terminate and return a triangle whose normal is equal to the normal of the plane. However, that triangle might have a very bad aspect ratio and its vertices might lie far away the starting point. The Delaunay property is a strong geometric result ensuring that the last triangle have only acute or right angles (Corollary 8, in sec. 3.1) and that its vertices stay close enough to the starting point (sec. 3.2).

### 3.1. The Delaunay property and its consequences

The main purpose of this paper is to prove the following theorem:

**Theorem 6.** The L-algorithm verifies the Delaunay property (Property 5).

The proof of Theorem 6 requires the following lemma whose quite technical and lengthy proof is postponed to sec. 4:

**Lemma 7.** For all $i \in \{0, \dots, n-1\}$, if the interior of $\mathcal{B}^{(i)}$ contains no point of $\mathbf{P}$, then the interior of $\mathcal{B}^{(i+1)}$ contains no point of $\mathbf{P} \cap \mathcal{H}_+^{(i)}$.

**Proof of Theorem 6.** Base case $\mathcal{B}^{(0)}$, which passes through all the vertices of a unit cube, contains no integer point in its interior and as a consequence, no point of $\mathbf{P}$.

*Induction step* We assume that $\mathcal{B}^{(i)}$ contains no point of $\mathbf{P}$ in its interior for any $i \in \{0, \dots, n-1\}$ and we want to show that no point of $\mathbf{P}$ lies in the interior of $\mathcal{B}^{(i+1)}$.

By definition, the boundary of $\mathcal{B}^{(i)}$ and the boundary of $\mathcal{B}^{(i+1)}$ pass through the vertices of $\mathbf{T}^{(i)}$ and there is a point $\mathbf{x}^*$, chosen by the algorithm, lying in $\mathcal{H}_+^{(i)}$ and such that $\mathbf{x}^* \in \mathbf{T}^{(i+1)} \setminus \mathbf{T}^{(i)}$ (see Fig. 7).

First, we can safely discard the points of $\mathbf{P}$ that are located in $\mathcal{H}_-^{(i)}$. Indeed, $\mathbf{x}^* \in \mathcal{H}_+^{(i)}$ (by definition) and $\mathbf{x}^* \notin \mathcal{B}^{(i)}$ (by hypothesis) together imply that $(\mathcal{B}^{(i)} \cap \mathcal{H}_+^{(i)}) \subseteq (\mathcal{B}^{(i+1)} \cap \mathcal{H}_+^{(i)})$, thus $(\mathcal{B}^{(i+1)} \cap \mathcal{H}_-^{(i)}) \subseteq (\mathcal{B}^{(i)} \cap \mathcal{H}_-^{(i)})$ (see Lemma 32 in Appendix A). We conclude that the interior of $(\mathcal{B}^{(i+1)} \cap \mathcal{H}_-^{(i)})$ contains no point of $\mathbf{P}$, because it is included in the interior of $(\mathcal{B}^{(i)} \cap \mathcal{H}_-^{(i)})$, itself included in the interior of $\mathcal{B}^{(i)}$, which is assumed to contain no point of $\mathbf{P}$.

If we denote by $\mathcal{H}^{(i)}$ the plane containing $\mathbf{T}^{(i)}$, we can similarly show that the interior of $(\mathcal{B}^{(i+1)} \cap \mathcal{H}^{(i)})$ contains no point of $\mathbf{P}$, because $(\mathcal{B}^{(i+1)} \cap \mathcal{H}^{(i)}) = (\mathcal{B}^{(i)} \cap \mathcal{H}^{(i)})$ by the definition of $\mathcal{B}^{(i)}$ and $\mathcal{B}^{(i+1)}$.

Finally, regarding the points of $\mathbf{P}$ that are located in $\mathcal{H}_+^{(i)}$, by Lemma 7, we know that none of them are in the interior of $\mathcal{B}^{(i+1)}$, which concludes. □

One of the consequences of Theorem 6 is the following result:

**Corollary 8.** The final triangle $\mathbf{T}^{(n)}$ has acute or right angles.
**Proof.** By Theorem 6, the circumsphere $B^{(n)}$ does not contain any point of $\mathbf{P}$ in its interior. In particular, the circumcircle passing through the vertices of $\mathbf{T}^{(n)}$ does not contain in its interior the points $\mathbf{v}_k^{(n)} + (\mathbf{v}_{k+1}^{(n)} - \mathbf{v}_k^{(n)}) + (\mathbf{v}_{k+2}^{(n)} - \mathbf{v}_k^{(n)})$, for all $k \in \mathbb{Z}/3\mathbb{Z}$. By Lemma 21 on page 15, this implies that the final triangle has three acute or right angles. □

That geometrical result has another consequence that requires the following definition:

**Definition 9.** Let $L$ be a rank-two integral lattice. A basis $(\mathbf{x}, \mathbf{y})$ of $L$ is minimal if and only if $\|\mathbf{x}\|, \|\mathbf{y}\| \le \|\mathbf{x} - \mathbf{y}\| \le \|\mathbf{x} + \mathbf{y}\|$, where $\|\cdot\|$ denotes the Euclidean norm.

Such a basis is said minimal because this definition matches with the well-known Minkowski's minima [17, Theorem 7].

**Corollary 10.** The two shortest edges of the final triangle $\mathbf{T}^{(n)}$ form a minimal basis of the translated lattice of upper leaning points, i.e., $\{\mathbf{x} \in \mathbb{Z}^3 | \mathbf{x} \cdot \mathbf{N} = \omega - 1\}$.

**Proof.** We know by Theorem 1 that any two edges of the final triangle form a basis of the translated lattice of upper leaning points. We show below that the fact that all angles are acute or right (Corollary 8) implies that the two shortest edges form a minimal basis.

Let $\mathbf{x}, \mathbf{y}, \mathbf{z}$ be respectively equal to $(\mathbf{v}_1^{(n)} - \mathbf{v}_0^{(n)}), (\mathbf{v}_2^{(n)} - \mathbf{v}_0^{(n)})$ and $(\mathbf{v}_2^{(n)} - \mathbf{v}_1^{(n)})$ and assume w.l.o.g. that $\mathbf{x}$ and $\mathbf{y}$ are the two shortest vectors, i.e., $\|\mathbf{x}\|, \|\mathbf{y}\| \le \|\mathbf{z}\|$. On one hand, since $-\mathbf{z} = \mathbf{x} - \mathbf{y}$, we have by definition

$$ \|\mathbf{x}\|, \|\mathbf{y}\| \le \|\mathbf{x} - \mathbf{y}\|. $$

On the other hand, since $\mathbf{x} \cdot \mathbf{y} \ge 0$ by Corollary 8, it is obvious that

$$ \|\mathbf{x} - \mathbf{y}\| \le \|\mathbf{x} + \mathbf{y}\|. $$

Putting all together, we have $\|\mathbf{x}\|, \|\mathbf{y}\| \le \|\mathbf{x} - \mathbf{y}\| \le \|\mathbf{x} + \mathbf{y}\|$, which means by definition that the basis $(\mathbf{x}, \mathbf{y})$ is minimal. □

Thanks to the Delaunay property, we have been able to prove that the L-algorithm always terminates with an acute or right triangle. In addition, the two shortest edges of the final triangle form a minimal basis of the translated lattice of upper leaning points. In the following section, we use this result to show that the last triangle cannot be too far away from the starting point.

## 3.2. Bound on the maximal distance

The goal of this section is to show an upper bound for the magnitude of the last three vectors $(\mathbf{m}_k^{(n)})_{k \in \mathbb{Z}/3\mathbb{Z}}$, i.e., for the distance of the three vertices $(\mathbf{v}_k^{(n)})_{k \in \mathbb{Z}/3\mathbb{Z}}$ from the fixed point $\mathbf{q}$, which is located very close to the starting point $\mathbf{o}$.

Let $\mathbf{x}, \mathbf{y}, \mathbf{z}$ be respectively equal to $(\mathbf{v}_1^{(n)} - \mathbf{v}_0^{(n)}), (\mathbf{v}_2^{(n)} - \mathbf{v}_0^{(n)})$ and $(\mathbf{v}_2^{(n)} - \mathbf{v}_1^{(n)})$ and assume w.l.o.g. that their magnitude are such that $\|\mathbf{x}\| \le \|\mathbf{y}\| \le \|\mathbf{z}\|$. □

Let us focus on the rank-two translated lattice $L := \{\mathbf{x} \in \mathbb{Z}^3 | \mathbf{x} \cdot \mathbf{N} = \omega - 1\}$. Its volume, denoted by $\mathrm{vol}(L)$, is defined as the square root of the Gram determinant of any basis $(\mathbf{b}_1, \mathbf{b}_2)$ of $L$ [17, Definitions 3 and 7]. If we choose the basis returned by Algorithm 1 (see also Theorem 1), we can easily compute that $\mathrm{vol}(L) = \|\mathbf{N}\|$. □

By Corollary 10, $\|\mathbf{x}\|$ and $\|\mathbf{y}\|$ are respectively the shortest and second shortest non-zero vectors of $L$, i.e., the first and second Minkowski's minima of $L$. We can therefore relate them with $\mathrm{vol}(L)$ and thus $\|\mathbf{N}\|$ using known results from lattice theory. Equation (6) involves Hermite's constant [17, Definition 14], whereas equation (7) involves Minkowski's Second Theorem [17, Theorem 5] and the trivial lower bound $\sqrt{2} \le \|\mathbf{x}\|$:

$$ \|\mathbf{x}\|^2 \le \frac{2}{\sqrt{3}} \|\mathbf{N}\|, \qquad (6) $$

$$ \|\mathbf{y}\| \le \sqrt{\frac{2}{3}} \|\mathbf{N}\|. \qquad (7) $$

Furthermore, since the last triangle $\mathbf{T}^{(n)}$ has three acute or right angles by Corollary 8, we can use the law of cosines to bound from equations (6) and (7), the length of the longest side:

$$ \|\mathbf{z}\| \le \sqrt{\frac{2}{\sqrt{3}}} \|\mathbf{N}\| + \frac{2}{3} \|\mathbf{N}\|^2. \qquad (8) $$

Now, for all $k \in \mathbb{Z}/3\mathbb{Z}$, let us consider the orthographic projection of $\mathbf{m}_k^{(n)}$ in direction $\mathbf{N}$ defined as:

$$ p_{\mathbf{N}}(\mathbf{m}_k^{(n)}) := \mathbf{m}_k^{(n)} - \left( \mathbf{m}_k^{(n)} \cdot \frac{\mathbf{N}}{\|\mathbf{N}\|} \right) \frac{\mathbf{N}}{\|\mathbf{N}\|}. $$
Since $p_N(\mathbf{m}_k^{(n)})$ is trivially bounded by $\|\mathbf{z}\|$, we can derive from (8) an upper bound for $\|\mathbf{m}_k^{(n)}\|$ as follows:

$$ \begin{aligned} \|p_N(\mathbf{m}_k^{(n)})\|^2 &= \|\mathbf{m}_k^{(n)}\|^2 - 2 \left( \mathbf{m}_k^{(n)} \cdot \frac{\mathbf{N}}{\|\mathbf{N}\|} \right)^2 + \left( \mathbf{m}_k^{(n)} \cdot \frac{\mathbf{N}}{\|\mathbf{N}\|} \right)^2 \left( \frac{\mathbf{N}}{\|\mathbf{N}\|} \right)^2 \\ &= \|\mathbf{m}_k^{(n)}\|^2 - \left( \mathbf{m}_k^{(n)} \cdot \frac{\mathbf{N}}{\|\mathbf{N}\|} \right)^2 \\ &\le \frac{2}{\sqrt{3}} \|\mathbf{N}\| + \frac{2}{3} \|\mathbf{N}\|^2 \\ &\Rightarrow \|\mathbf{m}_k^{(n)}\|^2 \le \left( \mathbf{m}_k^{(n)} \cdot \frac{\mathbf{N}}{\|\mathbf{N}\|} \right)^2 + \frac{2}{\sqrt{3}} \|\mathbf{N}\| + \frac{2}{3} \|\mathbf{N}\|^2 \end{aligned} $$

Since a direct consequence of Theorem 1 is $\mathbf{m}_k^{(n)} \cdot \mathbf{N} = 1$, we finally obtain

$$ \forall k \in \mathbb{Z}/3\mathbb{Z}, \quad \|\mathbf{m}_k^{(n)}\|^2 \le \frac{2}{3} \|\mathbf{N}\|^2 + \frac{2}{\sqrt{3}} \|\mathbf{N}\| + \frac{1}{\|\mathbf{N}\|^2}. $$

Hence,

$$ \max_k \{ \| \mathbf{m}_k^{(n)} \| \} \le \sqrt{\frac{2}{3} \| \mathbf{N} \|^2 + \frac{2}{\sqrt{3}} \| \mathbf{N} \| + \frac{1}{\| \mathbf{N} \|^2}} \quad (9) $$

This result shows that the last triangle has vertices not too far away from $\mathbf{q}$ and thus, from the starting point $\mathbf{o}$. More precisely, their distance to $\mathbf{q}$ is comparable to the magnitude of the normal vector of the digital plane. This provides some evidence that the L-algorithm locally probes the digital plane to determine its normal vector. This property is quite important for the analysis of digital surfaces with the help of a plane-probing algorithm.

Note, however, that this result is still partial, because our derivation only holds for the last triangle $T^{(n)}$ and not for all previous triangles. Even if it is unlikely, points farther away might be probed in the course of the algorithm.

## 4. Proof of Lemma 7

This section is dedicated to the proof of

**Lemma 7.** For all $i \in \{0, \dots, n-1\}$, if the interior of $B^{(i)}$ contains no point of $\mathbf{P}$, then the interior of $B^{(i+1)}$ contains no point of $\mathbf{P} \cap \mathcal{H}_+^{(i)}$.

The proof is based on the fact that the point $\mathbf{x}^*$ selected by the algorithm at a given step $i$ is closer than other specific points of $\mathcal{N}^{(i)}$ by definition. Those specific points are shown to be closer than the points lying in specific subsets of $\mathcal{H}_+^{(i)}$. We thus partition the points of $\mathcal{H}_+^{(i)}$ into different categories according to their position and we treat each case with distinct lemmas before concluding. Since we now focus on a step $i \in \{0, \dots, n-1\}$, for sake of simplicity, we drop the exponent $(i)$ in the notations of this section.

### 4.1. Outline of the proof and notations

Remind that $\mathbf{p}$ is equal to $\mathbf{q} - \sum_k \mathbf{m}_k$. By Theorem 2, $\mathbf{m}_0, \mathbf{m}_1$ and $\mathbf{m}_2$ form a basis of $\mathbb{Z}^3$. We conveniently describe any integer point $\mathbf{y} \in \mathbb{Z}^3$ as $\mathbf{y} := \mathbf{p} + \sum_k c_k \mathbf{m}_k$, with $c_k \in \mathbb{Z}$ for all $k \in \mathbb{Z}/3\mathbb{Z}$. By construction, the bounding plane of $\mathcal{H}_+$ is defined by the vertices of $\mathbf{T}$, which can be written as $\{\mathbf{p}+\mathbf{m}_0+\mathbf{m}_1, \mathbf{p}+\mathbf{m}_1+\mathbf{m}_2, \mathbf{p}+\mathbf{m}_0+\mathbf{m}_2\}$. All points $\mathbf{p} + \sum_k c_k \mathbf{m}_k$ on that plane, including those vertices, are such that $\sum_k c_k = 2$. Hence, we have $\mathbf{p} + \sum_k c_k \mathbf{m}_k \in \mathcal{H}_+ \Leftrightarrow \sum_k c_k \ge 3$. In this section, we only consider points in $\mathcal{H}_+$, i.e., such that $\sum_k c_k \ge 3$.

We consider several cases:

(Case 1) the coefficients $c_0, c_1, c_2$ are all strictly positive (see Lemma 11),

(Case 2) one coefficient is zero and the others are strictly positive; these points are exactly the ones probed in the L-algorithm (see also the definition of the candidate points, equation (2)),

(Case 3) one coefficient is strictly negative and the others are strictly positive (see Lemma 12 and Lemma 13),

(Case 4) one coefficient is strictly positive and the others are strictly negative or null (see Lemma 14 and Lemma 15).

To check that any $\mathbf{y} \in \mathcal{H}_+$ is in one of the previous cases, it is enough to consider the partition of $\mathbb{Z}^3$ into eight octants depending on the signs of the coefficients and with a convention for null coefficients (see Fig. 8). The negative octant, in red, does not intersect $\mathcal{H}_+$ and is therefore discarded. The positive octant is itself divided into two regions, the interior, in yellow, corresponds to (Case 1), whereas the boundary faces, in green, correspond to (Case 2). Among the last six octants, three of them, in blue, correspond to (Case 3), whereas the other three, in purple, correspond to (Case 4).
<figure><img src="image_13.png" /><figcaption>Fig. 8. The discrete space $\mathbb{Z}^3$ (intersected with the box $[-5, 5]^3$ for the illustration) is partitioned into five regions: the yellow, green, blue and purple regions respectively correspond to (Case 1), (Case 2), (Case 3) and (Case 4), the red one is discarded because none of its points lie in $H_+$ (the three black arrows indicate the direction of the grid axes).</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 9. Notations for $v_k$ (black), $m_k$ (red) and $d_k$ (blue). Note that $\hat{N}_k$ (grey) is used only in sec. 5.1.</figcaption></figure>

The proofs of the following lemmas require a lot of technical details that are postponed in sec. 5 for the sake of readability. They also require the introduction of new notations (see Fig. 9):

$$ \forall k \in \mathbb{Z}/3\mathbb{Z}, \mathbf{d}_k := \mathbf{m}_{k+1} - \mathbf{m}_{k+2} = \mathbf{v}_{k+2} - \mathbf{v}_{k+1}. \qquad (10) $$

For sake of clarity, we use the bar notation whenever a scalar product with $N$ is required, i.e., $\bar{y}$ instead of $y \cdot N$ for any vector $y \in \mathbb{Z}^3$.

Lemma 4 ensures that $\bar{p} \ge 0$. Since $\forall k \in \mathbb{Z}/3\mathbb{Z}, \bar{m}_k > 0$ by Theorem 3, all points of the form $\mathbf{p} + \sum_k c_k \mathbf{m}_k$ with positive coefficients are such that $\bar{p} + \sum_k c_k \bar{m}_k > 0$. That is why we will only check if $\bar{p} + \sum_k c_k \bar{m}_k < \omega$, whenever we want to determine whether such a point is in $\mathbf{P}$ or not.

Finally, let $\Sigma$ be the set of all permutations over $\{0, 1, 2\}$. Permutations will be useful to describe in a uniform way the various sign combinations of the coefficients.

## 4.2. (Case 1)

The following lemma indicates that the points $y$ corresponding to (Case 1) do not need to be considered because they are not in $\mathbf{P}$.

**Lemma 11.** Let $\mathbf{y} = \mathbf{p} + \sum_k c_k \mathbf{m}_k$ be such that $\sum_k c_k \ge 3$. If $c_0, c_1, c_2 > 0$, then $\mathbf{y} \notin \mathbf{P}$.

**Proof.** Note that $\mathbf{y} = \mathbf{q} + \sum_k (c_k - 1) \mathbf{m}_k$. Since $(c_k - 1) \ge 0$ for all $k \in \mathbb{Z}/3\mathbb{Z}$ (by hypothesis), $\bar{q} = \omega$ (by definition) and $\bar{m}_k > 0$ (by Theorem 3), then $\bar{y} = \bar{q} + \sum_k (c_k - 1) \bar{m}_k \ge \bar{q} = \omega$ and $\mathbf{y} \notin \mathbf{P}$. $\square$
<figure><img src="image_15.png" /><figcaption>Fig. 10. Relative position of $-c_0$ with respect to $c_1$ and $c_2$. Three separate cases, (i), (ii), and (iii), are considered in the proof.</figcaption></figure>

### 4.3. (Case 3)

This subsection contains Lemma 12 and Lemma 13 that focus on (Case 3). More precisely, they indicate that the points y corresponding to (Case 3) do not need to be considered because if they are in P, then there is at least one specific point x ∈ $\mathcal{N} \cap P$ (Lemma 12) such that x ≤$_{T}$ y (Lemma 13).

**Lemma 12.** Let $y = \mathbf{p} + \sum_k c_k \mathbf{m}_k$ be such that $\sum_k c_k \ge 3$. Let $\sigma \in \Sigma$ be such that $c_{\sigma(0)} < 0$ and $c_{\sigma(1)}, c_{\sigma(2)} > 0$. If $y \in P$, then $\mathbf{p} + 2\mathbf{m}_{\sigma(1)} + \mathbf{m}_{\sigma(2)} \in P$ or $\mathbf{p} + \mathbf{m}_{\sigma(1)} + 2\mathbf{m}_{\sigma(2)} \in P$ (the two points can be both in P).

In addition, if $-c_{\sigma(0)} < \min(c_{\sigma(1)}, c_{\sigma(2)}) - 1$, then $\mathbf{p} + (c_{\sigma(0)} + c_{\sigma(1)})\mathbf{m}_{\sigma(1)} + (c_{\sigma(0)} + c_{\sigma(2)})\mathbf{m}_{\sigma(2)} \in P$.

**Proof.** We assume w.l.o.g. that $\sigma$ is the identity substitution.

Since $y \in P$, we have

$$ \bar{y} = \bar{\mathbf{p}} + \sum_k c_k \bar{\mathbf{m}}_k = \bar{\mathbf{q}} + \sum_k (c_k - 1) \bar{\mathbf{m}}_k < \omega. $$

Since $\bar{\mathbf{q}} = \omega$, the last inequality is equivalent to $\sum_k (c_k - 1) \bar{\mathbf{m}}_k < 0$.

With h set to min($\bar{\mathbf{m}}_1, \bar{\mathbf{m}}_2$) and noticing that $c_0 < 0 \Leftrightarrow -(c_0 - 1) > 1$, we equivalently have

$$ \frac{(c_1 + c_2 - 2)h}{-(c_0 - 1)} \le \frac{(c_1 - 1)\bar{\mathbf{m}}_1 + (c_2 - 1)\bar{\mathbf{m}}_2}{-(c_0 - 1)} < \bar{\mathbf{m}}_0. $$

In addition, we have

$$ \sum_k c_k \ge 3 \Leftrightarrow c_1 + c_2 - 2 \ge -c_0 + 1, $$

which means that $h < \bar{\mathbf{m}}_0$.

We conclude that if $h = \bar{\mathbf{m}}_1$ (resp. $h = \bar{\mathbf{m}}_2$), $\bar{\mathbf{p}} + 2\bar{\mathbf{m}}_1 + \bar{\mathbf{m}}_2$ (resp. $\bar{\mathbf{p}} + \bar{\mathbf{m}}_1 + 2\bar{\mathbf{m}}_2$) is strictly smaller than $\bar{\mathbf{p}} + \sum_k \bar{\mathbf{m}}_k = \bar{\mathbf{q}} = \omega$ and thus, the point $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2$ (resp. $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$) is in P.

For the second part, we similarly derive from $\sum_k (c_k - 1) \bar{\mathbf{m}}_k < 0$:

$$ \frac{(\min(c_1, c_2) - 1)}{-(c_0 - 1)} (\bar{\mathbf{m}}_1 + \bar{\mathbf{m}}_2) \le \frac{(c_1 - 1)\bar{\mathbf{m}}_1 + (c_2 - 1)\bar{\mathbf{m}}_2}{-(c_0 - 1)} < \bar{\mathbf{m}}_0. $$

Since we assume $(\min(c_1, c_2) - 1) > -c_0$, we have $\frac{(\min(c_1, c_2) - 1)}{-(c_0 - 1)} \ge 1$ and it follows that $(\bar{\mathbf{m}}_1 + \bar{\mathbf{m}}_2) < \bar{\mathbf{m}}_0$.

As a consequence,

$$ \bar{\mathbf{p}} + (c_0 + c_1)\bar{\mathbf{m}}_1 + (c_0 + c_2)\bar{\mathbf{m}}_2 < \bar{\mathbf{p}} + \sum_k c_k \bar{\mathbf{m}}_k = \bar{y} < \omega, $$

which concludes. □

**Lemma 13.** Let $y = \mathbf{p} + \sum_k c_k \mathbf{m}_k$ be such that $\sum_k c_k \ge 3$. Let $\sigma \in \Sigma$ be such that $c_{\sigma(0)} < 0$ and $c_{\sigma(1)}, c_{\sigma(2)} > 0$. If $y \in P$ and if the interior of B contains no point of P, then there exists a point x ∈ $\mathcal{N} \cap P$ such that x ≤$_{T}$ y.

**Proof.** We assume w.l.o.g. that $\sigma$ is the identity. We also assume w.l.o.g. that $c_1 \le c_2$ and consider three separate cases (see Fig. 10):

(i) $(c_1 - 1) \le c_2 \le -c_0$,

(ii) $(c_1 - 1) \le -c_0 < c_2$,

(iii) $-c_0 < (c_1 - 1) < c_2$.

Since $y \in P$, either $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$ or $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2$ is in P by Lemma 12. For (i) and (ii), we suppose here that only $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2 \in P$, because the case where only $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2 \in P$ can be proven symmetrically. For (iii), Lemma 12 provides a stronger result, that is $y \in P$ implies $\mathbf{p} + (c_0 + c_1)\mathbf{m}_1 + (c_0 + c_2)\mathbf{m}_2 \in P$, which in turn implies both $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2 \in P$ and $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2 \in P$ because $(c_0 + c_1) \ge 2$ and $(c_0 + c_2) \ge 2$ ($\bar{\mathbf{p}} + \bar{\mathbf{m}}_1 + 2\bar{\mathbf{m}}_2, \bar{\mathbf{p}} + 2\bar{\mathbf{m}}_1 + \bar{\mathbf{m}}_2 < \bar{\mathbf{p}} + (c_0 + c_1)\bar{\mathbf{m}}_1 + (c_0 + c_2)\bar{\mathbf{m}}_2 < \omega$ by Theorem 3).
Let $\mathbf{u} := -\mathbf{m}_0 + \mathbf{m}_1 + \mathbf{m}_2$. By equation (10), $\mathbf{u}$ is also equal to $\mathbf{d}_1 + \mathbf{m}_1$. The first step of the proof is to show the following results:

$$ \mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2 \in \mathbf{P} \Rightarrow \left\{ \begin{array}{ll} \mathbf{d}_1 \cdot \mathbf{m}_2 \ge 0, & (a) \\ \mathbf{m}_2 \cdot \mathbf{u} \ge 0, & (b) \\ \mathbf{d}_1 \cdot \mathbf{u} \ge 0, & (c) \\ (-\mathbf{d}_2) \cdot \mathbf{u} \ge 0, & (d) \end{array} \right. \qquad (11) $$

and

$$ \mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2 \in \mathbf{P} \Rightarrow \mathbf{m}_1 \cdot \mathbf{u} \ge 0. \qquad (12) $$

Those results are used in a second step to complete the proof: (11a), (11b), (11c), (11d) are used in cases (i) and (ii), while (11b) and (12) are used in case (iii).

**First step** If $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$ is in $\mathbf{P}$, so is $\mathbf{p} + 2\mathbf{m}_2 (\bar{\mathbf{p}} + 2\bar{\mathbf{m}}_2 < \bar{\mathbf{p}} + \bar{\mathbf{m}}_1 + 2\bar{\mathbf{m}}_2 < \omega$ by Theorem 3). As the interior of $\mathcal{B}$ does not contain any point of $\mathbf{P}$ by hypothesis, $\mathbf{p} + 2\mathbf{m}_2 \notin \mathcal{B}$. By rewriting

$$ \mathbf{p} + 2\mathbf{m}_2 = \mathbf{v}_0 - \mathbf{d}_0 = \mathbf{v}_2 + \mathbf{d}_1 - \mathbf{d}_0, $$

we can apply Lemma 21 on page 15 with the two vectors $(-\mathbf{d}_0)$, $\mathbf{d}_1$ and the point $\mathbf{v}_2$ as origin. Since $\mathbf{v}_2$, $\mathbf{v}_2 - \mathbf{d}_0 = \mathbf{v}_1$ and $\mathbf{v}_2 + \mathbf{d}_1 = \mathbf{v}_0$ are indeed on the boundary of $\mathcal{B}$, we get $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \ge 0$. From that, we finally get (11a) because $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \ge 0$ implies $\mathbf{d}_1 \cdot \mathbf{m}_2 > 0$ by Lemma 18 on page 14.

We can similarly get (11b) and (12). To explain why, we focus on the case where $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$ is assumed to be in $\mathbf{P}$ because the other case is symmetric. Note first that $\mathbf{p} + \mathbf{m}_0 \in \mathbf{P}$ (using the same arguments as in the previous paragraph for $\mathbf{p} + 2\mathbf{m}_2$). As a consequence, both $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$ and $\mathbf{p} + \mathbf{m}_0$ are not in $\mathcal{B}$ by hypothesis. We can then apply Lemma 22 on page 15 with the two vectors $\mathbf{m}_2$, $(-\mathbf{u})$ and the point $\mathbf{v}_0$ as origin. Since $\mathbf{v}_0$ and $\mathbf{v}_0 + \mathbf{m}_2 - \mathbf{u} = \mathbf{v}_1$ are indeed on the boundary of $\mathcal{B}$, we get $\mathbf{m}_2 \cdot (-\mathbf{u}) < 0$ and thus (11b).

By Lemma 20 on page 15, $\mathbf{m}_2 \cdot (\mathbf{d}_1 + \mathbf{m}_1) \ge 0$ implies $\mathbf{d}_1 \cdot (\mathbf{d}_1 + \mathbf{m}_1) > 0$. Since $\mathbf{u} = \mathbf{d}_1 + \mathbf{m}_1$, (11c) is actually a simple consequence of (11b).

It remains (11d), whose proof is separated into two distinct cases.

If $\mathbf{d}_1 \cdot \mathbf{d}_2 \le 0$, we have $\mathbf{d}_2 \cdot (\mathbf{d}_1 + \mathbf{m}_1) < 0$ and thus (11d) by Lemma 19 on page 14.

Otherwise, i.e., if $(-\mathbf{d}_1) \cdot \mathbf{d}_2 < 0$, we apply Lemma 21 with vectors $(-\mathbf{d}_1)$, $\mathbf{d}_2$ and the point $\mathbf{v}_0$ as origin. Since the points $\mathbf{v}_0$, $\mathbf{v}_0 - \mathbf{d}_1 = \mathbf{v}_2$ and $\mathbf{v}_0 + \mathbf{d}_2 = \mathbf{v}_1$ are on the boundary of $\mathcal{B}$, we deduce that the point $\mathbf{v}_0 - \mathbf{d}_1 + \mathbf{d}_2 = \mathbf{q} - \mathbf{u}$ is necessarily in the interior of $\mathcal{B}$. Moreover, since no point of $\mathcal{B}$ belongs to $\mathbf{P}$, we deduce that $\mathbf{q} - \mathbf{u}$ is not in $\mathbf{P}$.

We have therefore $\bar{\mathbf{q}} - \bar{\mathbf{u}} \ge \omega \Leftrightarrow \bar{\mathbf{u}} \le 0$. It follows that $\bar{\mathbf{v}}_2 < \omega \Rightarrow \bar{\mathbf{v}}_2 + \bar{\mathbf{u}} < \omega$, which means that the point $\mathbf{v}_2 + \mathbf{u} = \mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2$ is in $\mathbf{P}$. In this case, we have (12) and as a consequence, (11d), because $\mathbf{m}_1 \cdot (\mathbf{d}_1 + \mathbf{m}_1) \ge 0$ implies $\mathbf{d}_2 \cdot (\mathbf{d}_1 + \mathbf{m}_1) < 0$ by Lemma 20.

**Second step**

(i) We assume first that $(c_1 - 1) \le c_2 \le -c_0$. One can check that

$$ \begin{aligned} \mathbf{y} &= \mathbf{p} + \sum_k c_k \mathbf{m}_k \\ &= \mathbf{v}_0 + c_0 \mathbf{m}_0 + (c_1 - 1) \mathbf{m}_1 + (c_2 - 1) \mathbf{m}_2 \\ &= \mathbf{v}_0 + (-c_0 - c_1 + 1)(\mathbf{d}_1) + (-c_0 - c_2 + 1)(-\mathbf{d}_2) + (\sum_k c_k - 2)\mathbf{u}. \end{aligned} $$

Let $\mathbf{w} := (-c_0 - c_1 + 1)(\mathbf{d}_1) + (-c_0 - c_2 + 1)(-\mathbf{d}_2) + (\sum_k c_k - 2)\mathbf{u}$. All its coefficients, i.e., $(-c_0 - c_1 + 1)$, $(-c_0 - c_2 + 1)$, $(\sum_k c_k - 2)$, are positive by hypothesis. Since we also have (11c) and (11d), we can apply Lemma 27 on page 17 to show that $\mathbf{v}_0 + \mathbf{m}_2 \le \mathbf{v}_0 + \mathbf{w}$. As a result, there exists a point in $\mathcal{N} \cap \mathbf{P}$, namely $\mathbf{v}_0 + \mathbf{m}_2$, which is closer than $\mathbf{y}$ according to $\le_T$.

(ii) We assume now $0 \le (c_1 - 1) \le -c_0 < c_2$ and we rewrite $\mathbf{y}$ as another positive linear combination:

$$ \begin{aligned} \mathbf{y} &= \mathbf{v}_0 + c_0 \mathbf{m}_0 + (c_1 - 1) \mathbf{m}_1 + (c_2 - 1) \mathbf{m}_2 \\ &= \mathbf{v}_0 + (-c_0 - c_1 + 1)(\mathbf{d}_1) + (c_0 + c_2 - 1)(\mathbf{m}_2) + (c_1 - 1)(\mathbf{u}). \end{aligned} $$

By assumptions, all coefficients, i.e., $(-c_0 - c_1 + 1)$, $(c_0 + c_2 - 1)$, $(c_1 - 1)$, are positive. From that and (11a), (11b), (11c), (11d), we can use Lemma 28 on page 17 to get $\mathbf{v}_0 + \mathbf{m}_2 \le_T \mathbf{v}_0 + \mathbf{w}$. Again, there exists a point in $\mathcal{N} \cap \mathbf{P}$, namely $\mathbf{v}_0 + \mathbf{m}_2$, which is closer than $\mathbf{y}$ according to $\le_T$.

(iii) We finally assume $0 < -c_0 < (c_1 - 1) < c_2$ and we rewrite $\mathbf{y}$ as:

$$ \begin{aligned} \mathbf{y} &= \mathbf{v}_0 + c_0 \mathbf{m}_0 + (c_1 - 1) \mathbf{m}_1 + (c_2 - 1) \mathbf{m}_2 \\ &= \mathbf{v}_0 + (c_0 + c_1 - 1)(\mathbf{m}_1) + (c_0 + c_2 - 1)(\mathbf{m}_2) + (-c_0)(\mathbf{u}). \end{aligned} $$
By assumptions, all coefficients, i.e., $(c_0 + c_1 - 1)$, $(c_0 + c_2 - 1)$, $(-c_0)$, are positive. From that and (11b), (12), Lemma 29 on page 17 shows that there exists a point $\mathbf{x} := \mathbf{v}_0 + \alpha \mathbf{m}_1 + \beta \mathbf{m}_2$, with $\alpha, \beta \in \mathbb{N} \setminus \{(0,0)\}$, $\alpha \le (c_0 + c_1 - 1)$, $\beta \le (c_0 + c_2 - 1)$, such that $\mathbf{x} \le_{\mathbf{T}} \mathbf{y}$. To conclude (iii), it remains to check that such a point is in $\mathbf{P}$. Indeed, since $\mathbf{p} + (c_0 + c_1)\mathbf{m}_1 + (c_0 + c_2)\mathbf{m}_2 \in \mathbf{P}$ (Lemma 12), we have:

$$ \bar{\mathbf{x}} = \bar{\mathbf{p}} + (\alpha + 1)\bar{\mathbf{m}}_1 + (\beta + 1)\bar{\mathbf{m}}_2 \le \bar{\mathbf{p}} + (c_0 + c_1)\bar{\mathbf{m}}_1 + (c_0 + c_2)\bar{\mathbf{m}}_2 < \omega. \quad \square $$

### 4.4. (Case 4)

This subsection contains Lemma 14 and Lemma 15 that focus on (Case 4). More precisely, they indicate that the points $\mathbf{y}$ corresponding to (Case 4) do not need to be considered because, as in the previous section, if they are in $\mathbf{P}$, then there is at least one specific point $\mathbf{x} \in \mathcal{N} \cap \mathbf{P}$ (Lemma 14) such that $\mathbf{x} \le_{\mathbf{T}} \mathbf{y}$ (Lemma 15).

**Lemma 14.** Let $\mathbf{y} = \mathbf{p} + \sum_k c_k \mathbf{m}_k$ be such that $\sum_k c_k \ge 3$. Let $\sigma \in \Sigma$ be such that $c_{\sigma(0)}, c_{\sigma(1)} \le 0$, then $\mathbf{y} \in \mathbf{P}$ implies both:

$$ \bullet \mathbf{p} + \mathbf{m}_{\sigma(0)} + 2\mathbf{m}_{\sigma(2)} \in \mathbf{P} \text{ or } \mathbf{p} + \mathbf{m}_{\sigma(1)} + 2\mathbf{m}_{\sigma(2)} \in \mathbf{P}, $$

$$ \bullet \mathbf{p} + 2\mathbf{m}_{\sigma(2)} \in \mathbf{P}. $$

**Proof.** We assume w.l.o.g. that $\sigma$ is the identity.

Since $\mathbf{y} \in \mathbf{P}$, we have

$$ \bar{\mathbf{y}} = \bar{\mathbf{p}} + \sum_k c_k \bar{\mathbf{m}}_k = \bar{\mathbf{q}} + \sum_k (c_k - 1) \bar{\mathbf{m}}_k < \omega. $$

Since $\bar{\mathbf{q}} = \omega$, the last inequality is equivalent to $\sum_k (c_k - 1) \bar{\mathbf{m}}_k < 0$.

With $h$ set to $\max(\bar{\mathbf{m}}_0, \bar{\mathbf{m}}_1)$ and noting that $(c_2 - 1) \ge 2$ (since $\sum_k c_k \ge 3$ and $c_0, c_1 \le 0$), we equivalently have

$$ \bar{\mathbf{m}}_2 < \frac{-(c_0 - 1)\bar{\mathbf{m}}_0 - (c_1 - 1)\bar{\mathbf{m}}_1}{c_2 - 1} < \frac{-(c_0 - c_1 + 2)h}{c_2 - 1}. $$

In addition, we have

$$ \sum_k c_k \ge 3 \Leftrightarrow c_2 - 1 \ge -c_0 - c_1 + 2, $$

which means that $\bar{\mathbf{m}}_2 < h$.

We conclude that if $h = \bar{\mathbf{m}}_0$ (resp. $h = \bar{\mathbf{m}}_1$), $\bar{\mathbf{p}} + \bar{\mathbf{m}}_1 + 2\bar{\mathbf{m}}_2$ (resp. $\bar{\mathbf{p}} + \bar{\mathbf{m}}_0 + 2\bar{\mathbf{m}}_2$) is strictly smaller than $\bar{\mathbf{p}} + \sum_k \bar{\mathbf{m}}_k = \bar{\mathbf{q}} = \omega$ and thus, the point $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$ (resp. $\mathbf{p} + \mathbf{m}_0 + 2\mathbf{m}_2$) is in $\mathbf{P}$. A fortiori and whatever $h$ is, $\mathbf{p} + 2\mathbf{m}_2 \in \mathbf{P}$. $\square$

**Lemma 15.** Let $\mathbf{y} = \mathbf{p} + \sum_k c_k \mathbf{m}_k$ be such that $\sum_k c_k \ge 3$. Let $\sigma \in \Sigma$ be such that $c_{\sigma(0)}, c_{\sigma(1)} \le 0$. If $\mathbf{y} \in \mathbf{P}$ and if the interior of $\mathcal{B}$ contains no point of $\mathbf{P}$, then there exists a point $\mathbf{x} \in \mathcal{N} \cap \mathbf{P}$ such that $\mathbf{x} \le_{\mathbf{T}} \mathbf{y}$.

**Proof.** We assume w.l.o.g. that $\sigma$ is the identity.

Since $\mathbf{y} \in \mathbf{P}$, $\mathbf{p} + 2\mathbf{m}_2 \in \mathbf{P}$ by Lemma 14. That point, which is also at $\mathbf{v}_0 - \mathbf{d}_0 = \mathbf{v}_1 + \mathbf{d}_1$, is not in the interior of $\mathcal{B}$ by hypothesis and we can apply Lemma 21 on page 15 with the two vectors $(-\mathbf{d}_0)$, $\mathbf{d}_1$ and the point $\mathbf{v}_2$ as origin to get $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \ge 0$.

Furthermore, either $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2 \in \mathbf{P}$ or $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2 \in \mathbf{P}$ by Lemma 14. We assume below that $\mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2 \in \mathbf{P}$, because the case where only $\mathbf{p} + 2\mathbf{m}_1 + \mathbf{m}_2 \in \mathbf{P}$ can be proven symmetrically.

One can check that

$$ \begin{aligned} \mathbf{y} &= \mathbf{p} + \sum_k c_k \mathbf{m}_k = \mathbf{v}_0 + c_0 \mathbf{m}_0 + (c_1 - 1) \mathbf{m}_1 + (c_2 - 1) \mathbf{m}_2 \\ &= \mathbf{v}_0 + (-c_1 + 1)(-\mathbf{d}_0) + (-c_0) \mathbf{d}_1 + (\sum_k c_k - 2) \mathbf{m}_2. \end{aligned} $$

Let $\mathbf{w} := (-c_1 + 1)(-\mathbf{d}_0) + (-c_0)\mathbf{d}_1 + (\sum_k c_k - 2)\mathbf{m}_2$. All coefficients, i.e., $(-c_1 + 1)$, $(-c_0)$, $(\sum_k c_k - 2)$, are positive. Since, in addition, $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \ge 0$, we can use Lemma 30 on page 18 to show that $\mathbf{v}_0 + \mathbf{m}_2 \le_{\mathbf{T}} \mathbf{v}_0 + \mathbf{w}$, where $\mathbf{v}_0 + \mathbf{w} = \mathbf{y}$ and $\mathbf{v}_0 + \mathbf{m}_2 = \mathbf{p} + \mathbf{m}_1 + 2\mathbf{m}_2$. $\square$

### 4.5. Conclusion of the proof

Now we have all the material required to prove Lemma 7:

**Proof.** For all $i \in \{0, \dots, n-1\}$, the interior of $\mathcal{B}^{(i)}$ is assumed to contain no point of $\mathbf{P}$.

Let $\mathbf{x}^*$ be the point chosen by the algorithm at step $i$, i.e., $\mathbf{x}^* = \mathbf{T}^{(i+1)} \setminus \mathbf{T}^{(i)}$. We want to show that $\mathbf{x}^* \le_{\mathbf{T}} \mathbf{y}$, for all $\mathbf{y} \in \mathbf{P} \cap \mathcal{H}_+^{(i)}$. Let $\mathbf{y}$ be denoted as $\mathbf{p}^{(i)} + \sum_k c_k \mathbf{m}_k^{(i)}$. Note that $\sum_k c_k \ge 3$ because $\mathbf{y} \in \mathcal{H}_+^{(i)}$. Moreover, since $\mathbf{y} \in \mathbf{P}$, the coefficients cannot be all strictly positive by Lemma 11.
<figure><img src="image_16.png" /><figcaption>Fig. 11. Illustration of Lemma 17. Note that **m** does not belong to the span of **d** and **d'**. However, it projects along **N** into the interior of the convex combination of **d** and **d'** (hatched area).</figcaption></figure>

* if one coefficient is zero and the others are strictly positive (Case 2), then $x^* \le_T y$ by the design of the algorithm,

* if one coefficient is strictly negative and the others are strictly positive (Case 3), then there exists a point $x \in \mathcal{N} \cap \mathbf{P}$ such that $x \le_T y$ by Lemma 13. Then, $x^* \le_T x$ by the design of the algorithm and $x^* \le_T y$ by transitivity.

* if one coefficient is strictly positive and the others are strictly negative or null (Case 4), then, similarly, there exists a point $x \in \mathcal{N} \cap \mathbf{P}$ such that $x \le_T y$ by Lemma 15. Then, $x^* \le_T x$ by the design of the algorithm and $x^* \le_T y$ by transitivity.

Since there is no other possibility, the proof is complete. ☐

## 5. Technical details

The proof of Lemma 7 refers to several technical details that we elaborate in this section. The results are organized into three categories. First, we present in sec. 5.1 some relations between the normal of the faces of the tetrahedron formed by the current triangle and the fixed point **q** (Lemma 16), which hints the fact that **q** always projects inside the current triangle. We also include several useful angle relations in the tetrahedron. Then, we present several general and purely geometrical circumsphere-based properties in sec. 5.2, because the relation $\le_T$ and the selection of a closest point according to $\le_T$ involve circumspheres. Finally, in sec. 5.3, we derive in an algebraic way several other results about the comparison of specific points according to $\le_T$. These results are used in Lemma 13 and Lemma 15, which are the main ingredients in the proof of Lemma 7.

### 5.1. Projection-based results

Remind that $k$ is taken modulo 3. To keep notations short, we simply write $\forall k$ instead of $\forall k \in \mathbb{Z}/3\mathbb{Z}$ in this section. Let us introduce the following extra notations (see Fig. 9):

$$ \forall i \in \{0, \dots, n\}, \quad \left\{ \begin{array}{l} \forall k, \hat{\mathbf{N}}_k^{(i)} := \mathbf{m}_{k+1}^{(i)} \times \mathbf{m}_{k+2}^{(i)}, \\ \sum_{k \in \{0,1,2\}} \hat{\mathbf{N}}_k^{(i)} := \hat{\mathbf{N}}(\mathbf{T}^{(i)}). \end{array} \right. \qquad (13) $$

Note that the following equality also holds for the estimated normal vector, which is normal to the current triangle:

$$ \forall i \in \{0, \dots, n\}, \forall k, \hat{\mathbf{N}}(\mathbf{T}^{(i)}) = \mathbf{d}_k^{(i)} \times \mathbf{d}_{k+1}^{(i)}. $$

**Lemma 16.** For all $i \in \{0, \dots, n\}$, $\forall k$, $\hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}_{k+1}^{(i)} \ge 0$ and $\hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}(\mathbf{T}^{(i)}) > 0$.

**Proof.** Base Case The triangle $\mathbf{T}^{(0)}$ and **q** forms a trirectangular tetrahedron. We have $\forall k$, $\hat{\mathbf{N}}_k^{(0)} \cdot \hat{\mathbf{N}}_{k+1}^{(0)} = 0$ and $\hat{\mathbf{N}}_k^{(0)} \cdot \hat{\mathbf{N}}(\mathbf{T}^{(0)}) > 0$.

**Induction case** We now assume that for any $i \in \{0, \dots, n-1\}$, $\forall k$, $\hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}_{k+1}^{(i)} \ge 0$ and $\hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}(\mathbf{T}^{(i)}) > 0$. By the update rule, equation (4), we straightforwardly have:

$$ \hat{\mathbf{N}}_k^{(i+1)} = \hat{\mathbf{N}}_k^{(i)}, \quad \hat{\mathbf{N}}_{k+1}^{(i+1)} = \hat{\mathbf{N}}_{k+1}^{(i)} + \alpha \hat{\mathbf{N}}_k^{(i)}, \quad \hat{\mathbf{N}}_{k+2}^{(i+1)} = \hat{\mathbf{N}}_{k+2}^{(i)} + \beta \hat{\mathbf{N}}_k^{(i)}, $$

and

$$ \hat{\mathbf{N}}_k^{(i+1)} \cdot \hat{\mathbf{N}}_{k+1}^{(i+1)} = \hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}_{k+1}^{(i)} + \alpha \|\hat{\mathbf{N}}_k^{(i)}\|^2, $$

$$ \hat{\mathbf{N}}_{k+1}^{(i+1)} \cdot \hat{\mathbf{N}}_{k+2}^{(i+1)} = \hat{\mathbf{N}}_{k+1}^{(i)} \cdot \hat{\mathbf{N}}_{k+2}^{(i)} + \alpha(\hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}_{k+2}^{(i)}) + \beta(\hat{\mathbf{N}}_{k+1}^{(i)} \cdot \hat{\mathbf{N}}_k^{(i)}) + \alpha\beta\|\hat{\mathbf{N}}_k^{(i)}\|^2, $$

$$ \hat{\mathbf{N}}_{k+2}^{(i+1)} \cdot \hat{\mathbf{N}}_k^{(i+1)} = \hat{\mathbf{N}}_{k+2}^{(i)} \cdot \hat{\mathbf{N}}_k^{(i)} + \beta \|\hat{\mathbf{N}}_k^{(i)}\|^2. $$

Since we have $\forall k$, $\hat{\mathbf{N}}_k^{(i+1)} \cdot \hat{\mathbf{N}}_{k+1}^{(i+1)} \ge \hat{\mathbf{N}}_k^{(i)} \cdot \hat{\mathbf{N}}_{k+1}^{(i)}$ and $\hat{\mathbf{N}}_k^{(i+1)} \cdot \hat{\mathbf{N}}(\mathbf{T}^{(i+1)}) \ge \hat{\mathbf{N}}_k^{(i+1)} \cdot \hat{\mathbf{N}}(\mathbf{T}^{(i+1)})$, the induction hypothesis implies the result. ☐

The acuteness of the angle between $\hat{\mathbf{N}}_k^{(i)}$ and $\hat{\mathbf{N}}(\mathbf{T}^{(i)})$ for all $k$ suggests that **q** always projects into the triangle $\mathbf{T}^{(i)}$. From now on, we omit once again the exponent (i) for clarity. We go on with this purely geometrical result (see Fig. 11):
<figure><img src="image_17.png" /><figcaption>Fig. 12. Illustration of Lemma 18 in (a), Lemma 19 in (b) and Lemma 20 in (c) and (d).</figcaption></figure>

**Lemma 17.** Let $\mathbf{d}$ and $\mathbf{d}'$ be two vectors that span a plane of normal $\mathbf{N} := \mathbf{d}' \times \mathbf{d}$. Let $\mathbf{m}$ be another vector that projects along $\mathbf{N}$ into the interior of the convex combination of $\mathbf{d}$ and $\mathbf{d}'$, i.e. $(\mathbf{N} \times \mathbf{d}) \cdot \mathbf{m} < 0$ and $(\mathbf{N} \times \mathbf{d}') \cdot \mathbf{m} > 0$. If $\mathbf{d} \cdot \mathbf{d}' \ge 0$, then $\mathbf{d} \cdot \mathbf{m} > 0$ and $\mathbf{d}' \cdot \mathbf{m} > 0$.

**Proof.** We first expand $(\mathbf{N} \times \mathbf{d}) \cdot \mathbf{m} < 0$, which is equivalent to $(\mathbf{d} \times \mathbf{m}) \cdot (\mathbf{d} \times \mathbf{d}') > 0$, using the scalar quadruple product rule:

$$ \|\mathbf{d}\|^2 \mathbf{d}' \cdot \mathbf{m} - (\mathbf{d} \cdot \mathbf{d}') \mathbf{d} \cdot \mathbf{m} > 0. \quad (14) $$

We then similarly expand $(\mathbf{N} \times \mathbf{d}') \cdot \mathbf{m} > 0$, equivalent to $(\mathbf{d}' \times \mathbf{m}) \cdot (\mathbf{d} \times \mathbf{d}') < 0$, as:

$$ (\mathbf{d} \cdot \mathbf{d}') \mathbf{d}' \cdot \mathbf{m} - \|\mathbf{d}'\|^2 \mathbf{d} \cdot \mathbf{m} < 0. \quad (15) $$

If $\mathbf{d} \cdot \mathbf{d}' = 0$, we can conclude from (14) for $\mathbf{d}' \cdot \mathbf{m}$ and from (15) for $\mathbf{d} \cdot \mathbf{m}$.

If not, then $\mathbf{d} \cdot \mathbf{d}' > 0$ and we can derive lower and upper bounds for $\mathbf{d}' \cdot \mathbf{m}$, respectively from (14) and (15):

$$ \frac{(\mathbf{d} \cdot \mathbf{d}')}{\|\mathbf{d}\|^2} \mathbf{d} \cdot \mathbf{m} < \mathbf{d}' \cdot \mathbf{m} < \frac{\|\mathbf{d}'\|^2}{(\mathbf{d} \cdot \mathbf{d}')}(\mathbf{d} \cdot \mathbf{m}). \quad (16) $$

Multiplying both sides by $\|\mathbf{d}\|^2$ and $(\mathbf{d} \cdot \mathbf{d}')$ leads to:

$$ \|\mathbf{d} \cdot \mathbf{d}'\|^2 \mathbf{d} \cdot \mathbf{m} < \|\mathbf{d}'\|^2 \|\mathbf{d}\|^2 \mathbf{d} \cdot \mathbf{m} \Leftrightarrow (\|\mathbf{d} \cdot \mathbf{d}'\|^2 - \|\mathbf{d}'\|^2 \|\mathbf{d}\|^2)(\mathbf{d} \cdot \mathbf{m}) < 0. $$

Since $\|\mathbf{d} \cdot \mathbf{d}'\|^2 \le \|\mathbf{d}'\|^2 \|\mathbf{d}\|^2$, we conclude that $\mathbf{d} \cdot \mathbf{m} > 0$. In addition, since $\mathbf{d} \cdot \mathbf{m} > 0$ and $\mathbf{d} \cdot \mathbf{d}' > 0$, it follows from (16) that $\mathbf{d}' \cdot \mathbf{m} > 0$. □

We now combine the two preceding lemmas to find angular relations in the tetrahedron formed by the current triangle and $\mathbf{q}$, i.e., involving the vectors $(\mathbf{m}_k)$ and $(\mathbf{d}_k)$. See Fig. 12. These results are used in Lemma 13 and in sec. 5.3.

**Lemma 18.** For all $k$, if $\mathbf{d}_k \cdot \mathbf{d}_{k+1} \le 0$, then $\mathbf{d}_{k+1} \cdot \mathbf{m}_{k+2} > 0$ and $\mathbf{d}_k \cdot \mathbf{m}_{k+2} < 0$.

**Proof.** (See Fig. 12-(a).) We use Lemma 17, with $\mathbf{d}, \mathbf{d}', \mathbf{m}$ respectively set to $(-\mathbf{d}_k)$, $\mathbf{d}_{k+1}$ and $\mathbf{m}_{k+2}$. Note that the normal $\mathbf{d}_k \times \mathbf{d}_{k+1}$ is by definition equal to $\hat{\mathbf{N}}(\mathbf{T})$. Note also that Lemma 16 implies (see (B.1) and (B.2)):

$$ (\hat{\mathbf{N}}(\mathbf{T}) \times (-\mathbf{d}_k)) \cdot \mathbf{m}_{k+2} < 0, $$

$$ (\hat{\mathbf{N}}(\mathbf{T}) \times \mathbf{d}_{k+1}) \cdot \mathbf{m}_{k+2} > 0, $$

which is the projection criterion of Lemma 17.

Since we assume in addition that $(-\mathbf{d}_k) \cdot \mathbf{d}_{k+1} \ge 0$, we conclude by Lemma 17 that $(-\mathbf{d}_k) \cdot \mathbf{m}_{k+2} > 0$ and $\mathbf{d}_{k+1} \cdot \mathbf{m}_{k+2} > 0$. □

Likewise,

**Lemma 19.** For all $k$, if $\mathbf{d}_k \cdot \mathbf{d}_{k+1} \le 0$, then $\mathbf{d}_k \cdot (\mathbf{d}_k + \mathbf{m}_k) > 0$ and $\mathbf{d}_{k+1} \cdot (\mathbf{d}_k + \mathbf{m}_k) < 0$.

**Proof.** (See Fig. 12-(b).) We use Lemma 17, with $\mathbf{d}, \mathbf{d}', \mathbf{m}$ respectively set to $(-\mathbf{d}_k)$, $\mathbf{d}_{k+1}$ and $-(\mathbf{d}_k + \mathbf{m}_k)$. Note that the normal is equal to $\hat{\mathbf{N}}(\mathbf{T})$ and the projection criterion is implied by Lemma 16 (see (B.3) and (B.4)):

$$ (\hat{\mathbf{N}}(\mathbf{T}) \times (-\mathbf{d}_k)) \cdot (-\mathbf{d}_k + \mathbf{m}_k) < 0, $$

$$ (\hat{\mathbf{N}}(\mathbf{T}) \times \mathbf{d}_{k+1}) \cdot (-\mathbf{d}_k + \mathbf{m}_k) > 0. $$

From Lemma 17, we thus have $\mathbf{d}_k \cdot (\mathbf{d}_k + \mathbf{m}_k) > 0$ and $\mathbf{d}_{k+1} \cdot (\mathbf{d}_k + \mathbf{m}_k) > 0$. □

Finally,
<figure><img src="image_18.png" /><figcaption>Fig. 13. Illustrations for circumsphere-based lemma of sec. 5.2. A point is depicted as a black disk if it is inside the ball of interest, and as a hollow disk if it is not in the closed ball.</figcaption></figure>

**Lemma 20.** For all $k$, if $\mathbf{m}_k \cdot (\mathbf{d}_k + \mathbf{m}_k) \ge 0$, then $\mathbf{d}_{k+1} \cdot \mathbf{m}_k < 0$ and $\mathbf{d}_{k+1} \cdot (\mathbf{d}_k + \mathbf{m}_k) < 0$. Similarly, if $\mathbf{m}_{k+1} \cdot (\mathbf{d}_k + \mathbf{m}_k) \ge 0$, then $\mathbf{d}_k \cdot \mathbf{m}_{k+1} > 0$ and $\mathbf{d}_k \cdot (\mathbf{d}_k + \mathbf{m}_k) > 0$.

**Proof.** (See Fig. 12-(c),(d).) We focus on the first part, because the proof of the second part is quite similar.

We use Lemma 17, with $\mathbf{d}, \mathbf{d}', \mathbf{m}$ respectively set to $(\mathbf{d}_k + \mathbf{m}_k)$, $\mathbf{m}_k$ and $(-\mathbf{d}_{k+1})$. Note that the normal is equal to $\mathbf{m}_k \times (\mathbf{d}_k + \mathbf{m}_k) = \hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}$ and the projection criterion is implied by Lemma 16 (see (B.5) and (B.6)):

$$((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times (\mathbf{d}_k + \mathbf{m}_k)) \cdot (-\mathbf{d}_{k+1}) < 0, \\ ((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times \mathbf{m}_k) \cdot (-\mathbf{d}_{k+1}) > 0.$$

From Lemma 17, we thus have $\mathbf{d}_{k+1} \cdot \mathbf{m}_k < 0$ and $\mathbf{d}_{k+1} \cdot (\mathbf{d}_k + \mathbf{m}_k) < 0$, which concludes. ☐

## 5.2. Circumsphere-based results

In this section, we show several general and purely geometrical circumsphere-based results. They are illustrated in Fig. 13. Lemma 21 is the most often used, notably in some of the key results, such as Lemma 13 and Lemma 15, as well as in Corollary 8. Lemma 22 is invoked in Lemma 13, whereas Lemma 23 and Lemma 24 are crucial in sec. 5.3. Note that we use the term ball for a 3D ball and disk for its 2D counterpart. For the sake of clarity, we identify any point in $x \in \mathbb{R}^3$ with the vector $x$ of its coordinates.

**Lemma 21.** Let $\mathbf{u}, \mathbf{w}$ be two non-zero vectors of $\mathbb{R}^3$. Let $\mathbf{B}$ be a closed ball whose border passes through the origin $\mathbf{0}$ as well as through $\mathbf{u}$ and $\mathbf{w}$. The point $\mathbf{s} := \mathbf{u} + \mathbf{w}$ belongs to the interior of the ball $\mathbf{B}$ if and only if $\mathbf{u} \cdot \mathbf{w} < 0$.

**Proof.** Consider a ball $\mathbf{B}$ with centre $\mathbf{c}$ and radius $r$. First $\mathbf{0} \in \partial \mathbf{B}$ is equivalent to $r^2 = c^2$. Using this relation it follows:

$$\mathbf{u} \in \partial \mathbf{B} \Leftrightarrow (\mathbf{u} - \mathbf{c})^2 = c^2 \Leftrightarrow 2\mathbf{c} \cdot \mathbf{u} = \mathbf{u}^2, \qquad (17)$$

$$\mathbf{w} \in \partial \mathbf{B} \Leftrightarrow (\mathbf{w} - \mathbf{c})^2 = c^2 \Leftrightarrow 2\mathbf{c} \cdot \mathbf{w} = \mathbf{w}^2, \qquad (18)$$

$$\mathbf{s} \in \tilde{\mathbf{B}} \Leftrightarrow (\mathbf{u} + \mathbf{w} - \mathbf{c})^2 < c^2 \Leftrightarrow (\mathbf{u} + \mathbf{w})^2 < 2(\mathbf{u} + \mathbf{w}) \cdot \mathbf{c}. \qquad (19)$$

Developing $(\mathbf{u} + \mathbf{w})^2$ in (19), we get $\mathbf{u}^2 + \mathbf{w}^2 + 2\mathbf{u} \cdot \mathbf{w} < 2(\mathbf{u} + \mathbf{w}) \cdot \mathbf{c}$, which is equivalent to $\mathbf{u}^2 + \mathbf{w}^2 + 2\mathbf{u} \cdot \mathbf{w} < \mathbf{u}^2 + \mathbf{w}^2$ by (17) and (18). Subtracting $\mathbf{u}^2 + \mathbf{w}^2$ from both sides gives the equivalent formulation $\mathbf{u} \cdot \mathbf{w} < 0$. ☐

**Lemma 22.** Let $\mathbf{u}, \mathbf{w}$ be two non-zero vectors of $\mathbb{R}^3$. Let $\mathbf{B}$ be a closed ball whose border passes through the origin $\mathbf{0}$ and the point $\mathbf{s} = \mathbf{u} + \mathbf{w}$. If $\mathbf{u}$ and $\mathbf{w}$ do not lie in the ball $\mathbf{B}$, then $\mathbf{u} \cdot \mathbf{w} < 0$.

**Proof.** Consider a ball $\mathbf{B}$ with centre $\mathbf{c}$ and radius $r$. Using again the equivalence $\mathbf{0} \in \partial \mathbf{B} \Leftrightarrow r^2 = c^2$ it follows:

$$\mathbf{s} \in \partial \mathbf{B} \Leftrightarrow (\mathbf{u} + \mathbf{w} - \mathbf{c})^2 = c^2 \Leftrightarrow (\mathbf{u} + \mathbf{w})^2 = 2(\mathbf{u} + \mathbf{w}) \cdot \mathbf{c}, \qquad (20)$$
$$ \mathbf{u} \notin B \Leftrightarrow (\mathbf{u} - c)^2 > c^2 \Leftrightarrow 2c \cdot \mathbf{u} < \mathbf{u}^2, \qquad (21) $$

$$ \mathbf{w} \notin B \Leftrightarrow (\mathbf{w} - c)^2 > c^2 \Leftrightarrow 2c \cdot \mathbf{w} < \mathbf{w}^2. \qquad (22) $$

Gathering results together, we get:

$$ \begin{align*} \mathbf{u}^2 + \mathbf{w}^2 + 2\mathbf{u} \cdot \mathbf{w} &= (\mathbf{u} + \mathbf{w})^2 = 2(\mathbf{u} + \mathbf{w}) \cdot c && \text{(using (20))} \\ < \mathbf{u}^2 + \mathbf{w}^2 && \text{(using (21) and (22))}. \end{align*} $$

Subtracting $\mathbf{u}^2 + \mathbf{w}^2$ from both sides gives $\mathbf{u} \cdot \mathbf{w} < 0$. $\square$

**Lemma 23.** Let $\mathbf{u}$ be a non-zero vector in $\mathbb{R}^3$. Let $B$ be a closed ball whose border passes through the origin $\mathbf{0}$. If $\mathbf{u}$ does not lie in the interior $\tilde{B}$ of the ball $B$, then no point $\delta\mathbf{u}$ such that $\delta > 1$ lies in the ball $B$.

**Proof.** Consider a ball $B$ with centre $c$ and radius $r$, and recalling that $\mathbf{0} \in \partial B$ is equivalent to $r^2 = c^2$, we get

$$ \mathbf{u} \notin \tilde{B} \Leftrightarrow (\mathbf{u} - c)^2 \geq c^2 \Leftrightarrow 2c \cdot \mathbf{u} \leq \mathbf{u}^2. \qquad (23) $$

We then compute:

$$ \begin{align*} (\delta \mathbf{u} - c)^2 &= \delta^2 \mathbf{u}^2 - 2\delta \mathbf{u} \cdot c + c^2 \\ &\geq \delta(\delta - 1)\mathbf{u}^2 + c^2 && \text{(by (23) and factoring $\mathbf{u}^2$)} \\ &> r^2. && \text{(since $\delta > 1$, $\mathbf{u}^2 > 0$ and $c^2 = r^2$)} \end{align*} $$

We conclude since $(\delta\mathbf{u} - c)^2 > r^2$ is equivalent to $\delta\mathbf{u} \notin B$. $\square$

**Lemma 24.** Let $\mathbf{u}, \mathbf{w}$ be two non-zero vectors of $\mathbb{R}^3$. Let $B$ be a closed ball whose border passes through the origin $\mathbf{0}$ and the two points $\mathbf{u}$ and $\mathbf{w}$. No point of the set $\Lambda := \{-\mathbf{u}\mathbf{u} - \mathbf{b}\mathbf{w} \mid (a, b) \in \mathbb{N}^2\}$ lies in the interior $\tilde{B}$ of the ball $B$.

**Proof.** Consider a ball $B$ with centre $c$ and radius $r$, and recalling that $\mathbf{0} \in \partial B$ is equivalent to $r^2 = c^2$, we get

$$ \mathbf{u} \in \partial B \Leftrightarrow (\mathbf{u} - c)^2 = c^2 \Leftrightarrow 2c \cdot \mathbf{u} = \mathbf{u}^2, \qquad (24) $$

$$ \mathbf{w} \in \partial B \Leftrightarrow (\mathbf{w} - c)^2 = c^2 \Leftrightarrow 2c \cdot \mathbf{w} = \mathbf{w}^2. \qquad (25) $$

We then compute for arbitrary non-negative integers $a$ and $b$:

$$ \begin{align*} (-\mathbf{u}\mathbf{u} - \mathbf{b}\mathbf{w} - c)^2 &= c^2 + (\mathbf{u}\mathbf{u} + \mathbf{b}\mathbf{w})^2 + 2c \cdot (\mathbf{u}\mathbf{u} + \mathbf{b}\mathbf{w}) \\ &= c^2 + (\mathbf{u}\mathbf{u} + \mathbf{b}\mathbf{w})^2 + \mathbf{u}\mathbf{u}^2 + \mathbf{b}\mathbf{w}^2 && \text{(using (24) and (25))} \\ &\geq r^2. && \text{(since $a \geq 0$, $b \geq 0$ and $c^2 = r^2$)} \end{align*} $$

We conclude since $(-\mathbf{u}\mathbf{u} - \mathbf{b}\mathbf{w} - c)^2 \geq r^2$ is equivalent to $-\mathbf{u}\mathbf{u} - \mathbf{b}\mathbf{w} \notin \tilde{B}$. $\square$

### 5.3. Proximity results

In this subsection, we demonstrate some technical lemmas that give the order relations induced by the spheres circumscribing the current triangle. They are used in the proofs of Lemma 13 and Lemma 15 to establish the Delaunay property.

In what follows, we use the notation $\delta_T^0(\cdot, \cdot)$, first introduced in [18], which designates the following 4D determinant:

**Definition 25.**

$$ \delta_T^0(\mathbf{x}, \mathbf{y}) := \begin{vmatrix} \mathbf{d}_0 & -\mathbf{d}_2 & \mathbf{x} & \mathbf{y} \\ \mathbf{d}_0^2 & \mathbf{d}_2^2 & \mathbf{x}^2 & \mathbf{y}^2 \end{vmatrix}, \qquad (26) $$

with the relation

$$ \forall \mathbf{x}, \mathbf{y} \in \mathcal{H}_+, \quad \delta_T^0(\mathbf{x}, \mathbf{y}) \geq 0 \Leftrightarrow \mathbf{v}_0 + \mathbf{x} \leq_T \mathbf{v}_0 + \mathbf{y} \qquad (27) $$

and the identity [18, equation (6)]

$$ \delta_T^0(\mathbf{z}, \mathbf{z}^\prime + \mathbf{z}^\prime\prime) = \delta_T^0(\mathbf{z}, \mathbf{z}^\prime) + \delta_T^0(\mathbf{z}, \mathbf{z}^\prime\prime) + (2\mathbf{z}^\prime \cdot \mathbf{z}^\prime\prime) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{z}]. \qquad (28) $$

**Lemma 26.** Let $\mathbf{u} := -\mathbf{m}_0 + \mathbf{m}_1 + \mathbf{m}_2$. If $\mathbf{d}_1 \cdot \mathbf{u} \geq 0$ (resp. $(-\mathbf{d}_2) \cdot \mathbf{u} \geq 0$), then $\delta_T^0(\mathbf{m}_1, \mathbf{u}\mathbf{u}) \geq 0$ (resp. $\delta_T^0(\mathbf{m}_2, \mathbf{u}\mathbf{u}) \geq 0$) for all $\mathbf{a} \in \mathbb{N}$.
**Proof.** The lemma is trivially true for $a = 0$ and we can safely assume that $a \ge 1$.

**Base case** Using Lemma 21 with the vectors $\mathbf{d}_1, \mathbf{u}$ and the origin set to $\mathbf{v}_2, \mathbf{d}_1 \cdot \mathbf{u} \ge 0$ implies that the ball whose border passes through $\mathbf{T}$ and $\mathbf{v}_2 + \mathbf{u} = \mathbf{v}_0 + \mathbf{m}_1$ does not include $\mathbf{v}_2 + \mathbf{d}_1 + \mathbf{u} = \mathbf{v}_0 + \mathbf{u}$ in its interior. That means that $\delta_T^0(\mathbf{m}_1, \mathbf{u}) \ge 0$ and we can similarly show that $\delta_T^0(\mathbf{m}_2, \mathbf{u}) \ge 0$ if $(-\mathbf{d}_2) \cdot \mathbf{u} \ge 0$.

**Induction step** Let $\mathbf{m}$ be either $\mathbf{m}_1$ or $\mathbf{m}_2$. We now assume that for some $a \in \mathbb{N}$, $\delta_T^0(\mathbf{m}, \mathbf{u}) \ge 0$ and we want to show that $\delta_T^0(\mathbf{m}, (a+1)\mathbf{u}) \ge 0$.

By (28), we have

$$ \delta_T^0(\mathbf{m}, (a+1)\mathbf{u}) = \delta_T^0(\mathbf{m}, a\mathbf{u}) + \delta_T^0(\mathbf{m}, \mathbf{u}) \\ + 2a(\mathbf{u} \cdot \mathbf{u}) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}]. $$

Since $\det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}] = \det[\mathbf{m}_0, \mathbf{m}_1, \mathbf{m}_2]$, which is equal to 1 by Theorem 2, the whole sum is strictly positive due to the induction hypothesis and the base case. $\square$

Lemma 27, Lemma 28, Lemma 29 are respectively used in the cases (i), (ii) and (iii) of the proof of Lemma 13.

**Lemma 27.** Let $\mathbf{u} := -\mathbf{m}_0 + \mathbf{m}_1 + \mathbf{m}_2$ and $\mathbf{w} := a(\mathbf{d}_1) + b(-\mathbf{d}_2) + c(\mathbf{u})$, with $a, b, c \ge 0$. If $\mathbf{d}_1 \cdot \mathbf{u} \ge 0$ and $(-\mathbf{d}_2) \cdot \mathbf{u} \ge 0$, then $\delta_T^0(\mathbf{m}_2, \mathbf{w}) \ge 0$.

**Proof.** By (28), we have

$$ \delta_T^0(\mathbf{m}_2, \mathbf{w}) = \delta_T^0(\mathbf{m}_2, a\mathbf{d}_1 + b(-\mathbf{d}_2)) + \delta_T^0(\mathbf{m}_2, c\mathbf{u}) \\ + 2((a\mathbf{d}_1 + b(-\mathbf{d}_2)) \cdot c\mathbf{u}) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2]. $$

We show below that the three terms are positive, so is the whole sum.

* For the first term, we apply Lemma 24 with the vectors $-\mathbf{d}_1, \mathbf{d}_2$ and the origin set to $\mathbf{v}_0$ to deduce that the point $\mathbf{v}_0 + a\mathbf{d}_1 + b(-\mathbf{d}_2)$ is not in the interior of the ball passing through $\mathbf{T}$ and $\mathbf{v}_0 + \mathbf{m}_2$. Thus, $\delta_T^0(\mathbf{m}_2, a\mathbf{d}_1 + b(-\mathbf{d}_2)) \ge 0$.

* Since $(-\mathbf{d}_2) \cdot \mathbf{u} \ge 0$, $\delta_T^0(\mathbf{m}_2, c\mathbf{u}) \ge 0$ by Lemma 26.

* Finally, $(a\mathbf{d}_1 + b(-\mathbf{d}_2)) \cdot c\mathbf{u} \ge 0$ because $a, b, c, \mathbf{d}_1 \cdot \mathbf{u}$ and $(-\mathbf{d}_2) \cdot \mathbf{u}$ are assumed to be positive and, using Theorem 2, one can easily check that $\det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2] = \det[\mathbf{m}_0, \mathbf{m}_1, \mathbf{m}_2] = 1$. $\square$

**Lemma 28.** Let $\mathbf{u} := -\mathbf{m}_0 + \mathbf{m}_1 + \mathbf{m}_2$ and $\mathbf{w} := a(\mathbf{d}_1) + b(\mathbf{m}_2) + c(\mathbf{u})$, with $a, b, c \ge 0$. If $\mathbf{m}_2 \cdot \mathbf{u} \ge 0$, $\mathbf{d}_1 \cdot \mathbf{u} \ge 0$, $(-\mathbf{d}_2) \cdot \mathbf{u} \ge 0$ and $\mathbf{d}_1 \cdot \mathbf{m}_2 \ge 0$, then $\delta_T^0(\mathbf{m}_2, \mathbf{w}) \ge 0$.

**Proof.** By (28), we have

$$ \delta_T^0(\mathbf{m}_2, \mathbf{w}) = \delta_T^0(\mathbf{m}_2, a\mathbf{d}_1 + b\mathbf{m}_2) + \delta_T^0(\mathbf{m}_2, c\mathbf{u}) \\ + 2((a\mathbf{d}_1 + b\mathbf{m}_2) \cdot c\mathbf{u}) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2]. $$

One can easily check that $\det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2] = \det[\mathbf{m}_0, \mathbf{m}_1, \mathbf{m}_2]$, which is equal to 1 by Theorem 2.

In addition, we use (28) again to decompose the first term and finally get

$$ \delta_T^0(\mathbf{m}_2, \mathbf{w}) = \delta_T^0(\mathbf{m}_2, a\mathbf{d}_1) + \delta_T^0(\mathbf{m}_2, b\mathbf{m}_2) + \delta_T^0(\mathbf{m}_2, c\mathbf{u}) \\ + 2ab(\mathbf{d}_1 \cdot \mathbf{m}_2) + 2(a\mathbf{d}_1 + b\mathbf{m}_2) \cdot c\mathbf{u}. $$

We can now prove that each term of the sum is positive:

* For the first two terms, we consider the ball whose border passes through $\mathbf{T}$ and $\mathbf{v}_0 + \mathbf{m}_2$. If $a = 0$ (resp. $b \in \{0, 1\}$), the point $\mathbf{v}_0 + a\mathbf{d}_1$ (resp. $\mathbf{v}_0 + b\mathbf{m}_2$) trivially belongs to the boundary of the ball, which implies a null term. If $a \ge 1$ (resp. $b \ge 2$), we consider the ray from $\mathbf{v}_0$ in direction $\mathbf{d}_1$ (resp. from $\mathbf{v}_0$ in direction $\mathbf{m}_2$) and we use Lemma 23 to show that the point $\mathbf{v}_0 + a\mathbf{d}_1$ (resp. $\mathbf{v}_0 + b\mathbf{m}_2$) does not belong to the interior of the ball, which means that $\delta_T^0(\mathbf{m}_2, a\mathbf{d}_1) \ge 0$ (resp. $\delta_T^0(\mathbf{m}_2, b\mathbf{m}_2) \ge 0$).

* Since $(-\mathbf{d}_2) \cdot \mathbf{u} \ge 0$, $\delta_T^0(\mathbf{m}_2, c\mathbf{u}) \ge 0$ by Lemma 26.

* All scalar products of the last two terms are positive or null due to the hypotheses. $\square$

**Lemma 29.** Let $\mathbf{u} := -\mathbf{m}_0 + \mathbf{m}_1 + \mathbf{m}_2$, $\mathbf{w} := a(\mathbf{m}_1) + b(\mathbf{m}_2) + c(\mathbf{u})$, with $a, b, c \ge 0$. Let $\Lambda$ be the set $\{\alpha\mathbf{m}_1 + \beta\mathbf{m}_2 | \alpha, \beta \in \mathbb{N} \setminus \{(0, 0)\}, \alpha \le a, \beta \le b\}$ and $\mathbf{w}' \in \Lambda$ be such that $\forall \mathbf{w}'' \in \Lambda$, $\delta_T^0(\mathbf{w}', \mathbf{w}'') \ge 0$. If $\mathbf{m}_1 \cdot \mathbf{u} \ge 0$ and $\mathbf{m}_2 \cdot \mathbf{u} \ge 0$, then $\delta_T^0(\mathbf{w}', \mathbf{w}) \ge 0$.
**Proof.** By (28), we have

$$ \delta_T^0(\mathbf{w}', \mathbf{w}) = \delta_T^0(\mathbf{w}', (a\mathbf{m}_1 + b\mathbf{m}_2)) + \delta_T^0(\mathbf{w}', c\mathbf{u}) \\ + 2((a\mathbf{m}_1 + b\mathbf{m}_2)) \cdot c\mathbf{u}) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{w}'] $$

* The first term $\delta_T^0(\mathbf{w}', (a\mathbf{m}_1 + b\mathbf{m}_2))$ is positive by definition of $\mathbf{w}'$.

* $2((a\mathbf{m}_1 + b\mathbf{m}_2)) \cdot c\mathbf{u})$ is positive because we assume that $a, b, c, \mathbf{m}_1 \cdot \mathbf{u}$ and $\mathbf{m}_2 \cdot \mathbf{u}$ are positive. Moreover, setting $\mathbf{w}' := a'\mathbf{m}_1 + b'\mathbf{m}_2$ and using Theorem 2, one can easily check that

$$ \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{w}'] = (a' + b') \det[\mathbf{m}_0, \mathbf{m}_1, \mathbf{m}_2] = (a' + b') \geq 1. $$

As a consequence, the third term of the sum is positive.

* It remains to show that the second term is also positive.

By Lemma 20, $\mathbf{m}_2 \cdot \mathbf{u} \geq 0 \Rightarrow \mathbf{d}_1 \cdot \mathbf{u} > 0$. From the last inequality, we have by Lemma 26, $\delta_T^0(\mathbf{m}_1, c\mathbf{u}) \geq 0$, which means that $\mathbf{v}_0 + \mathbf{m}_1 \leq_T \mathbf{v}_0 + c\mathbf{u}$. However, since $\mathbf{v}_0 + \mathbf{w}' \leq_T \mathbf{v}_0 + \mathbf{m}_1$ by definition of $\mathbf{w}'$, we have by transitivity $\mathbf{v}_0 + \mathbf{w}' \leq_T \mathbf{v}_0 + c\mathbf{u}$, i.e., $\delta_T^0(\mathbf{w}', c\mathbf{u}) \geq 0$. □

Lemma 30 is used in the proof of Lemma 15.

**Lemma 30.** Let $\mathbf{w} := a(-\mathbf{d}_0) + b(\mathbf{d}_1) + c(\mathbf{m}_2)$, with $a, b, c \geq 0$. If $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \geq 0$, then $\delta_T^0(\mathbf{m}_2, \mathbf{w}) \geq 0$.

**Proof.** By (28), we have

$$ \delta_T^0(\mathbf{m}_2, \mathbf{w}) = \delta_T^0(\mathbf{m}_2, a(-\mathbf{d}_0) + b(\mathbf{d}_1)) + \delta_T^0(\mathbf{m}_2, c\mathbf{m}_2) \\ + 2((a(-\mathbf{d}_0) + b\mathbf{d}_1) \cdot c\mathbf{m}_2) \det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2]. $$

One can easily check that $\det[\mathbf{d}_2, -\mathbf{d}_1, \mathbf{m}_2] = \det[\mathbf{m}_0, \mathbf{m}_1, \mathbf{m}_2]$, which is equal to 1 by Theorem 2.

In addition, we use (28) again to decompose the first term and finally get

$$ \delta_T^0(\mathbf{m}_2, \mathbf{w}) = \delta_T^0(\mathbf{m}_2, a(-\mathbf{d}_0)) + \delta_T^0(\mathbf{m}_2, b(\mathbf{d}_1)) + \delta_T^0(\mathbf{m}_2, c\mathbf{m}_2) \\ + 2ab((-\mathbf{d}_0) \cdot \mathbf{d}_1) + 2(a(-\mathbf{d}_0) + b\mathbf{d}_1) \cdot c\mathbf{m}_2. $$

We can now prove that each term of the sum is positive:

* For the first term, we consider the ball whose border passes through $\mathbf{T}$ and $\mathbf{v}_0 + \mathbf{u}$. If $a = 0$, the point $\mathbf{v}_0 + a(-\mathbf{d}_0) = \mathbf{v}_0$ trivially belongs to the boundary of the ball, which implies a null term. If $a = 1$, we apply Lemma 21 with the vectors $(-\mathbf{d}_0)$, $\mathbf{d}_1$ and the origin set to $\mathbf{v}_2$ to deduce from $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \geq 0$ that the point $\mathbf{v}_2 + \mathbf{d}_1 + a(-\mathbf{d}_0) = \mathbf{v}_0 + a(-\mathbf{d}_0)$ does not belong to the interior of the ball, which means that $\delta_T^0(\mathbf{m}_2, a(-\mathbf{d}_0)) \geq 0$. For $a \geq 2$, we consider the ray from $\mathbf{v}_0$ in direction $-\mathbf{d}_0$ to show that we have the same result in that case too.

* The two next terms are also positive or null and we can verify this using Lemma 23 as in the proof of Lemma 28 (first item).

* The fourth term is positive because $a, b$ and $(-\mathbf{d}_0) \cdot \mathbf{d}_1$ are assumed to be positive.

* For the sign of the last term, it is enough to note that $(-\mathbf{d}_0) \cdot \mathbf{d}_1 \geq 0$ also implies $\mathbf{m}_2 \cdot (-\mathbf{d}_0) > 0$ and $\mathbf{m}_2 \cdot \mathbf{d}_1 > 0$ by Lemma 18. As a consequence, the term $(a(-\mathbf{d}_0) + b\mathbf{d}_1) \cdot c\mathbf{m}_2$ develops into two positive scalar products and is therefore positive. □

# 6. Conclusion

We introduce the Delaunay property for plane-probing algorithms and prove that the L-algorithm verifies the Delaunay property. We invoke several geometry properties related to projections and spheres in order to proceed to the proof by recurrence. Since L-algorithm verifies the Delaunay property, a direct consequence is that the output triangle contains a minimal basis for the underlying rank-two translated lattice. We also show that such minimal basis provides a raw estimation of the bound for the distance between the vertex of the last triangle to the fixed apex of tetrahedron.

As for future work, our study serves as a basis for the study of the locality for the L-algorithm. The progress of the algorithm depends on every point that it visits during the iteration. We hope that we can find a bound for the convex hull of every point visited by the algorithm in order to optimize the performance of the algorithm on digital surfaces. On the other hand, we also wish to understand theoretically how the R-algorithm always returns the same acute or right triangle as the L-algorithm without verifying the Delaunay property.
CRediT authorship contribution statement

**Jui-Ting Lu:** Writing – original draft, Writing – review & editing. **Tristan Roussillon:** Writing – original draft, Writing – review & editing. **Jacques-Olivier Lachaud:** Writing – review & editing. **David Coeurjolly:** Writing – original draft, Writing – review & editing.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Data availability

No data was used for the research described in the article.

Acknowledgements

This work was supported by PARADIS ANR-18-CE23-0007-01 research grant. Furthermore, we sincerely appreciate the valuable feedbacks from the reviewers, which undoubtedly contributes to the improvement of this paper.

Appendix A. Relation between the preorder and the intersection of balls and half-spaces

In this section, we focus on a step $i \in \{0, ..., n-1\}$ and ignore the exponent (i) in the notations. Our goal is to show that $\leq_T$ is a total preorder on $H_+$. For any pair $x,y \subset H_+$, we remind that $y \leq_T x$ if and only if $(B(T,y) \cap H_+) \subseteq (B(T,x) \cap H_+)$.

• Reflexivity: the ball defined by T and $x \in H_+$ is unique, thus $(B(T,x) \cap H_+) \subseteq (B(T,x) \cap H_+)$.

• Transitivity: it is induced by the transitivity of the order $\subseteq$.

• Totality: $\leq_T$ is total if $(B(T,y) \cap H_+) \subseteq (B(T,x) \cap H_+)$ or $(B(T,x) \cap H_+) \subseteq (B(T,y) \cap H_+)$ for all $x,y \in H_+$. We have two cases according to the pair $x,y$:

- if $B(T,x) = B(T,y)$, both alternatives are obviously true.

- if $B(T,x) \neq B(T,y)$, the intersection of the boundaries of the two balls is a curve lying in a plane, which is by definition, the one containing T. Since $H_+$ does not contain that plane, we necessarily have either $(B(T,y) \cap H_+) \subseteq (B(T,x) \cap H_+)$ or $(B(T,x) \cap H_+) \subseteq (B(T,y) \cap H_+)$.

Remark 31. The preorder is not antisymmetric because there exist co-spherical cases where $x \neq y$ but $B(T,x) = B(T,y)$.

Lemma 32. For all $x, y \in H_+$, if $(B(T, y) \cap H_+) \subseteq (B(T, x) \cap H_+)$, then $(B(T, x) \cap H_-) \subseteq (B(T, y) \cap H_-)$.

Proof. Again, we have two cases according to the pair $x, y$:

• if $B(T,x) = B(T,y)$, the statement is obviously true.

• if $B(T,x) \neq B(T,y)$, we first note that we can symmetrically define a total preorder with $H_-$ instead of $H_+$, which means that there are only two possible cases: either $(B(T,x) \cap H_-) \subseteq (B(T,y) \cap H_-)$ or $(B(T,y) \cap H_-) \subseteq (B(T,x) \cap H_-)$. We now show by contradiction that the second one is impossible. Indeed, if we have the two following inclusions

$$ (B(T, y) \cap H_+) \subseteq (B(T, x) \cap H_+), $$

$$ (B(T, y) \cap H_-) \subseteq (B(T, x) \cap H_-), $$

by taking the union of both sides of the inclusions, we obtain $B(T,y) \subseteq B(T,x)$, which raises a contradiction as the two balls are assumed to be distinct and, by definition, intersect. $\square$

Appendix B. Derivations

In this section, we detail some elements of the technical proofs which are implied by Lemma 16.

In Lemma 18:

$$ \begin{align} (\hat{\mathbf{N}}(\mathbf{T}) \times (-\mathbf{d}_k)) \cdot \mathbf{m}_{k+2} &= (\hat{\mathbf{N}}(\mathbf{T}) \times (\mathbf{m}_{k+2} - \mathbf{m}_{k+1})) \cdot \mathbf{m}_{k+2} \tag{B.1} \\ &= -(\mathbf{m}_{k+1} \times \mathbf{m}_{k+2}) \cdot \hat{\mathbf{N}}(\mathbf{T}) \nonumber \\ &= -\hat{\mathbf{N}}_k \cdot \hat{\mathbf{N}}(\mathbf{T}). \nonumber \end{align} $$
And,

$$ \begin{aligned} & (\hat{\mathbf{N}}(\mathbf{T}) \times (\mathbf{d}_{k+1})) \cdot \mathbf{m}_{k+2} = (\hat{\mathbf{N}}(\mathbf{T}) \times (\mathbf{m}_{k+2} - \mathbf{m}_k)) \cdot \mathbf{m}_{k+2} \\ & = -(\mathbf{m}_k \times \mathbf{m}_{k+2}) \cdot \hat{\mathbf{N}}(\mathbf{T}) \tag{B.2} \\ & = \hat{\mathbf{N}}_{k+1} \cdot \hat{\mathbf{N}}(\mathbf{T}). \end{aligned} $$

In Lemma 19:

$$ \begin{aligned} & (\hat{\mathbf{N}}(\mathbf{T}) \times (-\mathbf{d}_k)) \cdot (\mathbf{d}_k + \mathbf{m}_k) = ((-\mathbf{d}_k) \times (\mathbf{d}_k + \mathbf{m}_k)) \cdot \hat{\mathbf{N}}(\mathbf{T}) \\ & = ((-\mathbf{d}_k) \times \mathbf{m}_k) \cdot \hat{\mathbf{N}}(\mathbf{T}) \tag{B.3} \\ & = ((-\mathbf{m}_{k+1} + \mathbf{m}_{k+2}) \times \mathbf{m}_k) \cdot \hat{\mathbf{N}}(\mathbf{T}) \\ & = (\hat{\mathbf{N}}_{k+2} + \hat{\mathbf{N}}_{k+1}) \cdot \hat{\mathbf{N}}(\mathbf{T}). \end{aligned} $$

And,

$$ \begin{aligned} & (\hat{\mathbf{N}}(\mathbf{T}) \times \mathbf{d}_{k+1}) \cdot (\mathbf{d}_k + \mathbf{m}_k) = (\hat{\mathbf{N}}(\mathbf{T}) \times \mathbf{d}_{k+1}) \cdot (-\mathbf{d}_{k+1} + \mathbf{m}_{k+1}) \\ & = (\hat{\mathbf{N}}(\mathbf{T}) \times \mathbf{d}_{k+1}) \cdot (\mathbf{m}_{k+1}) \\ & = (\mathbf{d}_{k+1} \times (\mathbf{m}_{k+1})) \cdot \hat{\mathbf{N}}(\mathbf{T}) \tag{B.4} \\ & = ((\mathbf{m}_{k+2} - \mathbf{m}_k) \times (\mathbf{m}_{k+1})) \cdot \hat{\mathbf{N}}(\mathbf{T}) \\ & = (-\hat{\mathbf{N}}_{k+2} - \hat{\mathbf{N}}_k)) \cdot \hat{\mathbf{N}}(\mathbf{T}). \end{aligned} $$

For Lemma 20:

$$ \begin{aligned} & ((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times (\mathbf{d}_k + \mathbf{m}_k)) \cdot (-\mathbf{d}_{k+1}) = ((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times (\mathbf{m}_{k+1} - \mathbf{d}_{k+1})) \cdot (-\mathbf{d}_{k+1}) \\ & = ((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times (\mathbf{m}_{k+1})) \cdot (-\mathbf{d}_{k+1}) \\ & = ((\mathbf{m}_{k+1}) \times (-\mathbf{d}_{k+1})) \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = ((\mathbf{m}_{k+1}) \times (-\mathbf{m}_{k+2} + \mathbf{m}_k)) \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = (-\hat{\mathbf{N}}_k - \hat{\mathbf{N}}_{k+2}) \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = -(\hat{\mathbf{N}}_k \cdot \hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_k \cdot \hat{\mathbf{N}}_{k+2} + \hat{\mathbf{N}}_{k+2} \cdot \hat{\mathbf{N}}_{k+1} + \|\hat{\mathbf{N}}_{k+2}\|^2). \end{aligned} $$

And,

$$ \begin{aligned} & ((\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \times \mathbf{m}_k) \cdot (-\mathbf{d}_{k+1}) = (\mathbf{m}_k \times (-\mathbf{d}_{k+1})) \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = (\mathbf{m}_k \times (-\mathbf{m}_{k+2} + \mathbf{m}_k)) \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = \hat{\mathbf{N}}_{k+1} \cdot (\hat{\mathbf{N}}_{k+1} + \hat{\mathbf{N}}_{k+2}) \\ & = (\|\hat{\mathbf{N}}_{k+1}\|^2 + \hat{\mathbf{N}}_{k+1} \cdot \hat{\mathbf{N}}_{k+2}). \end{aligned} \tag{B.6} $$

## References

[1] T. Hildebrand, A. Laib, R. Müller, J. Dequeker, P. Rüegsegger, Direct three-dimensional morphometric analysis of human cancellous bone: microstructural data from spine, femur, iliac crest, and calcaneus, J. Bone Miner. Res. 14 (7) (1999) 1167-1174.

[2] F. Flin, J.B. Brzoska, B. Lesaffre, C. Coléou, P. Lamboley, D. Coeurjolly, O. Teytaud, G. Vignoles, J.F. Delesse, An adaptive filtering method to evaluate normal vectors and surface areas of 3d objects. Application to snow images from x-ray tomography, IEEE Trans. Image Process. 14 (5) (2005) 585-596.

[3] J. Dardenne, S. Valette, N. Siauve, N. Burais, R. Prost, Variational tetrahedral mesh generation from discrete volume data, Vis. Comput. 25 (5-7) (2009) 401-410.

[4] V. Brimkov, D. Coeurjolly, R. Klette, Digital planarity—A review, Discrete Appl. Math. 155 (4) (2007) 468-495.

[5] I. Debled-Rrennesson, J. Reveillaés, An incremental algorithm for digital plane recognition, in: Proc. Discrete Geometry for Computer Imagery, 1994, pp. 194-205.

[6] Y. Gérard, I. Debled-Rrennesson, P. Zimmermann, An elementary digital plane recognition algorithm, Discrete Appl. Math. 151 (1) (2005) 169-183.

[7] L. Buzer, A linear incremental algorithm for naive and standard digital lines and planes recognition, Graph. Models 65 (1) (2003) 61-76, https://doi.org/10.1016/S1524-0703(03)00008-0, special Issue: Discrete Topology and Geometry for Image and Object Representation.

[8] J. Luel, J.-O. Lachaud, Q. Mérigot, B. Thibert, Robust geometry estimation using the generalized Voronoi covariance measure, SIAM J. Imaging Sci. 8 (2) (2015) 1293-1314.

[9] D. Coeurjolly, J.-O. Lachaud, J. Levallois, Integral based curvature estimators in digital geometry, in: R. Gonzalez-Diaz, M.-J. Jimenez, B. Medrano (Eds.), 17th International Conference on Discrete Geometry for Computer Imagery (DGCI 2013), Seville, Spain, vol. 7749, Springer Verlag, Spain, 2013, pp. 215-227.

[10] J.-O. Lachaud, X. Provençal, T. Roussillon, An output-sensitive algorithm to compute the normal vector of a digital plane, Theor. Comput. Sci. 624 (2016) 73-88.

[11] J.-O. Lachaud, X. Provençal, T. Roussillon, Computation of the normal vector to a digital plane by sampling significant points, in: 19th IAPR International Conference on Discrete Geometry for Computer Imagery, Nantes, France, 2016.

[12] J.-O. Lachaud, X. Provençal, T. Roussillon, Two plane-probing algorithms for the computation of the normal vector to a digital plane, J. Math. Imaging Vis. 59 (1) (2017) 23-39.

[13] J.-T. Lu, T. Roussillon, D. Coeurjolly, A new lattice-based plane-probing algorithm, in: E. Baudrier, B. Naegel, A. Krähenbühl, M. Tajine (Eds.), Second International Conference on Discrete Geometry and Mathematical Morphology (DGMM 2022), in: Lecture Notes in Computer Science, Springer Verlag, 2022.
[14] T. Roussillon, J.-O. Lachaud, Delaunay properties of digital straight segments, in: I. Debled-Rrennesson, E. Domenjoud, B. Kerautret, P. Even (Eds.), Discrete Geometry for Computer Imagery, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 308–319.

[15] J.-P. Reveillès, Géométrie discrète, calculs en nombres entiers et algorithmique, Thèse d'etat, Université Louis Pasteur, 1991.

[16] J.-O. Lachaud, J. Meyron, T. Roussillon, An optimized framework for plane-probing algorithms, J. Math. Imaging Vis. 62 (2020) 718–736.

[17] P.Q. Nguyen, The LLL Algorithm: Survey and Applications, Information Security and Cryptography, Springer, 2009, Ch. Hermite's Constant and Lattice Algorithms.

[18] T. Roussillon, J.-O. Lachaud, Digital plane recognition with fewer probes, in: M. Couprie, J. Cousty, Y. Kenmochi, N. Mustafa (Eds.), 21st IAPR International Conference on Discrete Geometry for Computer Imagery, in: Lecture Notes in Computer Science, Couprie, vol. 11414, Springer, Cham, Marne-la-Vallée, France, 2019, pp. 380–393.