# Full Convexity for Polyhedral Models in Digital Spaces

Fabien Feschet, Jacques-Olivier Lachaud

► To cite this version:

Fabien Feschet, Jacques-Olivier Lachaud. Full Convexity for Polyhedral Models in Digital Spaces. DGMM 2022 - IAPR Second International Conference on Discrete Geometry and Mathematical Morphology, Étienne Baudrier, Benoît Naegel, Adrien Krähenbühl, Mohamed Tajine, Oct 2022, Strasbourg, France. pp.98-109, 10.1007/978-3-031-19897-7_9. hal-03823832

HAL Id: hal-03823832

https://hal.science/hal-03823832

Submitted on 10 Jun 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Full Convexity for Polyhedral Models in Digital Spaces

Fabien Feschet, Jacques-Olivier Lachaud

► To cite this version:

Fabien Feschet, Jacques-Olivier Lachaud. Full Convexity for Polyhedral Models in Digital Spaces. DGMM 2022 - IAPR Second International Conference on Discrete Geometry and Mathematical Morphology, Étienne Baudrier, Benoît Naegel, Adrien Krähenbühl, Mohamed Tajine, Oct 2022, Strasbourg, France. pp.98-109, 10.1007/978-3-031-19897-7_9. hal-03823832

HAL Id: hal-03823832

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

Submitted on 10 Jun 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_1.png" /></figure>
# Full convexity for polyhedral models in digital spaces*

Fabien Feschet¹[0000-0001-5178-0842] and Jacques-Olivier Lachaud²[0000-0003-4236-2133]

¹ Université Clermont Auvergne, CNRS, ENSMSE, LIMOS, F-63000 Clermont-Ferrand, France
fabien.feschet@u-auvergne.fr

² Université Savoie Mont Blanc, CNRS, LAMA, F-73000 Chambéry, France
jacques-olivier.lachaud@univ-smb.fr

**Abstract.** In a recent work, *full convexity* has been proposed as an alternative definition of digital convexity. It solves many problems related to its usual definitions, for instance: fully convex sets are digitally convex in the usual sense, but are also connected and simply connected. However, full convexity is not a monotone property hence intersections of fully convex sets may be neither fully convex nor connected. This defect might forbid digital polyhedral models with fully convex faces and edges. This can be detrimental since classical standard and naive planes are fully convex. We propose in this paper an *envelope operator* which solves in arbitrary dimension the problem of extending a digital set into a fully convex set. This extension naturally leads to digital polyhedra whose cells are fully convex. We present first a generic envelope operator which add points in required directions in parallel and prove that it builds a fully convex set. Then a relative envelope operator is proposed, which can be used to force digital planarity of fully convex sets. We provide experiments showing that our method produces coherent polyhedral models for any polyhedron in arbitrary dimension.

**Keywords:** Digital geometry · Digital convexity · Polyhedral model

## 1 Introduction

Convexity is a classical property in various domains of mathematics and computer science. It allows for instance guarantees for optimization, containment property via its separability with hyperplanes, and many convergence results in real or discrete analysis need convexity assumptions. While it has been primarily developed in $\mathbb{R}^d$, several extensions have been proposed in the past. Two main paths are possible for extending convexity: either going more abstract to adapt convexity to generic spaces or building more specialized versions for dedicated spaces like the digital space $\mathbb{Z}^d$ for instance. Most general extensions of convexity

<footnote>* This work has been partly funded by COMEDIC ANR-15-CE40-0006 research grant.</footnote>
# Full convexity for polyhedral models in digital spaces*

Fabien Feschet¹[0000-0001-5178-0842] and Jacques-Olivier Lachaud²[0000-0003-4236-2133]

¹ Université Clermont Auvergne, CNRS, ENSMSE, LIMOS, F-63000 Clermont-Ferrand, France
fabien.feschet@u-auvergne.fr

² Université Savoie Mont Blanc, CNRS, LAMA, F-73000 Chambéry, France
jacques-olivier.lachaud@univ-smb.fr

**Abstract.** In a recent work, full convexity has been proposed as an alternative definition of digital convexity. It solves many problems related to its usual definitions, for instance: fully convex sets are digitally convex in the usual sense, but are also connected and simply connected. However, full convexity is not a monotone property hence intersections of fully convex sets may be neither fully convex nor connected. This defect might forbid digital polyhedral models with fully convex faces and edges. This can be detrimental since classical standard and naive planes are fully convex. We propose in this paper an envelope operator which solves in arbitrary dimension the problem of extending a digital set into a fully convex set. This extension naturally leads to digital polyhedra whose cells are fully convex. We present first a generic envelope operator which add points in required directions in parallel and prove that it builds a fully convex set. Then a relative envelope operator is proposed, which can be used to force digital planarity of fully convex sets. We provide experiments showing that our method produces coherent polyhedral models for any polyhedron in arbitrary dimension.

**Keywords:** Digital geometry · Digital convexity · Polyhedral model

## 1 Introduction

Convexity is a classical property in various domains of mathematics and computer science. It allows for instance guarantees for optimization, containment property via its separability with hyperplanes, and many convergence results in real or discrete analysis need convexity assumptions. While it has been primarily developed in $\mathbb{R}^d$, several extensions have been proposed in the past. Two main paths are possible for extending convexity: either going more abstract to adapt convexity to generic spaces or building more specialized versions for dedicated spaces like the digital space $\mathbb{Z}^d$ for instance. Most general extensions of convexity

<footnote>* This work has been partly funded by COMEDIC ANR-15-CE40-0006 research grant.</footnote>
rely on hull systems [Lau06], K-convexity and simplicial convexity [Lli02] or closure (hull) operators [And06]. Those general extensions do not necessarily embed a geometric vision of convexity, so convex sets do not have a geometric structure in the same veins as in $\mathbb{R}^d$. More resembling extensions rely on anti-matroids notably with the anti-exchange property [RS03] or cellular extensions based on discrete hyperplanes [Web01,RS03]. They induce spaces of convex sets with more geometric interpretations, but also fail to be connected in some situations. Several extensions have also been proposed in the optimization community using convexity and digital convexity as certificates of optimality [MS01]. For digital spaces $\mathbb{Z}^d$, digital convexity was first defined as the intersection of real convex sets of $\mathbb{R}^d$ with $\mathbb{Z}^d$ (e.g. see survey [Ron89]). Many works have then tried to enforce the connectedness of such sets, for instance by relying on digital lines [KR82b,Eck01] or extensions of digital functions [Kis04]. Most works are limited to 2D, and 3D extensions do not solve all geometric issues [KR82a].

This paper considers the recently introduced notion of *full convexity* [Lac21,Lac22]. It extends digital convex sets while enforcing connectedness of fully convex sets. This notion is also computational in the sense that verifying full convexity is an easy task. Furthermore classical standard and naive planes are fully convex, so this convexity is appealing for building polyhedral models in any dimensions. However, since intersections of fully convex sets are not always fully convex, full convexity cannot be used directly for building faces and edges of polyhedra. Indeed the full convexity does not verify the monotonicity property of classical hull operators and thus fully convex hull is not a properly defined hull operator. This is a problem if we wish to build digital polyhedra in arbitrary dimension. In 3D, graceful lines and planes have been proposed in [BB02] to define edges consistent with triangular faces. It permits to fix varying arithmetical thickness between interior and boundary of digital triangles by construction but it is limited to 3D.

Our objective is to define polyhedral models in digital space $\mathbb{Z}^d$ which are based on full convexity. Our proposal lets us freely choose the thickness of digital faces, is canonic in arbitrary dimension, and benefits from the nice properties of fully convex sets. Indeed, naive, standard or even thicker pieces of arithmetical planes can be reconstructed in the proposed unified framework.

We start by defining the *fully convex envelope*, that is a pre-hull operator without the monotonicity property, which builds a fully convex set containing the input digital set. Our process is iterative, fully parallel at each iteration and ends after a finite number of iterations. It uses solely classical operators in the cubical complex $\mathcal{C}^d$ associated to $\mathbb{Z}^d$. We then adapt it to define a fully convex enveloppe *relative to another fully convex set*. Since thick enough digital planes are known to be fully convex, we can define fully convex subsets of digital planes in arbitrary dimension. The simultaneous use of those two operators builds edges and faces for meshes with planar faces or meshes with non planar faces. Experiments show that the induced *polyhedral models* are visually appealing and preserve the connectivity graphs between faces and edges of original models.
rely on hull systems [Lau06], K-convexity and simplicial convexity [Lli02] or closure (hull) operators [And06]. Those general extensions do not necessarily embed a geometric vision of convexity, so convex sets do not have a geometric structure in the same veins as in $\mathbb{R}^d$. More resembling extensions rely on anti-matroids notably with the anti-exchange property [RS03] or cellular extensions based on discrete hyperplanes [Web01,RS03]. They induce spaces of convex sets with more geometric interpretations, but also fail to be connected in some situations. Several extensions have also been proposed in the optimization community using convexity and digital convexity as certificates of optimality [MS01]. For digital spaces $\mathbb{Z}^d$, digital convexity was first defined as the intersection of real convex sets of $\mathbb{R}^d$ with $\mathbb{Z}^d$ (e.g. see survey [Ron89]). Many works have then tried to enforce the connectedness of such sets, for instance by relying on digital lines [KR82b,Eck01] or extensions of digital functions [Kis04]. Most works are limited to 2D, and 3D extensions do not solve all geometric issues [KR82a].

This paper considers the recently introduced notion of *full convexity* [Lac21,Lac22]. It extends digital convex sets while enforcing connectedness of fully convex sets. This notion is also computational in the sense that verifying full convexity is an easy task. Furthermore classical standard and naive planes are fully convex, so this convexity is appealing for building polyhedral models in any dimensions. However, since intersections of fully convex sets are not always fully convex, full convexity cannot be used directly for building faces and edges of polyhedra. Indeed the full convexity does not verify the monotonicity property of classical hull operators and thus fully convex hull is not a properly defined hull operator. This is a problem if we wish to build digital polyhedra in arbitrary dimension. In 3D, graceful lines and planes have been proposed in [BB02] to define edges consistent with triangular faces. It permits to fix varying arithmetical thickness between interior and boundary of digital triangles by construction but it is limited to 3D.

Our objective is to define polyhedral models in digital space $\mathbb{Z}^d$ which are based on full convexity. Our proposal lets us freely choose the thickness of digital faces, is canonic in arbitrary dimension, and benefits from the nice properties of fully convex sets. Indeed, naive, standard or even thicker pieces of arithmetical planes can be reconstructed in the proposed unified framework.

We start by defining the *fully convex envelope*, that is a pre-hull operator without the monotonicity property, which builds a fully convex set containing the input digital set. Our process is iterative, fully parallel at each iteration and ends after a finite number of iterations. It uses solely classical operators in the cubical complex $\mathscr{C}^d$ associated to $\mathbb{Z}^d$. We then adapt it to define a fully convex enveloppe *relative to another fully convex set*. Since thick enough digital planes are known to be fully convex, we can define fully convex subsets of digital planes in arbitrary dimension. The simultaneous use of those two operators builds edges and faces for meshes with planar faces or meshes with non planar faces. Experiments show that the induced *polyhedral models* are visually appealing and preserve the connectivity graphs between faces and edges of original models.
# 2 Full convexity and fully convex envelope

## 2.1 Definitions

**Cubical cell complex.** We consider the (cubical) cell complex $\mathscr{C}^d$ induced by the lattice $\mathbb{Z}^d$, such that its 0-cells are the points of $\mathbb{Z}^d$, its 1-cells are the open unit segments joining two 0-cells at distance 1, its 2-cells are the open unit squares formed by these segments, ..., and its $d$-cells are the $d$-dimensional unit hypercubes with vertices in $\mathbb{Z}^d$. We denote $\mathscr{C}_k^d$ the set of its $k$-cells. We call *complex/subcomplex* any subset of cells of $\mathscr{C}^d$, e.g. any single cell is a subcomplex. A *digital set* is a subset of $\mathbb{Z}^d$.

The (topological) boundary $\partial Y$ of a subset $Y$ of $\mathbb{R}^d$ is the set of points in its closure but not in its interior. The star of a cell $\sigma$ in $\mathscr{C}^d$, denoted by $\mathrm{Star}(\sigma)$, is the set of cells of $\mathscr{C}^d$ whose boundary contains $\sigma$ and it contains the cell $\sigma$ itself. The closure $\mathrm{Cl}(\sigma)$ of $\sigma$ contains $\sigma$ and all the cells in its boundary. We extend these definitions to any subcomplex $K$ of $\mathscr{C}^d$ by taking unions:

$$ \mathrm{Star}(K) := \bigcup_{\sigma \in K} \{\mathrm{Star}(\sigma)\}, $$

$$ \mathrm{Cl}(K) := \bigcup_{\sigma \in K} \{\mathrm{Cl}(\sigma)\}. $$

In combinatorial topology, a subcomplex $K$ with $\mathrm{Star}(K) = K$ is open, while being closed when $\mathrm{Cl}(K) = K$. The body of a subcomplex $K$, i.e. the union of its cells in $\mathbb{R}^d$, is written $\|K\|$. We denote by $\mathrm{Extr}(K) = \mathrm{Cl}(K) \cap \mathbb{Z}^d$.

**Intersection complex.** If $Y$ is any subset of the Euclidean space $\mathbb{R}^d$, we denote by $\tilde{\mathscr{C}}_k^d[Y]$ the set of $k$-cells whose topological closure intersects $Y$, i.e.

$$ \tilde{\mathscr{C}}_k^d[Y] := \{c \in \mathscr{C}_k^d, \bar{c} \cap Y \neq \emptyset\}. \quad (1) $$

The complex that is the union of all, $\tilde{\mathscr{C}}_k^d[Y]$, $0 \le k \le d$, is called the intersection (cubical) complex of $Y$ and is denoted by $\tilde{\mathscr{C}}^d[Y]$.

It is worth to note that, for any complex $K$, $\mathrm{Star}(K) = \tilde{\mathscr{C}}_k^d[\|K\|]$. Hence, for any subset $Y \subset \mathbb{R}^d$, it is natural to define $\mathrm{Star}(Y) := \tilde{\mathscr{C}}_k^d[Y]$, which coincides with the standard definition of star on subsets of $\mathscr{C}^d$ or $\mathbb{Z}^d$.

**Skeleton.** We define a kind of converse operation to the star. For any complex $K \subset \mathscr{C}^d$, the skeleton of $K$ is (with $K'$ any subset of $K$)

$$ \mathrm{Skel}(K) := \bigcap_{K' \subset K \subset \mathrm{Star}(K')} K'. \quad (2) $$

**Lemma 1** For any complex $K$, $K \subset \mathrm{Star}(\mathrm{Skel}(K))$.

**Lemma 2** For any digital set $X$ we have $\mathrm{Skel}(\mathrm{Star}(X)) = X$ using lemma (1).

**Lemma 3** For any open complex $K$, $\mathrm{Star}(\mathrm{Skel}(K)) = K$.

*Proof.* ($\supset$) $K \subset \mathrm{Star}(\mathrm{Skel}(K))$ by lemma (1).

($\subset$) $\mathrm{Skel}(K) \subset K$ because $\mathrm{Skel}(K)$ is the intersection of subsets of $K$. $\mathrm{Star}()$ being increasing, $\mathrm{Star}(\mathrm{Skel}(K)) \subset \mathrm{Star}(K) = K$ since $K$ is open.
# 2 Full convexity and fully convex envelope

## 2.1 Definitions

*Cubical cell complex.* We consider the (cubical) cell complex $\mathscr{C}^d$ induced by the lattice $\mathbb{Z}^d$, such that its 0-cells are the points of $\mathbb{Z}^d$, its 1-cells are the open unit segments joining two 0-cells at distance 1, its 2-cells are the open unit squares formed by these segments, ..., and its $d$-cells are the $d$-dimensional unit hypercubes with vertices in $\mathbb{Z}^d$. We denote $\mathscr{C}_k^d$ the set of its $k$-cells. We call *complex/subcomplex* any subset of cells of $\mathscr{C}^d$, e.g. any single cell is a subcomplex. A *digital set* is a subset of $\mathbb{Z}^d$.

The (topological) boundary $\partial Y$ of a subset $Y$ of $\mathbb{R}^d$ is the set of points in its closure but not in its interior. The star of a cell $\sigma$ in $\mathscr{C}^d$, denoted by $\mathrm{Star}(\sigma)$, is the set of cells of $\mathscr{C}^d$ whose boundary contains $\sigma$ and it contains the cell $\sigma$ itself. The closure $\mathrm{Cl}(\sigma)$ of $\sigma$ contains $\sigma$ and all the cells in its boundary. We extend these definitions to any subcomplex $K$ of $\mathscr{C}^d$ by taking unions:

$$ \mathrm{Star}(K) := \bigcup_{\sigma \in K} \{\mathrm{Star}(\sigma)\}, $$

$$ \mathrm{Cl}(K) := \bigcup_{\sigma \in K} \{\mathrm{Cl}(\sigma)\}. $$

In combinatorial topology, a subcomplex $K$ with $\mathrm{Star}(K) = K$ is open, while being closed when $\mathrm{Cl}(K) = K$. The body of a subcomplex $K$, i.e. the union of its cells in $\mathbb{R}^d$, is written $\|K\|$. We denote by $\mathrm{Extr}(K) = \mathrm{Cl}(K) \cap \mathbb{Z}^d$.

*Intersection complex.* If $Y$ is any subset of the Euclidean space $\mathbb{R}^d$, we denote by $\tilde{\mathscr{C}}_k^d[Y]$ the set of $k$-cells whose topological closure intersects $Y$, i.e.

$$ \tilde{\mathscr{C}}_k^d[Y] := \{c \in \mathscr{C}_k^d, \bar{c} \cap Y \neq \emptyset\}. \quad (1) $$

The complex that is the union of all, $\tilde{\mathscr{C}}_k^d[Y]$, $0 \le k \le d$, is called the intersection (cubical) complex of $Y$ and is denoted by $\tilde{\mathscr{C}}^d[Y]$.

It is worth to note that, for any complex $K$, $\mathrm{Star}(K) = \tilde{\mathscr{C}}^d[\|K\|]$. Hence, for any subset $Y \subset \mathbb{R}^d$, it is natural to define $\mathrm{Star}(Y) := \tilde{\mathscr{C}}^d[Y]$, which coincides with the standard definition of star on subsets of $\mathscr{C}^d$ or $\mathbb{Z}^d$.

*Skeleton.* We define a kind of converse operation to the star. For any complex $K \subset \mathscr{C}^d$, the skeleton of $K$ is (with $K'$ any subset of $K$)

$$ \mathrm{Skel}(K) := \bigcap_{K' \subset K \subset \mathrm{Star}(K')} K'. \quad (2) $$

**Lemma 1** For any complex $K$, $K \subset \mathrm{Star}(\mathrm{Skel}(K))$.

**Lemma 2** For any digital set $X$ we have $\mathrm{Skel}(\mathrm{Star}(X)) = X$ using lemma (1).

**Lemma 3** For any open complex $K$, $\mathrm{Star}(\mathrm{Skel}(K)) = K$.

*Proof.* ($\supset$) $K \subset \mathrm{Star}(\mathrm{Skel}(K))$ by lemma (1).

($\subset$) $\mathrm{Skel}(K) \subset K$ because $\mathrm{Skel}(K)$ is the intersection of subsets of $K$. $\mathrm{Star}()$ being increasing, $\mathrm{Star}(\mathrm{Skel}(K)) \subset \mathrm{Star}(K) = K$ since $K$ is open.
## 2.2 Full convexity

For a set $A \subset \mathbb{R}^d$, its convex hull $\text{CvxH}(A)$ is the intersection of all convex sets that contains $A$.

**Definition 1 (Full convexity)** A digital set $X \subset \mathbb{Z}^d$ is digitally $k$-convex for $0 \le k \le d$ whenever

$$ \tilde{\mathcal{C}}_k^d[X] = \tilde{\mathcal{C}}_k^d[\text{CvxH}(X)]. \quad (3) $$

Subset $X$ is fully (digitally) convex if it is digitally $k$-convex for all $k, 0 \le k \le d$.

The following characterization will be useful:

**Lemma 4** A digital set $X$ is fully convex iff $\text{Star}(X) = \text{Star}(\text{CvxH}(X))$.

## 2.3 Fully convex envelope

Convex hull is one of the most fundamental tool in continuous geometry. We wish to design a digital analogue to convex hull. The question is then how to build a fully convex set from an arbitrary digital subset of $\mathbb{Z}^d$. For instance can we build this fully convex envelope with intersections of fully convex set? We do have this rather straightforward property:

**Lemma 5** If $A$ and $B$ are digitally $0$-convex, then $A \cap B$ is digitally $0$-convex.

*Proof.*

$$ \begin{aligned} \text{CvxH}(A \cap B) \cap \mathbb{Z}^d &\subset \text{CvxH}(A) \cap \text{CvxH}(B) \cap \mathbb{Z}^d \quad (\text{CvxH}(\cdot) \text{ is increasing}) \\ &= A \cap B \quad (A \text{ and } B \text{ are digitally } 0\text{-convex}) \end{aligned} $$

□

However, intersections of fully convex sets are gener-
ally not fully convex. As a very simple example, just pick
$A = \{(0,0), (1,1), (2,1)\}$ and $B = \{(0,0), (1,0), (2,1)\}$,
which are both fully convex. Then the set $A \cap B =$
$\{(0,0), (2,1)\}$ is not fully convex, not even connected.

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

Therefore, we propose another way to build a fully
convex set from an arbitrary digital set, which uses the
cells intersected by the convex hull of this set, and which is defined through an
iterative process.

Each iteration composes these operations, for $X \subset \mathbb{R}^d$:

$$ \text{FC}(X) := \text{Extr} (\text{Skel}(\text{Star}(\text{CvxH}(X)))) $$

First the Euclidean convex hull of the set is computed, letting $Y = \text{CvxH}(X)$, then its covering $\text{Star}(Y)$ by cells of the cellular grid is determined. The skeleton of these cells is their smallest subset such that $\text{Star}(\text{Skel}(\text{Star}(Y))) = Y$. Finally $\text{FC}(X)$ is composed of the grid vertices of the skeleton cells. The last operation implies that $\text{FC}(X) \subset \mathbb{Z}^d$. Refer to Figure 1 for an illustration of FC operation and fully convex envelope computation.
## 2.2 Full convexity

For a set $A \subset \mathbb{R}^d$, its convex hull $\text{CvxH}(A)$ is the intersection of all convex sets that contains $A$.

**Definition 1 (Full convexity)** A digital set $X \subset \mathbb{Z}^d$ is digitally $k$-convex for $0 \le k \le d$ whenever

$$ \tilde{\mathcal{C}}_k^d[X] = \tilde{\mathcal{C}}_k^d[\text{CvxH}(X)]. \quad (3) $$

Subset $X$ is fully (digitally) convex if it is digitally $k$-convex for all $k, 0 \le k \le d$.

The following characterization will be useful:

**Lemma 4** A digital set $X$ is fully convex iff $\text{Star}(X) = \text{Star}(\text{CvxH}(X))$.

## 2.3 Fully convex envelope

Convex hull is one of the most fundamental tool in continuous geometry. We wish to design a digital analogue to convex hull. The question is then how to build a fully convex set from an arbitrary digital subset of $\mathbb{Z}^d$. For instance can we build this fully convex envelope with intersections of fully convex set? We do have this rather straightforward property:

**Lemma 5** If $A$ and $B$ are digitally $0$-convex, then $A \cap B$ is digitally $0$-convex.

*Proof.*

$$ \begin{aligned} \text{CvxH}(A \cap B) \cap \mathbb{Z}^d &\subset \text{CvxH}(A) \cap \text{CvxH}(B) \cap \mathbb{Z}^d \quad (\text{CvxH}(\cdot) \text{ is increasing}) \\ &= A \cap B \quad (A \text{ and } B \text{ are digitally } 0\text{-convex}) \end{aligned} $$

□

However, intersections of fully convex sets are gener-
ally not fully convex. As a very simple example, just pick
$A = \{(0,0), (1,1), (2,1)\}$ and $B = \{(0,0), (1,0), (2,1)\}$,
which are both fully convex. Then the set $A \cap B =$
$\{(0,0), (2,1)\}$ is not fully convex, not even connected.

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

Therefore, we propose another way to build a fully
convex set from an arbitrary digital set, which uses the
cells intersected by the convex hull of this set, and which is defined through an
iterative process.

Each iteration composes these operations, for $X \subset \mathbb{R}^d$:

$$ \text{FC}(X) := \text{Extr} (\text{Skel}(\text{Star}(\text{CvxH}(X)))) $$

First the Euclidean convex hull of the set is computed, letting $Y = \text{CvxH}(X)$, then its covering $\text{Star}(Y)$ by cells of the cellular grid is determined. The skeleton of these cells is their smallest subset such that $\text{Star}(\text{Skel}(\text{Star}(Y))) = Y$. Finally $\text{FC}(X)$ is composed of the grid vertices of the skeleton cells. The last operation implies that $\text{FC}(X) \subset \mathbb{Z}^d$. Refer to Figure 1 for an illustration of FC operation and fully convex envelope computation.
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Illustration of FC operation and fully convex envelope construction. Left: input digital set $X$ and its convex hull, middle: Star (CvxH($X$)) (gray and thick black) and its skeleton (thick black), right: extremal points of the skeleton, i.e. $FC(X)$. Here $X$ is digitally 0-convex but not fully convex. $FC(X)$ is not even digitally 0-convex, while $FC(FC(X))$ is fully convex and is therefore the fully convex envelope to $X$.</figcaption></figure>

**Definition 2 (Fully convex envelope)** For any integer $n \ge 0$, the $n$-th convex envelope of $X \subset \mathbb{R}^d$ is the $n$ times composition of operation FC.

$$FC^n(X) := \underbrace{FC \circ \cdots \circ FC}_{n \text{ times}}(X).$$

The fully convex envelope of $X$ is the limit of $FC^n(X)$ when $n \to \infty$:

$$FC^*(X) := \lim_{n \to \infty} FC^n(X).$$

We have to show that this process has a limit for every subset $X$.

**Theorem 1** For any finite digital set $X \subset \mathbb{Z}^d$, there exists a finite $n$ such that $FC^n(X) = FC^{n+1}(X)$, which implies that $FC^*(X)$ exists and is equal to $FC^n(X)$.

It is the immediate consequence of Lemma 6 and Lemma 7 below: the first one tells that FC is increasing, the second that $X$ and $FC(X)$ have the same bounding box.

**Lemma 6** For any $X \subset \mathbb{Z}^d$, $X \subset FC(X)$.

*Proof.* Let $x \in X \subset \mathbb{Z}^d = \mathcal{C}_0^d$. Obviously $x \in \text{CvxH}(X)$. It follows that $x \in \text{Star}(\text{CvxH}(X))$ and, since $\text{Star}(\cdot)$ is idempotent, $\text{Star}(x) \subset \text{Star}(\text{CvxH}(X))$. The whole star of $x$ belonging to the subcomplex $K := \text{Star}(\text{CvxH}(X))$, the 0-cell $x$ belongs to the skeleton of $K$. Since all 0-cells of a subcomplex are extremal points, it is an extremal point of $\text{Skel}(K)$, which concludes. □
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Illustration of FC operation and fully convex envelope construction. Left: input digital set $X$ and its convex hull, middle: Star (CvxH($X$)) (gray and thick black) and its skeleton (thick black), right: extremal points of the skeleton, i.e. $FC(X)$. Here $X$ is digitally 0-convex but not fully convex. $FC(X)$ is not even digitally 0-convex, while $FC(FC(X))$ is fully convex and is therefore the fully convex envelope to $X$.</figcaption></figure>

**Definition 2 (Fully convex envelope)** For any integer $n \ge 0$, the $n$-th convex envelope of $X \subset \mathbb{R}^d$ is the $n$ times composition of operation FC.

$$FC^n(X) := \underbrace{FC \circ \cdots \circ FC}_{n \text{ times}}(X).$$

The fully convex envelope of $X$ is the limit of $FC^n(X)$ when $n \to \infty$:

$$FC^*(X) := \lim_{n \to \infty} FC^n(X).$$

We have to show that this process has a limit for every subset $X$.

**Theorem 1** For any finite digital set $X \subset \mathbb{Z}^d$, there exists a finite $n$ such that $FC^n(X) = FC^{n+1}(X)$, which implies that $FC^*(X)$ exists and is equal to $FC^n(X)$.

It is the immediate consequence of Lemma 6 and Lemma 7 below: the first one tells that FC is increasing, the second that $X$ and $FC(X)$ have the same bounding box.

**Lemma 6** For any $X \subset \mathbb{Z}^d$, $X \subset FC(X)$.

*Proof.* Let $x \in X \subset \mathbb{Z}^d = \mathcal{C}_0^d$. Obviously $x \in \text{CvxH}(X)$. It follows that $x \in \text{Star}(\text{CvxH}(X))$ and, since $\text{Star}(\cdot)$ is idempotent, $\text{Star}(x) \subset \text{Star}(\text{CvxH}(X))$. The whole star of $x$ belonging to the subcomplex $K := \text{Star}(\text{CvxH}(X))$, the 0-cell $x$ belongs to the skeleton of $K$. Since all 0-cells of a subcomplex are extremal points, it is an extremal point of $\text{Skel}(K)$, which concludes. □
**Lemma 7** For any finite $X \subset \mathbb{Z}^d$, $X$ and $\text{FC}(X)$ have the same bounding box.

*Proof.* Let $p \subset \mathbb{Z}^d$ be the lowest point of the axis-aligned bounding box of $X$, i.e. $\forall i, 1 \le i \le d, p^i = \min_{z \in X} z^i$. Obviously, it is also the lowest point of the bounding box of $\text{CvxH}(X)$. Let $K := \text{Star}(\text{CvxH}(X))$. Since $\forall x \in \text{CvxH}(X), p^i \le x^i$, any cell $c$ of $K$ that lie below point $q$ along some coordinate axis $j$ has a twin cell $e \in K$ in its boundary, such that $e$ is closed along coordinate $j$ and $e^j = p^j$. Continuing the argument along every coordinate axis $k$ where $e$ is below point $p$, we know that there is a digital point $z \in K$ in the boundary of $c$, such that $z$ is not below $p$. Point $z$ being a 0-cell it follows that $z \in \text{Skel}(K)$ while all $m$-cells incident to $z$, $m > 0$, are not in $\text{Skel}(K)$. We have just shown that no cells of $\text{Skel}(K)$ can be lower than $p$. The reasoning is the same for the uppermost point. $\square$

A first observation is that operation FC does not modify fully convex sets, so the fully convex envelope of a fully convex set $X$ is $X$ itself.

**Lemma 8** If $X \subset \mathbb{Z}^d$ is fully convex, then $\text{FC}(X) = X$. So $\text{FC}^*(X) = X$.

*Proof.* Indeed we have

$$ 
\begin{align*}
\text{FC}(X) &= \text{Extr}(\text{Skel}(\text{Star}(\text{CvxH}(X)))) \\
&= \text{Extr}(\text{Skel}(\text{Star}(X))) \tag*{(\text{Lemma 4})} \\
&= \text{Extr}(X) \tag*{(\text{Lemma 2})} \\
&= X \tag*{(X \subset \mathbb{Z}^d)}
\end{align*}
$$

$\square$

Reciprocally, non fully convex sets are modified through operation FC.

**Lemma 9** If $X \subset \mathbb{Z}^d$ is not fully convex, then $X \subsetneq \text{FC}(X)$

*Proof.* By Lemma 6 we already know that $X \subset \text{FC}(X)$. Let us show that there is a digital point $z \in \text{FC}(X)$ that is not in $X$. Since $X$ is not fully convex, there exists some cell $c \in \text{Star}(\text{CvxH}(X))$ such that $c \notin \text{Star}(X)$. It is possible that there are other cells $c'$ in $\bar{c}$ such that $c' \in \text{Star}(\text{CvxH}(X))$ and $c' \notin \text{Star}(X)$. In this case we pick one, say $b$, with lowest dimension.

Let $z \in \bar{b} \cap \mathbb{Z}^d$ be a grid vertex of this cell (which may be $b$ itself). Then $z \notin X$. Otherwise, $\text{Star}(z) \subset \text{Star}(X)$, hence the cell $b$, which belongs to $\text{Star}(z)$ (through the equivalence $z \subset \bar{b} \Leftrightarrow b \in \text{Star}(z)$), would thus belong to $\text{Star}(X)$, a contradiction with the hypothesis.

Let us show now that $z \in \text{FC}(X)$. Recall that

$$ \text{FC}(X) = \text{Extr}(\text{Skel}(\text{Star}(\text{CvxH}(X)))) $$

We have $b \in \text{Star}(\text{CvxH}(X))$. Furthermore $b$ belongs to the skeleton of $\text{Star}(\text{CvxH}(X))$, since it is a cell of $\text{Star}(\text{CvxH}(X))$ with lowest dimension in the closure of $c$. Finally grid vertex $z$ is an extremal point of $b$, so belongs to $\text{FC}(X)$. We conclude since $z \notin X$ holds. $\square$
**Lemma 7** For any finite $X \subset \mathbb{Z}^d$, $X$ and $\text{FC}(X)$ have the same bounding box.

*Proof.* Let $p \subset \mathbb{Z}^d$ be the lowest point of the axis-aligned bounding box of $X$, i.e. $\forall i, 1 \le i \le d, p^i = \min_{z \in X} z^i$. Obviously, it is also the lowest point of the bounding box of $\text{CvxH}(X)$. Let $K := \text{Star}(\text{CvxH}(X))$. Since $\forall x \in \text{CvxH}(X), p^i \le x^i$, any cell $c$ of $K$ that lie below point $q$ along some coordinate axis $j$ has a twin cell $e \in K$ in its boundary, such that $e$ is closed along coordinate $j$ and $e^j = p^j$. Continuing the argument along every coordinate axis $k$ where $e$ is below point $p$, we know that there is a digital point $z \in K$ in the boundary of $c$, such that $z$ is not below $p$. Point $z$ being a 0-cell it follows that $z \in \text{Skel}(K)$ while all $m$-cells incident to $z$, $m > 0$, are not in $\text{Skel}(K)$. We have just shown that no cells of $\text{Skel}(K)$ can be lower than $p$. The reasoning is the same for the uppermost point. □

A first observation is that operation FC does not modify fully convex sets, so the fully convex envelope of a fully convex set $X$ is $X$ itself.

**Lemma 8** If $X \subset \mathbb{Z}^d$ is fully convex, then $\text{FC}(X) = X$. So $\text{FC}^*(X) = X$.

*Proof.* Indeed we have

$$ 
\begin{align*}
\text{FC}(X) &= \text{Extr}(\text{Skel}(\text{Star}(\text{CvxH}(X)))) \\
&= \text{Extr}(\text{Skel}(\text{Star}(X))) \tag*{(\text{Lemma 4})} \\
&= \text{Extr}(X) \tag*{(\text{Lemma 2})} \\
&= X \tag*{(X \subset \mathbb{Z}^d)}
\end{align*}
$$

□

Reciprocally, non fully convex sets are modified through operation FC.

**Lemma 9** If $X \subset \mathbb{Z}^d$ is not fully convex, then $X \subsetneq \text{FC}(X)$

*Proof.* By Lemma 6 we already know that $X \subset \text{FC}(X)$. Let us show that there is a digital point $z \in \text{FC}(X)$ that is not in $X$. Since $X$ is not fully convex, there exists some cell $c \in \text{Star}(\text{CvxH}(X))$ such that $c \notin \text{Star}(X)$. It is possible that there are other cells $c'$ in $\bar{c}$ such that $c' \in \text{Star}(\text{CvxH}(X))$ and $c' \notin \text{Star}(X)$. In this case we pick one, say $b$, with lowest dimension.

Let $z \in \bar{b} \cap \mathbb{Z}^d$ be a grid vertex of this cell (which may be $b$ itself). Then $z \notin X$. Otherwise, $\text{Star}(z) \subset \text{Star}(X)$, hence the cell $b$, which belongs to $\text{Star}(z)$ (through the equivalence $z \subset \bar{b} \Leftrightarrow b \in \text{Star}(z)$), would thus belong to $\text{Star}(X)$, a contradiction with the hypothesis.

Let us show now that $z \in \text{FC}(X)$. Recall that

$$ \text{FC}(X) = \text{Extr}(\text{Skel}(\text{Star}(\text{CvxH}(X)))) $$

We have $b \in \text{Star}(\text{CvxH}(X))$. Furthermore $b$ belongs to the skeleton of $\text{Star}(\text{CvxH}(X))$, since it is a cell of $\text{Star}(\text{CvxH}(X))$ with lowest dimension in the closure of $c$. Finally grid vertex $z$ is an extremal point of $b$, so belongs to $\text{FC}(X)$. We conclude since $z \notin X$ holds. □
Note that the Lemma also indicates where operation FC add digital points. Indeed, they are the vertices of the cells touched by the convex hull but not by the digital set itself. Lemmas 8 and 9 lead immediately to a characterization of fully convex sets:

**Theorem 2** $X \subset \mathbb{Z}^d$ is fully convex iff $X = FC(X)$.

It also induces the most important property of the fully convex envelope operation: it always outputs fully convex sets.

**Theorem 3** For any finite $X \subset \mathbb{Z}^d$, $FC^*(X)$ is fully convex.

*Proof.* By Theorem 1, $FC^*(X)$ exists and there exists some $n$ such that $FC^*(X) = FC^n(X)$. Hence, $FC(FC^n(X)) = FC^n(X)$. By Theorem 2, $FC^n(X)$ is fully convex, and so is $FC^*(X)$. □

The operator $FC^*(.)$ is thus increasing and idempotent. It however fails to be monotone because Skel(.) is not a monotone operator with respect to inclusion. So, it is not a hull operator [And06]. Nevertheless, it induces a preorder relation $\mathcal{R}_{FC^*}$ on digital sets using

$$X \mathcal{R}_{FC^*} Y \iff FC^*(X) = FC^*(Y).$$

It induces equivalent classes among the set of digital sets. It has its own topology through its associated Alexandrov topology.

## 2.4 Algorithmic aspects

We now look at the algorithmic aspects of computing $FC^*$. Since the computation of $FC^*$ is done in a loop, we compute the complexity for each iteration. At the beginning of iteration $k$ the points set is $FC^{k-1}(X)$. Using Quickhull, the convex hull can be computed in $O(nf_r/r)$ [BDH96] with $n$ the number of input points, $r$ the number of processed points and $f_r$ the maximum number of facets of $r$ vertices ($f_r = O(r^{\lfloor d/2 \rfloor / \lfloor d/2 \rfloor!})$). Obviously $r \le n$, such that the complexity is bounded by $O(f_n)$ with $f_n = O(n^{\lfloor d/2 \rfloor / \lfloor d/2 \rfloor!})$. Here, $n$ is the number of points in $FC^{k-1}(X)$. As described in [Lac21], Star (CvxH(.)) can be computed using $2^d$ Quickhull calls with the morphological characterizations of full convexity. It is the most intensive part of the computation. Then, Skel and Extr are extracted by simple traversal over the volume of Star (CvxH(.)). It is thus linear in the volume of Star (CvxH(.)) which is bounded above by the volume of the bounding box of $FC^{k-1}(X)$. Hence the complexity of one iteration is bounded by $O(n^{\lfloor d/2 \rfloor})$. A precise bound on the number of iterations is still under study. In practice 1-4 iterations are generally observed in 3D, but we have come along examples with depth about ten.
Note that the Lemma also indicates where operation FC add digital points. Indeed, they are the vertices of the cells touched by the convex hull but not by the digital set itself. Lemmas 8 and 9 lead immediately to a characterization of fully convex sets:

**Theorem 2** $X \subset \mathbb{Z}^d$ is fully convex iff $X = FC(X)$.

It also induces the most important property of the fully convex envelope operation: it always outputs fully convex sets.

**Theorem 3** For any finite $X \subset \mathbb{Z}^d$, $FC^*(X)$ is fully convex.

*Proof.* By Theorem 1, $FC^*(X)$ exists and there exists some $n$ such that $FC^*(X) = FC^n(X)$. Hence, $FC(FC^n(X)) = FC^n(X)$. By Theorem 2, $FC^n(X)$ is fully convex, and so is $FC^*(X)$. □

The operator $FC^*(.)$ is thus increasing and idempotent. It however fails to be monotone because Skel(.) is not a monotone operator with respect to inclusion. So, it is not a hull operator [And06]. Nevertheless, it induces a preorder relation $\mathcal{R}_{FC^*}$ on digital sets using

$$X \mathcal{R}_{FC^*} Y \iff FC^*(X) = FC^*(Y).$$

It induces equivalent classes among the set of digital sets. It has its own topology through its associated Alexandrov topology.

## 2.4 Algorithmic aspects

We now look at the algorithmic aspects of computing $FC^*$. Since the computation of $FC^*$ is done in a loop, we compute the complexity for each iteration. At the beginning of iteration $k$ the points set is $FC^{k-1}(X)$. Using Quickhull, the convex hull can be computed in $O(nf_r/r)$ [BDH96] with $n$ the number of input points, $r$ the number of processed points and $f_r$ the maximum number of facets of $r$ vertices ($f_r = O(r^{\lfloor d/2 \rfloor / \lfloor d/2 \rfloor!})$). Obviously $r \le n$, such that the complexity is bounded by $O(f_n)$ with $f_n = O(n^{\lfloor d/2 \rfloor / \lfloor d/2 \rfloor!})$. Here, $n$ is the number of points in $FC^{k-1}(X)$. As described in [Lac21], Star (CvxH(.)) can be computed using $2^d$ Quickhull calls with the morphological characterizations of full convexity. It is the most intensive part of the computation. Then, Skel and Extr are extracted by simple traversal over the volume of Star (CvxH(.)). It is thus linear in the volume of Star (CvxH(.)) which is bounded above by the volume of the bounding box of $FC^{k-1}(X)$. Hence the complexity of one iteration is bounded by $O(n^{\lfloor d/2 \rfloor})$. A precise bound on the number of iterations is still under study. In practice 1-4 iterations are generally observed in 3D, but we have come along examples with depth about ten.
<figure><img src="image_4.png" /><figcaption>Fig. 2. Relative fully convex envelope for naive lines having disconnected intersection.</figcaption></figure>

### 3 Relative fully convex envelope

We now specialize operator FC in order to stay into a given fully convex set. This creates fully convex sets relative to a given fully convex set. Given $Y \subset \mathbb{Z}^d$ a fully convex set and $X \subset Y$, the FC operator relative to $Y$ is defined as

$$FC_{|Y}(X) := FC(X) \cap Y.$$

As previously, $FC_{|Y}^n(X) := FC_{|Y} \circ \cdots \circ FC_{|Y}(X)$, composed $n$ times. The fully convex envelope of $X$ relative to $Y$ is obtained at the limit:

$$FC_{|Y}^*(X) := \lim_{n \to \infty} FC_{|Y}^n(X).$$

We thus have $FC^*(X) = FC_{|\mathbb{Z}^d}^*(X)$. In practice, for $X$ not included in $Y$, we compute $FC_{|Y}^*(X \cap Y)$ to get the fully convex envelope of $X \cap Y$.

As seen on Figure (2), the relative fully convex envelope extends sets only using points of the fully convex set $Y$. So when considering two naive lines $X$ and $Y$ having disconnected intersection, both subsets $FC_{|Y}^*(X \cap Y)$ and $FC_{|X}^*(X \cap Y)$ are fully convex, hence are connected intersections.

**Theorem 4** For any finite $X \subset \mathbb{Z}^d$ and any fully convex set $Y \subset \mathbb{Z}^d$, the digital set $FC_{|Y}^*(X \cap Y)$ is fully convex and is included in $Y$.

*Proof.* Let $X' = X \cap Y$. To see that $FC_{|Y}^*(X')$ is well defined, we rely on previous properties of $FC^*(\cdot)$. By construction, since $FC(\cdot)$ is increasing, so is $FC_{|Y}(\cdot)$. Moreover lemma (7) readily extends to say that $X'$ and $FC_{|Y}(X')$ have the same bounding box. It is also true that if $X'$ is fully convex then $FC_{|Y}(X') = X' \cap Y$ and so $FC_{|Y}^*(X') = X'$. Let us now see why lemma (9) also extends to this situation. We hence suppose that $X'$ is not fully convex. Let us then consider any cell $b$ such that $b \in \text{Star}(FC_{|Y}(X'))$ but $b \notin \text{Star}(X')$. Since $\text{CvxH}(X') \subset \text{CvxH}(Y)$, we deduce that $b \in \text{Star}(\text{CvxH}(Y)) = \text{Star}(Y)$ since $Y$ is fully convex. Moreover as in lemma (9), we have $\bar{b} \cap \mathbb{Z}^d \cap X' = \emptyset$. But since $Y \subset \mathbb{Z}^d$ and $b \in \text{Star}(Y)$, we deduce that $\bar{b} \cap \mathbb{Z}^d \cap Y \neq \emptyset$. Hence at least one point in $Y$ is added by $FC_{|Y}(\cdot)$. This implies that $X' \subsetneq FC_{|Y}(X')$. We can thus mimic Theorem 1 and Theorem 2 to get that $FC_{|Y}^*(X')$ exists and is fully convex. It is included in $Y$ by construction. □
<figure><img src="image_4.png" /><figcaption>Fig. 2. Relative fully convex envelope for naive lines having disconnected intersection.</figcaption></figure>

### 3 Relative fully convex envelope

We now specialize operator FC in order to stay into a given fully convex set. This creates fully convex sets relative to a given fully convex set. Given $Y \subset \mathbb{Z}^d$ a fully convex set and $X \subset Y$, the FC operator relative to $Y$ is defined as

$$FC_{|Y}(X) := FC(X) \cap Y.$$

As previously, $FC_{|Y}^n(X) := FC_{|Y} \circ \cdots \circ FC_{|Y}(X)$, composed $n$ times. The fully convex envelope of $X$ relative to $Y$ is obtained at the limit:

$$FC_{|Y}^*(X) := \lim_{n \to \infty} FC_{|Y}^n(X).$$

We thus have $FC^*(X) = FC_{|\mathbb{Z}^d}^*(X)$. In practice, for $X$ not included in $Y$, we compute $FC_{|Y}^*(X \cap Y)$ to get the fully convex envelope of $X \cap Y$.

As seen on Figure (2), the relative fully convex envelope extends sets only using points of the fully convex set $Y$. So when considering two naive lines $X$ and $Y$ having disconnected intersection, both subsets $FC_{|Y}^*(X \cap Y)$ and $FC_{|X}^*(X \cap Y)$ are fully convex, hence are connected intersections.

**Theorem 4** For any finite $X \subset \mathbb{Z}^d$ and any fully convex set $Y \subset \mathbb{Z}^d$, the digital set $FC_{|Y}^*(X \cap Y)$ is fully convex and is included in $Y$.

*Proof.* Let $X' = X \cap Y$. To see that $FC_{|Y}^*(X')$ is well defined, we rely on previous properties of $FC^*(\cdot)$. By construction, since $FC(\cdot)$ is increasing, so is $FC_{|Y}(\cdot)$. Moreover lemma (7) readily extends to say that $X'$ and $FC_{|Y}(X')$ have the same bounding box. It is also true that if $X'$ is fully convex then $FC_{|Y}(X') = X' \cap Y$ and so $FC_{|Y}^*(X') = X'$. Let us now see why lemma (9) also extends to this situation. We hence suppose that $X'$ is not fully convex. Let us then consider any cell $b$ such that $b \in \text{Star}(\text{CvxH}(X'))$ but $b \notin \text{Star}(X')$. Since $\text{CvxH}(X') \subset \text{CvxH}(Y)$, we deduce that $b \in \text{Star}(\text{CvxH}(Y)) = \text{Star}(Y)$ since $Y$ is fully convex. Moreover as in lemma (9), we have $\bar{b} \cap \mathbb{Z}^d \cap X' = \emptyset$. But since $Y \subset \mathbb{Z}^d$ and $b \in \text{Star}(Y)$, we deduce that $\bar{b} \cap \mathbb{Z}^d \cap Y \neq \emptyset$. Hence at least one point in $Y$ is added by $FC_{|Y}(\cdot)$. This implies that $X' \subsetneq FC_{|Y}(X')$. We can thus mimic Theorem 1 and Theorem 2 to get that $FC_{|Y}^*(X')$ exists and is fully convex. It is included in $Y$ by construction. □
Arithmetical planes with thickness at least as thick as naive planes are fully
convex [Lac21, Theorem 7]. Hence the set Y can be chosen to be either a naive or
a standard plane. Then the fully convex hull of X relative to Y is a fully convex
subset of Y containing X ∩ Y. Hence, $FC^*_{|X∩Y}(X)$ is a simply connected piece of
the arithmetical plane Y. To compute $FC^*_{|Y}(\cdot)$, we only have to incorporate the
intersection with Y at each iteration. This is directly linked to the complexity
of deciding if a point $p$ is in Y. If Y is a digital plane then this complexity is
constant but in general it can be up to the order of $O(\log(\#Y))$.

4 Digital polyhedron

We now present digital models for Euclidean polyhedra based on envelopes. A
polyhedron $\mathcal{P}$ is a collection of finite convex sets called cells, such that each
cell $\sigma$ is characterized by a finite number of points $V(\sigma)$ called vertices. Cell $\sigma$
is a face of cell $\sigma'$ if $V(\sigma) \subset V(\sigma')$. The vertices $V$ of the polyhedron are the
union of the vertices of all cells. Generally an abstract dimension is attached to
cells, 0 for vertices, 1 for edges, 2 for faces, etc., and must be consistent with
the face relation. We take an interest here in polyhedra with maximal dimension
$d-1$, i.e. surfaces, whose $(d-1)$-cells are called facets. Figure 3, left, shows two
polyhedra in 3D space: a quadrangulated surface $\mathcal{Q}$ with non planar facets and
a triangulated surface $\mathcal{T}$ with planar facets.

Assuming each vertex of $\mathcal{P}$ is a point of $\mathbb{Z}^d$, the (generic) digital polyhedron $\mathcal{P}^*$ associated to $\mathcal{P}$ is the collection of digital cells that are subsets of $\mathbb{Z}^d$, such that: if $\sigma$ is a cell of $\mathcal{P}$, then $\sigma^*$ is a cell of $\mathcal{P}^*$ with $\sigma^* := \text{FC}^*(V(\sigma))$. Such a digital polyhedron is illustrated on Figure 3, top row.

When vertices of facets are coplanar, we can build a digital polyhedron whose facets are pieces of arithmetic planes. Pure simplicial complexes of dimension $d-1$ are important examples of such polyhedron. For $T \subset \mathbb{Z}^d$ made of coplanar points, let us denote by $P_1(T)$ the median standard plane (resp. $P_\infty(T)$ the median naive plane) defined by $T$.

The standard (resp. naive) digital polyhedron $\mathcal{P}_1^*$ (resp. $\mathcal{P}_\infty^*$) is the collection of digital cells subsets of $\mathbb{Z}^d$, defined as follows. For $p \in \{1, \infty\}$, if $\sigma$ is a facet of $\mathcal{P}$, then $\sigma_p^*$ is a cell of $\mathcal{P}_p^*$ with $\sigma_p^* := \text{FC}_{|P_p(V(\sigma))}^*(V(\sigma))$. For any cell $\tau$ that is not a facet, then it has as many geometric realizations as incident facets $\sigma$ and each pair $(\tau, \sigma)$ is digitized as $(\tau, \sigma)_p^* := \text{FC}_{|\sigma_p^*}^*(V(\tau))$. Cell pairs have the same role as *half-edges* in winged-edge data structures and more generally *darts* in combinatorial maps. Note that other thicknesses could be chosen for digital polyhedron but naive and standard are the most common ones. A standard (resp. naive) digital polyhedron associated to a triangulated mesh is illustrated on Figure 3, middle row (resp. bottom row). They require less digital points than the generic digital points, while keeping their separation properties.

To better understand the three defined polyhedra, let us consider a single
triangle and its edges and vertices: its three digital models are displayed on
Figure 4. All induced cells are fully convex, but we notice that standard cells
are thinner while naive cells are even thinner. What might be surprising is that
Arithmetical planes with thickness at least as thick as naive planes are fully
convex [Lac21, Theorem 7]. Hence the set Y can be chosen to be either a naive or
a standard plane. Then the fully convex hull of X relative to Y is a fully convex
subset of Y containing X ∩ Y. Hence, $FC^*_{|X∩Y}(X)$ is a simply connected piece of
the arithmetical plane Y. To compute $FC^*_{|Y}(.)$, we only have to incorporate the
intersection with Y at each iteration. This is directly linked to the complexity
of deciding if a point p is in Y. If Y is a digital plane then this complexity is
constant but in general it can be up to the order of $O(\log(|Y))$.

4 Digital polyhedron

We now present digital models for Euclidean polyhedra based on envelopes. A
polyhedron $\mathcal{P}$ is a collection of finite convex sets called cells, such that each
cell $\sigma$ is characterized by a finite number of points $V(\sigma)$ called vertices. Cell $\sigma$
is a face of cell $\sigma'$ if $V(\sigma) \subset V(\sigma')$. The vertices $V$ of the polyhedron are the
union of the vertices of all cells. Generally an abstract dimension is attached to
cells, 0 for vertices, 1 for edges, 2 for faces, etc., and must be consistent with
the face relation. We take an interest here in polyhedra with maximal dimension
d − 1, i.e. surfaces, whose (d − 1)-cells are called facets. Figure 3, left, shows two
polyhedra in 3D space: a quadrangulated surface $\mathcal{Q}$ with non planar facets and
a triangulated surface $\mathcal{T}$ with planar facets.

Assuming each vertex of $\mathcal{P}$ is a point of $\mathbb{Z}^d$, the (generic) digital polyhedron $\mathcal{P}^*$ associated to $\mathcal{P}$ is the collection of digital cells that are subsets of $\mathbb{Z}^d$, such that: if $\sigma$ is a cell of $\mathcal{P}$, then $\sigma^*$ is a cell of $\mathcal{P}^*$ with $\sigma^* := \text{FC}^*(V(\sigma))$. Such a digital polyhedron is illustrated on Figure 3, top row.

When vertices of facets are coplanar, we can build a digital polyhedron whose
facets are pieces of arithmetic planes. Pure simplicial complexes of dimension
d − 1 are important examples of such polyhedron. For T ⊂ Z d made of coplanar
points, let us denote by P₁(T) the median standard plane (resp. P∞(T) the
median naive plane) defined by T.

The standard (resp. naive) digital polyhedron $\mathcal{P}_1^*$ (resp. $\mathcal{P}_\infty^*$) is the collection of digital cells subsets of $\mathbb{Z}^d$, defined as follows. For $p \in \{1, \infty\}$, if $\sigma$ is a facet of $\mathcal{P}$, then $\sigma_p^*$ is a cell of $\mathcal{P}_p^*$ with $\sigma_p^* := \text{FC}_{|P_p(V(\sigma))}^*(V(\sigma))$. For any cell $\tau$ that is not a facet, then it has as many geometric realizations as incident facets $\sigma$ and each pair $(\tau, \sigma)$ is digitized as $(\tau, \sigma)_p^* := \text{FC}_{|\sigma_p^*}^*(V(\tau))$. Cell pairs have the same role as *half-edges* in winged-edge data structures and more generally *darts* in combinatorial maps. Note that other thicknesses could be chosen for digital polyhedron but naive and standard are the most common ones. A standard (resp. naive) digital polyhedron associated to a triangulated mesh is illustrated on Figure 3, middle row (resp. bottom row). They require less digital points than the generic digital points, while keeping their separation properties.

To better understand the three defined polyhedra, let us consider a single
triangle and its edges and vertices: its three digital models are displayed on
Figure 4. All induced cells are fully convex, but we notice that standard cells
are thinner while naive cells are even thinner. What might be surprising is that
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Discretization of Euclidean polyhedral models without or with planar facets (left), at gridstep $h = 1$ (middle) and $h = 0.5$ (right).</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Discretization of Euclidean polyhedral models without or with planar facets (left), at gridstep $h = 1$ (middle) and $h = 0.5$ (right).</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** A generic digital triangle $\mathcal{T}^*$ with its darker edges and black vertices $(p, q, r)$ (left); corresponding standard digital triangle $\mathcal{T}_1^*$ which lies in the median standard plane $P_1(p, q, r)$ (middle); corresponding naive digital triangle $\mathcal{T}_\infty^*$ which lies in the median naive plane $P_\infty(p, q, r)$ (right).</figcaption></figure>

relative fully convex enveloppe may create larger subset than expected, especially for the naive triangle example. One should keep in mind that expanding a set inside a naive plane to become fully convex is a very restrictive transform: edges have to expand more within naive plane $P_\infty$ than within standard plane $P_1$. Of course, this is quite an extreme example and edges are narrower in most cases.

The following properties are quite straightforward, but show that every digital polyhedron covers well the cells of its associated Euclidean polyhedron, and that the inclusion/face property between cells is satisfied in the digital domain. Digitizing a polyhedron at different gridstep $h$ is just a matter of embedding every real vertex point $q$ as a digital vertex $q^* = \text{round}(q/h)$ (see Figure 3).

**Proposition 1.** Let $\sigma^*$ be a digital cell of a generic, standard or naive digital polyhedron. Then it is fully convex, hence digitally connected and simply connected. We have $\text{Star}(\text{CvxH}(V(\sigma))) \subset \text{Star}(\sigma^*)$. For any cell $\tau$ such that $\sigma$ is a face of $\tau$, $\text{Star}(\tau^*)$ cover $\text{Star}(\text{CvxH}(V(\sigma)))$.

# 5 Conclusion and perspectives

We provide in this paper an envelope operator for full convexity $\text{FC}^*(\cdot)$. For any digital set $X$, $\text{FC}^*(X)$ is proved to be fully convex and $X \subset \text{FC}^*(X)$. Furthermore this operator leaves fully convex sets unchanged. Moreover, the operator is well defined in arbitrary dimension as well as computable. This operator can be restricted to stay within a fully convex set $Y$, leading to the relative enveloppe operator $\text{FC}^*|_Y(X)$. It builds fully convex sets within $Y$. Since classical naive and standard planes are fully convex, this leads to a straightforward computation of digital analogues to polyhedral models of $\mathbb{R}^d$. The obtained results are quite appealing: we can control the incidence relationship between cells, while their full convexity guarantees their topological and geometrical properties. These digital polyhedral models embrace both meshes with planar or non planar faces.
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** A generic digital triangle $\mathcal{T}^*$ with its darker edges and black vertices $(p, q, r)$ (left); corresponding standard digital triangle $\mathcal{T}_1^*$ which lies in the median standard plane $P_1(p, q, r)$ (middle); corresponding naive digital triangle $\mathcal{T}_\infty^*$ which lies in the median naive plane $P_\infty(p, q, r)$ (right).</figcaption></figure>

relative fully convex enveloppe may create larger subset than expected, especially for the naive triangle example. One should keep in mind that expanding a set inside a naive plane to become fully convex is a very restrictive transform: edges have to expand more within naive plane $P_\infty$ than within standard plane $P_1$. Of course, this is quite an extreme example and edges are narrower in most cases.

The following properties are quite straightforward, but show that every digital polyhedron covers well the cells of its associated Euclidean polyhedron, and that the inclusion/face property between cells is satisfied in the digital domain. Digitizing a polyhedron at different gridstep $h$ is just a matter of embedding every real vertex point $q$ as a digital vertex $q^* = \text{round}(q/h)$ (see Figure 3).

**Proposition 1.** Let $\sigma^*$ be a digital cell of a generic, standard or naive digital polyhedron. Then it is fully convex, hence digitally connected and simply connected. We have $\text{Star}(\text{CvxH}(V(\sigma))) \subset \text{Star}(\sigma^*)$. For any cell $\tau$ such that $\sigma$ is a face of $\tau$, $\text{Star}(\tau^*)$ cover $\text{Star}(\text{CvxH}(V(\sigma)))$.

# 5 Conclusion and perspectives

We provide in this paper an envelope operator for full convexity $\text{FC}^*(\cdot)$. For any digital set $X$, $\text{FC}^*(X)$ is proved to be fully convex and $X \subset \text{FC}^*(X)$. Furthermore this operator leaves fully convex sets unchanged. Moreover, the operator is well defined in arbitrary dimension as well as computable. This operator can be restricted to stay within a fully convex set $Y$, leading to the relative enveloppe operator $\text{FC}^*|_Y(X)$. It builds fully convex sets within $Y$. Since classical naive and standard planes are fully convex, this leads to a straightforward computation of digital analogues to polyhedral models of $\mathbb{R}^d$. The obtained results are quite appealing: we can control the incidence relationship between cells, while their full convexity guarantees their topological and geometrical properties. These digital polyhedral models embrace both meshes with planar or non planar faces.
In future works, we would like to study more precisely the iterative process of FC\*(.), in order to localize where full convexity defects reside. This could accelerate the operator and give more practical bounds on the number of iterations. Incremental quickhull should also be considered. A more general goal is to extend the enveloppe process to a true convex hull operator. The difficulty is to ensure the monotone property, but if we succeed, the full convexity would then be a digital analogue to convexity for digital spaces.

## References

And06. Kazutoshi Ando. Extreme points axioms for closure spaces. *Discrete Mathematics*, 306:3181-3188, 2006.

BB02. Valentin E. Brimkov and Reneta P. Barneva. Graceful planes and lines. *Theoretical Computer Science*, 283(1):151-170, 2002.

BDH96. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. *ACM Transactions on Mathematical Software*, 22 (4):469-483, 1996.

Eck01. Ulrich Eckhardt. Digital lines and digital convexity. In *Digital and Image Geometry, Advanced Lectures [Based on a Winter School Held at Dagstuhl Castle, Germany in December 2000]*, page 209-228. Springer-Verlag, 2001.

Kis04. Christer Oscar Kiselman. Convex functions on discrete sets. In R. Klette and J. Žunić, editors, *Combinatorial Image Analysis. 10th International Workshop, IWCIA, LNCS 3322, pages 443-457*. Springer-Verlag, 2004.

KR82a. Chul E. Kim and Azriel Rosenfeld. Convex digital solids. *IEEE Trans. Pattern Anal. Machine Intel.*, 6:612-618, 1982.

KR82b. Chul E. Kim and Azriel Rosenfeld. Digital straight lines and convexity of digital regions. *IEEE Trans. Pattern Anal. Machine Intel.*, 2:149-153, 1982.

Lac21. Jacques-Olivier Lachaud. An alternative definition for digital convexity. In J. Lindblad, F. Malmberg, and N. Sladoje, editors, *Discrete Geometry and Mathematical Morphology - First International Joint Conference, DGMM 2021, Uppsala, Sweden, May 24-27, 2021, Proceedings*, volume 12708 of LNCS, pages 269-282. Springer, 2021.

Lac22. Jacques-Olivier Lachaud. An alternative definition for digital convexity. *Journal of Mathematical Imaging and Vision*, 2022. Accepted. To appear.

Lau06. Dietlinde Lau. *Function algebras on finite sets*. Springer-Verlag, 2006.

Lli02. Juan-Vicente Llinares. Abstract convexity, some relations and applications. *Optimization*, 51(6):797-818, 2002.

MS01. Kazuo Murota and Akiyoshi Shioura. Relationship of m/l-convex functions with discrete convex functions by miller and favati-tardella. *Discrete Applied Maths*, 115:151-176, 2001.

Ron89. Christian Ronse. A bibliography on digital and computational convexity (1961-1988). *IEEE Trans. Pattern Anal. Machine Intel.*, 11(2):181-190, 1989.

RS03. Anthony J. Roy and John G. Stell. Convexity in discrete space. In W. Kuhn, M. Worboys, and S. Timpf, editors, *COSIT*, pages 253-269. LNCS 2825, Springer-Verlag, 2003.

Web01. Julian Webster. Cell complexes and digital convexity. In *Digital and image geometry*, pages 272-282. Springer, 2001.
In future works, we would like to study more precisely the iterative process of FC\*(.), in order to localize where full convexity defects reside. This could accelerate the operator and give more practical bounds on the number of iterations. Incremental quickhull should also be considered. A more general goal is to extend the enveloppe process to a true convex hull operator. The difficulty is to ensure the monotone property, but if we succeed, the full convexity would then be a digital analogue to convexity for digital spaces.

## References

And06. Kazutoshi Ando. Extreme points axioms for closure spaces. *Discrete Mathematics*, 306:3181-3188, 2006.

BB02. Valentin E. Brimkov and Reneta P. Barneva. Graceful planes and lines. *Theoretical Computer Science*, 283(1):151-170, 2002.

BDH96. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. *ACM Transactions on Mathematical Software*, 22 (4):469-483, 1996.

Eck01. Ulrich Eckhardt. Digital lines and digital convexity. In *Digital and Image Geometry, Advanced Lectures [Based on a Winter School Held at Dagstuhl Castle, Germany in December 2000]*, page 209-228. Springer-Verlag, 2001.

Kis04. Christer Oscar Kiselman. Convex functions on discrete sets. In R. Klette and J. Žunić, editors, *Combinatorial Image Analysis. 10th International Workshop, IWCIA*, LNCS 3322, pages 443-457. Springer-Verlag, 2004.

KR82a. Chul E. Kim and Azriel Rosenfeld. Convex digital solids. *IEEE Trans. Pattern Anal. Machine Intel.*, 6:612-618, 1982.

KR82b. Chul E. Kim and Azriel Rosenfeld. Digital straight lines and convexity of digital regions. *IEEE Trans. Pattern Anal. Machine Intel.*, 2:149-153, 1982.

Lac21. Jacques-Olivier Lachaud. An alternative definition for digital convexity. In J. Lindblad, F. Malmberg, and N. Sladoje, editors, *Discrete Geometry and Mathematical Morphology - First International Joint Conference, DGMM 2021, Uppsala, Sweden, May 24-27, 2021, Proceedings*, volume 12708 of LNCS, pages 269-282. Springer, 2021.

Lac22. Jacques-Olivier Lachaud. An alternative definition for digital convexity. *Journal of Mathematical Imaging and Vision*, 2022. Accepted. To appear.

Lau06. Dietlinde Lau. *Function algebras on finite sets*. Springer-Verlag, 2006.

Lli02. Juan-Vicente Llinares. Abstract convexity, some relations and applications. *Optimization*, 51(6):797-818, 2002.

MS01. Kazuo Murota and Akiyoshi Shioura. Relationship of m/l-convex functions with discrete convex functions by miller and favati-tardella. *Discrete Applied Maths*, 115:151-176, 2001.

Ron89. Christian Ronse. A bibliography on digital and computational convexity (1961-1988). *IEEE Trans. Pattern Anal. Machine Intel.*, 11(2):181-190, 1989.

RS03. Anthony J. Roy and John G. Stell. Convexity in discrete space. In W. Kuhn, M. Worboys, and S. Timpf, editors, *COSIT*, pages 253-269. LNCS 2825, Springer-Verlag, 2003.

Web01. Julian Webster. Cell complexes and digital convexity. In *Digital and image geometry*, pages 272-282. Springer, 2001.