# Geometry of Gauss digitized convex shapes

Jacques-Olivier Lachaud, David Coeurjolly, Tristan Roussillon

► To cite this version:

Jacques-Olivier Lachaud, David Coeurjolly, Tristan Roussillon. Geometry of Gauss digitized convex shapes. 4th International Joint Conference, DGMM 2025, Nov 2025, Groningen, Netherlands, Netherlands. hal-05355892

HAL Id: hal-05355892

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

Submitted on 9 Nov 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Geometry of Gauss digitized convex shapes

Jacques-Olivier Lachaud¹,²[0000-0003-4236-2133], David
Coeurjolly²[0000-0003-3164-8697], and Tristan
Roussillon²[0000-0003-2524-3685]

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

² Université Lyon, CNRS, INSA, LIRIS, F-69000 Lyon, France
{david.coeurjolly,tristan.roussillon}@liris.cnrs.fr

**Abstract.** This paper studies how well we can infer the geometry of a (smooth or not) convex shape $X$ from the convex hull $Y_h$ of its Gauss digitization with a given gridstep $h$. Without smoothness constraint, we first present results concerning the proximity of facet normal vectors to the shape normal vectors, as well as a relation between the number of lattice points just above a facet and its area. Then, further results can be obtained when $X$ is smooth, that are valid in arbitrary dimension $d$. More precisely, we show that the boundary of $Y_h$ is Hausdorff-close to the boundary of $X$ with distance less than $\sqrt{dh}$, and that the vertices of $Y_h$ are even much closer (some $O(h^{2d/\delta+1})$). Finally we show that the geometric normal vectors to the facets of $Y_h$ tend to the smooth shape normals with a speed $O(h^{1/2})$, and the bound is tight.

**Keywords:** Geometric inference · Gauss digitization · Convex hull geometry · Digital normal estimation · Digital geometry

## 1 Introduction

Many works aim at inferring a shape geometry from sampled data. We study here the Gauss digitization, which is the sampling on a regular grid of step $h$. For instance, in 2D, when $h$ is sufficiently small, the digitized boundary is shown to have the same topology as the input smooth shape [28,29]. Classical results from Huxley [10] relate the area of a smooth strictly convex shape with the number of lattice points of its digitization. Klette and Žunić [13] extend these convergence results to moments estimation. For results valid in arbitrary dimension $d$, we can mention that the boundary of a smooth shape and its digitized boundary are at a Hausdorff distance no greater than $\frac{\sqrt{d}}{2}h$ [14].

For the local geometry, understanding the discrete affine geometry of digitized shapes has been a widespread approach [12,3]. Hence recognizing pieces of digital straight lines or planes is a common way to determine the local tangential geometry of digitized shapes, with however few theoretical results on geometric
convergence (see related works below). Straightness is also related to convexity [11], has very nice arithmetic and combinatorics properties [8], while its characteristics are related to the local tangent plane. Recent plane-probing algorithms [16,19] analyzes the local affine geometry of digitized boundaries using separation properties.

The common feature between all these discrete methods is that their holy grail is to recover the geometry of the convex hull when the shape is (at least locally) digitally convex, while hopefully keeping an interesting behavior in non-convex parts. The objective of this paper is precisely to determine if the convex hull of the digitization of a convex shape is an accurate approximation of the geometry of the convex shape. In some sense, this work indicates the best one can hope for when using digital linear geometry to analyze digitized shapes.

*Related works on affine geometry estimation.* The local affine geometry of the digitized boundary is clearly related to the shape tangential characteristics. If most methods ignore the specificities of lattice data and rely on regression, smooth approximations or kernel convolutions and offer a priori no convergence results, several methods do take into account those specificities. We recall that an estimator has order $\beta > 0$ whenever its estimation presents an error bounded by some $O(h^\beta)$, and hence the error tends to 0 with finer sampling. In 2D, binomial derivatives achieves convergence with order $\frac{2}{3}$ [6]. Using Taylor-Lagrange inequality and a roughness criterion gives derivate estimates with order $\frac{1}{2}$ [25]. Both methods require a user given scale parameter. The maximal digital straight segment (MDSS) approach [18] is a parameter-free 2D method with a convergence order of $\frac{1}{3}$ worst case and $\frac{2}{3}$ on average. In 3D, on-surface convolutions [9] are more effective than digital straightness methods [30,17], but with no theoretical guarantees. The only methods achieving proven normal convergence in 3D for smooth enough shapes are a discretization of Voronoi covariance measure [22] with order $\frac{1}{8}$ [5] and digital integral invariants [24] with the better order $\frac{2}{3}$ [15]: both methods require an optimal scale parameter and behave quite similarly in practice.

*Contributions and outlines.* After recalling some essential notions in Section 2, Section 3 studies the general case of digitizing an arbitrary compact convex shape and of inferring its affine geometry from the convex hull of the sampled points. Lemma 1 links the facet normal vectors to the shape normal vectors. Theorem 2 relates the number of lattice points just above a facet and the facet area, which tells on which facet the previous lemma is significant. Section 4 studies the case of smooth convex shapes, which happens to be more fruitful. We can then sandwich the original shape between the digitized convex hull and its dilation by a ball of radius $\sqrt{dh}$ (Theorem 4). Vertices of the convex hull are shown asymptotically much closer to the smooth shape boundary than expected (Theorem 5). This explains a *posteriori* why the convex hull is a “nice” approximation of the underlying smooth convex shape (see Figure 1). Finally, Theorem 6 shows the convergence of the normal vectors to the facets of the convex hull toward the normal vectors of the input smooth convex shape with tight order $\frac{1}{2}$. The result
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** 3D illustration of notations and concepts, from left to right: input convex shape $X$, its digitization $X_h := X \cap h\mathbb{Z}^d$ seen as a collection of cubes (visually equivalent to the $h$-boundary $\partial_h X$), its digitized convex hull $Y_h := \text{CvxH}(X_h)$, the $h$-boundary $\partial_h X$ with the normals of the closest facet on $Y_h$. The three left images are rendered with material “normal”, i.e. the displayed color corresponds to the normal vector direction.</figcaption></figure>

is valid in arbitrary dimension and the constant is explicitly related to the reach of the shape. Section 5 concludes and gives some perspectives. This paper is a fundamental study of the geometric properties of digitized convex hulls. Comparing its practical accuracy to state-of-the-art digital normal estimators is an essential next step, but for space reasons could not be developed here.

## 2 Basic notions

We are only concerned with convex sets of the Euclidean space that are compact. Hence compact or bounded is implicit in all statements. The topological boundary of a compact set $S$ is denoted $\partial S$, its interior $\bar{S} := S \setminus \partial S$. The $d$-dimensional volume of $S$ is written $\text{Vol}^d(S)$ (here taking the Lebesgue or the Hausdorff measure is equivalent in our context). The scalar product of two vectors $\mathbf{u}, \mathbf{v}$ of $\mathbb{R}^n$ is denoted by $\mathbf{u} \cdot \mathbf{v}$ and the Euclidean norm of $\mathbf{u}$ is $\|\mathbf{u}\| := \sqrt{\mathbf{u} \cdot \mathbf{u}}$. The Euclidean distance between a point $\mathbf{x}$ and the set $S$ is $d_E(\mathbf{x}, S) := \min_{\mathbf{s} \in S} \|\mathbf{s} - \mathbf{x}\|$.

*Support function, normal cone, normal vector.* Given a convex set $S$, we denote by $\phi_S$ its support function, such that $\phi_S : \mathbf{w} \in \mathbb{R}^d \mapsto \max_{\mathbf{x} \in S} \mathbf{w} \cdot \mathbf{x} \in \mathbb{R}$. We recall the main property of the support function [27, §1.7.1]:

**Theorem 1.** For $S \subset T$ two convex sets of $\mathbb{R}^d$, $\forall \mathbf{w} \in \mathbb{R}^d$, $\phi_S(\mathbf{w}) \le \phi_T(\mathbf{w})$.

For a given unit vector $\mathbf{w} \in \mathbb{R}^d$, assume the point $\mathbf{p} \in S$ satisfies $\mathbf{p} \cdot \mathbf{w} = \phi_S(\mathbf{w})$, then $\mathbf{p} \in \partial S$ and we say that $\mathbf{w}$ is a normal vector to $S$ at $\mathbf{p}$. For any $\mathbf{p} \in \partial S$, the normal cone to $S$ at $\mathbf{p}$ is the set of normal vectors to $S$ at $\mathbf{p}$, and is denoted by $N_S(\mathbf{p})$. Note that the normal cone is reduced to one vector when $\partial S$ is twice differentiable at $\mathbf{p}$ and we speak of the normal vector to $S$ at $\mathbf{p}$.

*Gauss digitization, digitized boundary, digitized convex hull.* The gridstep is a real positive number denoted by $h$. The lattice $h\mathbb{Z}^d$ is denoted by $\mathcal{L}_h$. The set $X$
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** 2D illustration of the main notations: the convex shape $X$, its Gauss digitization $X_h$, the convex hull of the digitization $Y_h$ and convex sets used in Theorem 4, Section 4 ($Y_h \oplus H_h$, and $Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h}$).</figcaption></figure>

always designates a non-empty compact convex subset of $\mathbb{R}^d$. Its Gauss digitization at step $h$ is the finite set $D_h(X) := \mathcal{L}_h \cap X$. Following standard notations, the number of lattice points hitting $X$ is written $\mathcal{L}_h(X) := \#(D_h(X))$.

Let $H_h$ be the hypercube $h[-\frac{1}{2}, \frac{1}{2}]^d$. For any digital set $Z \subset h\mathbb{Z}^d$, the voxel representation of $Z$ is $Q_h Z := Z \oplus H_h$ (and is a union of axis-aligned cubes with edge length $h$ centered on each digital point of $Z$). The (digitized) h-boundary of a subset $S \subset \mathbb{R}^d$ is $\partial_h S := \partial Q_h D_h(S)$ (e.g. see [14]). Let $(e_i)_{i=1,...,d}$ be the canonical orthonormal basis of $\mathbb{Z}^d$. For any $z \in Z$, and if $z' := z \pm h e_i$ is not in $Z$, we call the pair $(z, z')$ a *surfel* of $Z$. Clearly, the segment $[z, z']$ crosses $\partial_h Z$ at exactly a point, which is the center of the face of $z \oplus H_h$ common with $z' \oplus H_h$.

Finally, the digital set $D_h(X)$ is written $X_h$ to shorten notations. The digitized convex hull $Y_h$ of $X$ is $Y_h := \text{CvxH}(X_h)$ (where $\text{CvxH}(\cdot)$ stands for the convex hull). The objective of the paper is to show how we can infer the geometry of $X$ from the geometry of $Y_h$. Refer to Fig. 2 and 1 for 2D and 3D illustrations.

## 3 Properties for digitized general convex shapes

This section focuses on geometric properties of digitized convex shape, without specific assumptions on the input convex shape. Let $X$ be a compact convex shape of $\mathbb{R}^d$ (smooth or not). The next lemma states that if the shape boundary $\partial X$ is close to a facet of an included polyhedron, then the normal of this facet and the normal of a nearby point $\mathbf{x}$ of $\partial X$ are close to each other, and, the closer the points, the closer the normals. Besides, the further the projection of $\mathbf{x}$ is from the boundary of the facet, the closer are the normals.

**Lemma 1.** Let $Y \subset X$ be a convex polyhedron (i.e. $Y = \text{CvxH}(V)$, where $V$ is a finite subset of $X$). Let $\mathbf{x}$ be an arbitrary point of $\partial X$, and $\mathbf{n} \in N_X(\mathbf{x})$. Let $\mathbf{y}$ be the closest point of $\mathbf{x}$ on $\partial Y$ (which is unique). Assume $\mathbf{y}$ is contained in only one facet (say $\sigma$) of $Y$, with unit normal vector $\mathbf{n}_\sigma$. Then the normal vector $\mathbf{n}_\sigma$
to Y and the normal vector **n** to X are related as:

$$
\begin{array}{ll}
\mathbf{n} \cdot \mathbf{n}_{\sigma} \ge 0, & \\
\sin^2 \angle(\mathbf{n}, \mathbf{n}_{\sigma}) \le \frac{\epsilon^2}{\epsilon^2+r^2}, & \text{with } \left\{ \begin{array}{l} \epsilon := \|\mathbf{x} - \mathbf{y}\|, \\ r := d_E(\mathbf{y}, \partial\sigma). \end{array} \right.
\end{array}
$$

Proof. Since $\mathbf{y} \in Y \subset X$ and using the support function of $X$, we have immediately (see Theorem 1): $\mathbf{y} \cdot \mathbf{n} \le \phi_Y(\mathbf{n}) \le \phi_X(\mathbf{n}) = \mathbf{x} \cdot \mathbf{n}$. But $\mathbf{x} = \mathbf{y} + \epsilon \mathbf{n}_\sigma$ by construction. Substituting above gives

$$
\mathbf{y} \cdot \mathbf{n} \le (\mathbf{y} + \epsilon \mathbf{n}_{\sigma}) \cdot \mathbf{n} \Rightarrow 0 \le \epsilon \mathbf{n}_{\sigma} \cdot \mathbf{n}.
$$

Either $\epsilon > 0$ and we conclude for the relation $\mathbf{n} \cdot \mathbf{n}_{\sigma} \ge 0$, or $\epsilon = 0$ and $\mathbf{x} = \mathbf{y}$ which implies $\sigma \subset \partial X$ and $N_X(\mathbf{x}) = N_Y(\mathbf{x}) = \{\mathbf{n}_{\sigma}\}$, hence $\mathbf{n}_{\sigma} = \mathbf{n}$ and we also conclude.

For the second relation, let us project **n** onto the plane containing $\sigma$. This gives the vector $\mathbf{n}' := \mathbf{n} - (\mathbf{n} \cdot \mathbf{n}_{\sigma})\mathbf{n}_{\sigma}$. If $\mathbf{n}' = \mathbf{0}$ then $\mathbf{n} = \mathbf{n}_{\sigma}$ and the relation is obvious. Otherwise, by the convexity and compactness of $\sigma$, the ray from point $\mathbf{y}$ in direction $\mathbf{n}'$ hits the boundary of $\sigma$ at one point $\mathbf{a}$. We can write $\mathbf{a} = \mathbf{y} + s\frac{\mathbf{n}'}{\|\mathbf{n}'\|}$ with $s$ the (positive) distance from $\mathbf{y}$ to $\mathbf{a} \in \partial\sigma$. Note that $s \ge r$ by hypothesis.

Since $\mathbf{a} \in \sigma \subset Y \subset X$, we have $\mathbf{a} \in X$ and using the support function of $X$, we get: $\mathbf{a} \cdot \mathbf{n} \le \sup_{\mathbf{p} \in X} \mathbf{p} \cdot \mathbf{n} = \phi_X(\mathbf{n}) = \mathbf{x} \cdot \mathbf{n}$. It implies $(\mathbf{x} - \mathbf{a}) \cdot \mathbf{n} \ge 0$. We can decompose $\mathbf{x} - \mathbf{a} = \mathbf{x} - \mathbf{y} + \mathbf{y} - \mathbf{a} = \epsilon \mathbf{n}_{\sigma} - s \frac{\mathbf{n}'}{\|\mathbf{n}'\|}$. It follows that

$$
-s \frac{\mathbf{n}' \cdot \mathbf{n}}{\|\mathbf{n}'\|} + \epsilon \mathbf{n}_{\sigma} \cdot \mathbf{n} \ge (\mathbf{x} - \mathbf{a}) \cdot \mathbf{n} \ge 0 \Rightarrow -s \sqrt{1 - (\mathbf{n}_{\sigma} \cdot \mathbf{n})^2} + \epsilon \mathbf{n}_{\sigma} \cdot \mathbf{n} \ge 0,
$$

since simple calculations give $\mathbf{n}' \cdot \mathbf{n} = \mathbf{n}' \cdot \mathbf{n}' = 1 - (\mathbf{n}_{\sigma} \cdot \mathbf{n})^2$ (both $\mathbf{n}$ and $\mathbf{n}_{\sigma}$ are unit vectors). Posing $c = \mathbf{n}_{\sigma} \cdot \mathbf{n}$ and recalling that the first relation implies that $c \ge 0$, we derive

$$
\epsilon c \ge s \sqrt{1 - c^2} \Rightarrow c^2 \ge \frac{s^2}{s^2 + \epsilon^2} \Rightarrow 1 - c^2 \le \frac{\epsilon^2}{s^2 + \epsilon^2}.
$$

Now $\sin \angle(\mathbf{n}_{\sigma}, \mathbf{n}) = \frac{\|\mathbf{n}'\|}{\|\mathbf{n}\|} = \sqrt{1 - c^2}$. The result follows since $r \le s$. $\square$

In the following corollary (proof is in Appendix A), we consider as convex polyhedron Y the convex hull $Y_h$ of $X_h := D_h(X)$.

**Corollary 1.** Let $(\mathbf{z}, \mathbf{z}')$ be a surfel of $X_h$. Let $\mathbf{y}$ be the nearest point on $\partial Y_h$ to $\mathbf{z}'$ and let $\sigma$ be a facet of $Y_h$ containing $\mathbf{y}$, with normal vector $\mathbf{n}_{\sigma}$. We have:

- there exists $\mathbf{x} \in \partial X \cap [\mathbf{y}, \mathbf{z}']$, that is at a distance less than $h$ from $\mathbf{y}$,

- for any $\mathbf{n} \in N_X(\mathbf{x})$, $\sin^2 \angle(\mathbf{n}, \mathbf{n}_{\sigma}) \le \frac{1}{1+(r/h)^2}$, if $r := d_E(\mathbf{y}, \partial\sigma)$.

The previous corollary looks like a proof of convergence of normal vectors of $Y_h$ towards normal vectors of $X$. It means that the point where the best estimation will be obtained is around the center of the inscribed circle/sphere of the facet. However it leaves unclear where the exterior lattice points of boundary
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Digitizations of arbitrary convex shapes: $\partial Y_h$ (in red) can be very far away from $\partial X$ (in black, left figure); however there are exterior points close to long enough edges, depending on the $x$- (middle, in green) or $y$-component (right, in blue) of the edge vector, so $\partial X$ is at a distance less than $h$ near these points.</figcaption></figure>

surfels are projected onto their nearest facet: perhaps no such point exists above this center, especially if the facet is small or elongated. The following theorem shows that there are indeed exterior lattice points just above the interior of facets of $Y_h$, for long enough edges in 2D or wide enough triangles in 3D.

We say that a $d$-simplex $\sigma$ of vertices $(p_1, \dots, p_d)$ in $h\mathbb{Z}^d$ is primitive if $\mathrm{CvxH}(\sigma) \cap h\mathbb{Z}^d = \{p_1, \dots, p_d\}$. The $d-1$-dimensional measure of the projection of $\sigma$ onto a plane orthogonal to the axis $i \in \{1, \dots, d\}$ is denoted by $A_i(\sigma)$ (informally the length or the area of the projected simplex). See Figure 3 for a 2D illustration of where the lattice points are not in $X$ but close to $Y_h$.

**Theorem 2.** For $d \in \{2,3\}$, let $\sigma$ be a primitive edge ($d=2$) or a primitive triangle ($d=3$) of $\partial Y_h$. Then there are (at least) $k$ lattice points of $h\mathbb{Z}^d$ not in $X$ at a distance less than $h$ from $\sigma$, where $k$ follows:

$$-d=2: \text{ then } k = \max_{i \in \{1,2\}} (A_i(\sigma)/h) - 1,$$

$$-d=3: \text{ then } k \ge \frac{-7+\sqrt{25+48 \max_{i \in \{1,2,3\}} A_i(\sigma)/h^2}}{2}.$$

Otherwise said, a segment of $\partial Y_h$ with one component greater or equal to $2h$, and a triangle with one projected area greater or equal to $\frac{7}{6}h^2$, have at least one close exterior lattice point not in $X$ that projects in $\tilde{\sigma}$ along some $\pm \mathbf{e}_i$.

*Proof.* Let us start with the case $d=2$. Let $\sigma = (p,q)$ be a primitive edge of $\partial Y_h$. Let $\mathbf{t} = \pm h\mathbf{e}_i$, $i \in \{1,2\}$ be an axis lattice vector such that $p' := p + \mathbf{t} \notin X$ and $q' := q + \mathbf{t} \notin X$ (at least one such vector exists, otherwise $p$ and $q$ are not vertices of $Y_h$). Let $P$ be the parallelogram $\mathrm{CvxH}(\{p,q,p',q'\})$ and we denote by $k$ the number of lattice points in the interior of $P$. We use Pick's theorem to bound $k$ from below:

$$\begin{aligned} \mathrm{Vol}^2 \left( \frac{1}{h} P \right) &= \mathcal{L}_h(\dot{P}) + \frac{1}{2} \mathcal{L}_h(\partial P) - 1 && (\text{Pick's theorem}) \\ &= k + 1 && (\text{since } \partial P \text{ hits 4 points exactly}) \end{aligned}$$

These $k$ interior points are necessarily outside $X$, otherwise they would be in $Y_h$ and $(p,q)$ would not be an edge of $\partial Y_h$. Noticing that $\mathrm{Vol}^2(\frac{1}{h}P) = \frac{1}{h^2}|\det(q-p, \mathbf{t})| = \frac{1}{h}|(q-p)_i| = A_i(\sigma)/h$ and using both directions $i \in \{1,2\}$, we have found
k lattice points not in X but strictly inside a parallelogram touching $Y_h$ with width at most $h$. This concludes.

The case $d=3$ is harder, especially because there are lattice polyhedra with infinite volume that hits a few lattice points.<fnref n="3" /> Let $\sigma = (p, q, r)$ be a primitive triangle of $\partial Y_h$. Let $\mathbf{t} = \pm h\mathbf{e}_i$, $i \in \{1, 2, 3\}$ be an axis lattice vector such that $p' := p + \mathbf{t} \notin X$, $q' := q + \mathbf{t} \notin X$ and $r' := r + \mathbf{t} \notin X$ (at least one exists for the reason mentioned above). Let $P$ be the triangular prism $\text{CvxH}(\{p, q, r, p', q', r'\})$ and we denote by $k$ the number of lattice points in the interior of $P$. We exploit here Reeve's result [26, Theorem I], valid for any integer $n \ge 1$ and full-dimensional lattice convex polyhedron $P$:

$$2(n^3 - n)\text{Vol}^3\left(\frac{1}{h}P\right) = 2\left(\mathcal{L}_{\frac{h}{n}}(P) - n\mathcal{L}_h(P)\right) - \left(\mathcal{L}_{\frac{h}{n}}(\partial P) - n\mathcal{L}_h(\partial P)\right), \quad (1)$$

$$\text{and} \quad 2(1 - n^2) = \mathcal{L}_{\frac{h}{n}}(\partial P) - n^2 \mathcal{L}_h(\partial P). \qquad (2)$$

Note that we have $\mathcal{L}_{\frac{h}{n}}(P) = \mathcal{L}_h(nP)$ (where $nP$ stands for homothety of $P$ centered at the origin by the factor $n$). We use the relations above with the dilation factor $n = 2$.

$\mathcal{L}_h(P) = 6+k$ and $\mathcal{L}_h(\partial P) = 6$ are obvious from the fact that the triangular face is primitive and $k$ is the number of interior lattice points. Dilating by two the lattice prism creates 5 lattice points per quadrangular face, and 3 per triangular face, but most are shared between two faces (except one per quadrangle). We have 3 quadrangular faces, so $3(\frac{4}{2} + 1)$ new lattice points. We have 2 triangular faces, so $2(\frac{3}{2})$ new lattice points. Summing with the initial 6 lattice points gives $\mathcal{L}_{\frac{h}{2}}(\partial P) = \mathcal{L}_h(\partial 2P) = 6 + 9 + 3 = 18$. We can already check (2).

Finally, each of the $k$ interior lattice points of $P$ can be combined with any lattice point of $\partial P$ and their middle point gives an interior lattice point of $\mathcal{L}_h(2P)$, hence at most $6k$ points. The middle point of any pair of interior lattice points of $P$ is also a lattice point of $\mathcal{L}_h(2P)$ and there are at most $\binom{k}{2}$ of them that are distinct (some of them could be the same). We get $\mathcal{L}_{\frac{h}{2}}(P) = \mathcal{L}_h(2P) \le 18 + 6k + \binom{k}{2}$. Inserting the found values in (1):

$$12\text{Vol}^3\left(\frac{1}{h}P\right) \le 2\left(18 + 6k + \frac{k(k-1)}{2} - 2(6 + k)\right) - (18 - 12) = 6 + 7k + k^2.$$

Otherwise said, $k$ satisfies $k^2 + 7k + 6 - 12\text{Vol}^3(\frac{1}{h}P) \ge 0$. A short computation gives $k \ge (-7 + \sqrt{25 + 48\text{Vol}^3(\frac{1}{h}P)})/2$.

We notice again that $\text{Vol}^3(\frac{1}{h}P) = \frac{1}{2h^3}|\det(q - p, r - p, \mathbf{t})| = \frac{1}{h^2}A_i(\sigma)$ to conclude the argument. □

The results in this section show that there are points on $Y_h$ where the normal vector of the underlying shape can be pretty well estimated, and we know where the estimation will be good: above large enough facets and near their inscribed sphere center. However we have no control on the radius of the inscribed

<footnote n="3">³ For instance the tetrahedron $\{(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, j)\}$ with $j \in \mathbb{Z}$.</footnote>
sphere. The purpose of the next section is to get better estimates by considering digitization of convex shapes with smoothness properties.

# 4 Properties for digitized smooth convex shapes

If we assume smoothness of the convex shape $X$, we can use the previous result to show the convergence of normal vectors in 2D around most edges of $Y_h$.

**Theorem 3.** If $X$ is a convex shape of $\mathbb{R}^2$ with $C^3$-smooth boundary and positive curvature, then any edge $\sigma$ of $\partial Y_h$ having at least the average length of edges of $\partial Y_h$ has a normal $n_\sigma$ close to the normal $n$ of the closest point of $\partial X$ to the edge center, and more precisely $\angle(n, n_\sigma) \le \Theta(h^{\frac{1}{3}})$.

*Proof.* [1, Theorem 2] tells that the number of vertices $N(Y_h)$ of $Y_h$ is some $\Theta(h^{-2/3})$. So the average length $L(Y_h)$ of the edges of $Y_h$ is the perimeter of $X$ divided by $N(Y_h)$, so $L(Y_h) = \Theta(h^{2/3})$. According to Theorem 2 in the case $d=2$, there are almost as many exterior lattice points as the discrete length of the nearby edge. Except for a constant number of edges (maximum 8, the ones having directions (1,0) and (1,1) and their 4 rotations), all the other edges have an exterior lattice point close to the center of the edge. For an edge $\sigma$ with approximately the average length $L(Y_h)$, the estimation error between $n_\sigma$ and the closest point on $\partial X$ is (Corollary 1): $\sin^2 \angle(n, n_\sigma) \le \frac{1}{1+(L(Y_h)/2h)^2} = \frac{1}{1+\Theta(h^{-2/3})}$. Taylor expansion of the previous relation gives $\angle(n, n_\sigma) \le \Theta(h^{2/3})$. $\square$

Unfortunately, this result cannot be easily extended to higher dimensions, since there exist small or elongated facets starting from 3D. In fact, by using a completely different approach, we achieve below a much stronger result on normal convergence.

Before that, let us try to better understand how the geometry of $Y_h$ and the geometry of $X$ exhibit more relations in the case where $X$ has a smooth boundary. The reach of $S \subset \mathbb{R}^d$, denoted reach($S$), is the infimum of the distance of the set $S$ to its medial axis [7] (the medial axis gathers points that have at least two nearest neighbors on $S$). From now on, we change the smoothness condition on $X$ and we assume that reach($\partial X$) is greater than some $\rho > 0$. In our context, it means that $\partial X$ has its principal curvatures between 0 (included) and $1/\rho$ (excluded).

We start by sandwiching $X$ between $Y_h$ and $Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h}$, where $B_r$ is the ball centered on $0$ and of radius $r$. Note that it is not true in general that $X \subset Y_h \oplus H_h$, as illustrated by Figure 2.

**Theorem 4.** Assume $X \subset \mathbb{R}^d$, compact, convex with reach($\partial X$) > $\rho$. For all gridsteps $h$, $0 < h < \frac{2\rho}{\sqrt{d}}$, we have $Y_h \subset X \subset Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h}$. It follows that the convex boundary $\partial X$ lies in the strip $Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h} \setminus \text{Int}(Y_h)$. Furthermore $d_H(X, Y_h) = d_H(\partial Y_h, \partial X) \le \sqrt{dh}$.
Proof. We have $X_h \subset X$ so $Y_h = \text{CvxH}(X_h) \subset \text{CvxH}(X) = X$ and the first inclusion follows. By definition, the $h$-boundary $\partial_h X$ of $X$ is the topological boundary of $X_h \oplus H_h$, i.e. $\partial_h X = \partial(X_h \oplus H_h)$. It implies

$$ \text{CvxH}(\partial_h X) = \text{CvxH}(\partial(X_h \oplus H_h)) = \text{CvxH}(X_h \oplus H_h) = Y_h \oplus H_h. \quad (3) $$

According to [14, Theorem 1], $d_H(\partial_h X, \partial X) \le \frac{\sqrt{d}}{2}h$ for $h < \frac{2\rho}{\sqrt{d}}$. Hence

$$ \partial X \subset \partial_h X \oplus B_{\frac{\sqrt{d}}{2}h}. \quad (4) $$

By convexity $X = \text{CvxH}(\partial X)$. The second inclusion follows from

$$ \begin{align*} \text{CvxH}(\partial X) &\subset \text{CvxH}\left(\partial_h X \oplus B_{\frac{\sqrt{d}}{2}h}\right) \quad \text{(using (4))} \\ &\subset \text{CvxH}(\partial_h X) \oplus B_{\frac{\sqrt{d}}{2}h} \quad \text{(commutativity of $\oplus$ and CvxH(·))} \\ &\subset Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h} \quad \text{(using (3))} \end{align*} $$

It remains to establish the Hausdorff distance between $\partial X$ and $\partial Y_h$. Since $Y_h$, $X$ and $Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h}$ are all convex, we have these relations for their support functions, for any $\mathbf{w} \in \mathbb{R}^d$:

$$ \phi_{Y_h}(\mathbf{w}) \le \phi_X(\mathbf{w}) \le \phi_{Y_h \oplus H_h \oplus B_{\frac{\sqrt{d}}{2}h}}(\mathbf{w}) = \phi_{Y_h}(\mathbf{w}) + \phi_{H_h}(\mathbf{w}) + \phi_{B_{\frac{\sqrt{d}}{2}h}}(\mathbf{w}). $$

Subtracting $\phi_{Y_h}(\mathbf{w})$ to the three terms above, and assuming $\|\mathbf{w}\|_2 = 1$ gives:

$$ 0 \le \phi_X(\mathbf{w}) - \phi_{Y_h}(\mathbf{w}) \le \phi_{H_h}(\mathbf{w}) + \phi_{B_{\frac{\sqrt{d}}{2}h}}(\mathbf{w}) \le \frac{\sqrt{d}}{2}h + \frac{\sqrt{d}}{2}h. $$

Since $\sup_{\mathbf{w} \in S} \|\phi_X(\mathbf{w}) - \phi_{Y_h}(\mathbf{w})\| \le \sqrt{d}h$ for $S$ the unit sphere of $\mathbb{R}^d$, we have that $d_H(X, Y_h) \le \sqrt{d}h$.

We finally use [31, Theorem 20], which states that “If $A$ and $B$ are non-empty, closed, bounded convex sets, $d_H(A, B) = d_H(\partial A, \partial B)$”, to conclude that $d_H(\partial X, \partial Y_h) \le \sqrt{d}h$. $\square$

**Corollary 2.** For all gridsteps $h$, $0 < h < \frac{2\rho}{\sqrt{d}}$, for $\mathbf{y} \in \partial Y_h$ and any normal vector $\mathbf{w} \in N_{Y_h}(\mathbf{y})$, define $P$ as the plane orthogonal to $\mathbf{w}$ and containing $\mathbf{y}$. then for any point $\mathbf{y}' \in P$, we have that $\mathbf{y}' + t\mathbf{w}$ is outside $X$ for $t \ge \sqrt{d}h$.

*Proof.* Proof is in appendix. $\square$

We now show that vertices of $\partial Y_h$ are much closer to $\partial X$ than the upper bound on $d_H(\partial X, \partial Y_h)$ suggests, ie. some $\Theta(h^{3/2})$ instead of $\sqrt{3}h$ in 3D. This result is not really new. Most of the proof relies on the so called Macbeath region of a point $\mathbf{x} \in X$, that is $M_X(\mathbf{x}) := X \cap (2\mathbf{x} - X)$ (intersection of $X$ with its central symmetry around $\mathbf{x}$). Macbeath [20] introduced them to count lattice points in-between two convex bodies. Similar arguments can be found in the proof of the upper bound of [1, Theorem II], or from [2, Theorem 4.3 and discussion]. Our proof below has the advantage of expliciting precisely the constant in the upper-bound with respect to the reach.
**Theorem 5.** Assume the convex set $X \subset \mathbb{R}^d$ has reach($\partial X$) > $\rho$. Let $\mathbf{y}$ be a vertex of $Y_h$. It holds that, for gridsteps $h$, $0 < h \le \rho$, $d_E(\mathbf{y}, \partial X) < \alpha_d \rho^{-\frac{d-1}{d+1}} h^{\frac{2d}{d+1}}$, where the constant $\alpha_d$ depends on the dimension. If $h$ is sufficiently small, we have $\alpha_2 \approx (\frac{3}{2\sqrt{2}})^{\frac{2}{3}}$ and $\alpha_3 \approx \frac{2}{\sqrt{\pi}}$.

*Proof.* Any vertex $\mathbf{y}$ of $Y_h$ is at a distance less than $h$ from $\partial X$ (one of $\mathbf{y} \pm h\mathbf{e}_i$, $i \in \{1, \dots, d\}$, must be outside $X$). So $d_E(\mathbf{y}, \partial X) \le h$ and $\mathbf{y}$ is within the reach of $\partial X$ by hypothesis. Let $\mathbf{x}$ be the projection on $\partial X$ of $\mathbf{y}$ and $\mathbf{n} := \frac{\mathbf{x}-\mathbf{y}}{|\mathbf{x}-\mathbf{y}|}$ the unit outward normal to $X$ at $\mathbf{x}$. The open ball $B$ of center $\mathbf{x} - \rho\mathbf{n}$ and radius $\rho$ is contained in $X$. Furthermore, $\mathbf{y}$ belongs to the straight segment $[\mathbf{x} - \rho\mathbf{n}, \mathbf{x}]$.

Let $S_X := M_X(\mathbf{y}) = X \cap (2\mathbf{y} - X)$ and $S_B := M_B(\mathbf{y}) = B \cap (2\mathbf{y} - B)$ (see Figure 4). Since $B \subset X$ we have $S_B \subset S_X$, hence $\mathrm{Vol}^d(S_B) \le \mathrm{Vol}^d(S_X)$. We explicit $\mathrm{Vol}^d(S_B)$ as a function of $\delta := \|\mathbf{x} - \mathbf{y}\| = d_E(\mathbf{y}, \partial X)$.

It is clear that $S_B$ is the union of two caps of a $d$-ball of radius $\rho$. Each slice of each cap is itself a $d-1$-ball of radius $s$, denoted by $B^{d-1}(s)$, where $s$ depends on the distance $t$ to $\mathbf{x}$. It is also known that $\mathrm{Vol}^{d-1}(B^{d-1})(s) = \frac{\pi^{(d-1)/2}}{\Gamma((d+1)/2)}s^{d-1}$. Besides Pythagoras theorem indicates $\rho^2 = (\rho - t)^2 + s^2$, so $s = \sqrt{2\rho t - t^2}$. We compute:

$$ \mathrm{Vol}^d(S_B) = 2 \int_0^\delta \mathrm{Vol}^{d-1} \left( B^{d-1} \left( \sqrt{2\rho t - t^2} \right) \right) dt = 2 \int_0^\delta \frac{\pi^{\frac{d-1}{2}}}{\Gamma\left(\frac{d+1}{2}\right)} \left( \sqrt{2\rho t - t^2} \right)^{d-1} dt. $$

Standard integral computations gives:

$$ - \text{ for } d=2, \text{ we have } \Gamma(\frac{3}{2}) = \frac{1}{2}\sqrt{\pi}, \text{ and } \mathrm{Vol}^2(S_B) = \frac{8\sqrt{2\rho}}{3}\delta^{\frac{3}{2}} + O\left(\frac{\delta^{\frac{5}{2}}}{\sqrt{\rho}}\right), $$

$$ - \text{ for } d=3, \Gamma(2)=1, \text{ and } \mathrm{Vol}^3(S_B) = 2\pi\rho\delta^2 - \frac{2}{3}\pi\delta^3, $$

$$ - \text{ for } d=4, \Gamma(\frac{5}{2}) = \frac{3}{4}\sqrt{\pi}, \text{ and } \mathrm{Vol}^4(S_B) = \frac{32\pi\sqrt{2\rho}}{15}\delta^{\frac{3}{2}} + O\left(\delta^{\frac{7}{2}}\sqrt{\rho}\right). $$

For a bound generic in $d$, it is enough in our context — and simpler — to compute the volume of the bi-cone within $S_B$, hence:

$$ \begin{aligned} \mathrm{Vol}^d(S_B) &\ge 2 \int_0^\delta \mathrm{Vol}^{d-1} \left( B^{d-1} \left( \frac{t}{\delta} \sqrt{2\rho\delta - \delta^2} \right) \right) dt \\ &\ge 2 \int_0^\delta \frac{\pi^{\frac{d-1}{2}}}{\Gamma\left(\frac{d+1}{2}\right)} \left( \frac{t}{\delta} \sqrt{2\rho\delta - \delta^2} \right)^{d-1} dt = \Theta\left(\rho^{\frac{d-1}{2}} \delta^{\frac{d+1}{2}}\right). \end{aligned} $$

We may now use Minkowski's theorem [23] on $S_X$. The volume of $S_X$ cannot exceed $(2h)^d$. Indeed, if this is the case, then $S_X$ must contain at least two other lattice points $\mathbf{z}$ and $\mathbf{z}'$ symmetric around $\mathbf{y}$ ($\mathbf{y} - \mathbf{z} = \mathbf{z}' - \mathbf{y}$). But both $\mathbf{z}, \mathbf{z}' \in X$, so $\mathbf{z}$ and $\mathbf{z}'$ belong to $X_h$ and thus $Y_h$. Yet $\mathbf{y}$ is a vertex of the convex polyhedron $Y_h$ and cannot be in the middle of two other points of $Y_h$. It follows that

$$ (2h)^d > \mathrm{Vol}^d(S_X) \ge \mathrm{Vol}^d(S_B) \ge \Theta\left(\rho^{\frac{d-1}{2}} \delta^{\frac{d+1}{2}}\right). $$
<figure><img src="image_5.png" /><figcaption>Fig. 4. Illustrations for the proofs of Theorem 5 (left) and Theorem 6 (right).</figcaption></figure>

We achieve this upper bound for vertex distance $\delta < \alpha_d h^{2d}/\rho^{d-1}$. Constants $\alpha_2$ and $\alpha_3$ are derived from the more precise formula above. □

One can check in practice that these theoretical bounds are indeed reached in 2D and 3D, on digitizations of ellipses for instance, and that the constants are quite tight (see Figure 5, page 15).

Theorem 6 below is our main result: it shows that the normal vectors to the facets of the digitized convex hull converge towards the normal vectors of the smooth convex shape, for small enough gridstep $h$, and that the speed of convergence is proportional to $\sqrt{h/\rho}$.

**Theorem 6.** Assume the convex set $X \subset \mathbb{R}^d$ has reach($\partial X$) > $\rho$. Let $\mathbf{y}$ be any point on the boundary $\partial Y_h$. The point $\mathbf{x} := \pi_{\partial X}(\mathbf{y})$ is its closest point on $\partial X$, and it is well known that the outer normal $\mathbf{n}$ to $X$ at $\mathbf{x}$ is aligned with $\mathbf{x} - \mathbf{y}$. Let $\mathbf{w} \in N_{Y_h}(\mathbf{y})$ be any normal vector to $Y_h$ at $\mathbf{y}$. Let $\delta := \|\mathbf{x} - \mathbf{y}\|$. Then for gridsteps $h$, $0 < h < \frac{\rho}{\sqrt{d}}$, it holds that $0 \le \delta < \sqrt{dh}$ and:

$$ \mathbf{n} \cdot \mathbf{w} \ge \frac{1 - \sqrt{d \frac{h}{\rho}}}{1 - \frac{\delta}{\rho}} \ge 1 - \sqrt{d \frac{h}{\rho}} > 0 \quad \text{i.e.} \quad \angle(\mathbf{n}, \mathbf{w}) \le O\left(\sqrt{\frac{h}{\rho}}\right). $$

*Proof.* See Figure 4 (right) for an illustration. Let $B$ be the ball centered on $\mathbf{c} := \mathbf{x} - \rho\mathbf{n}$ and of radius $\rho$. Since $\partial X$ has positive reach $\rho$, $B$ lies inside $X$. Let $P$ be the plane containing $\mathbf{y}$ and orthogonal to $\mathbf{w}$ and let $\mathbf{c}' := \pi_P(\mathbf{c}) = \mathbf{c} - ((\mathbf{c} - \mathbf{y}) \cdot \mathbf{w})\mathbf{w}$, i.e. the projection of $\mathbf{c}$ onto $P$. Letting $\delta := \|\mathbf{x} - \mathbf{y}\|$, we have $\|\mathbf{c} - \mathbf{y}\| = \rho - \delta$ since $\mathbf{c}, \mathbf{y}, \mathbf{x}$ are aligned.

$$ \begin{aligned} (\mathbf{c}' - \mathbf{c}) \cdot \mathbf{w} &= (\mathbf{c} - ((\mathbf{c} - \mathbf{y}) \cdot \mathbf{w})\mathbf{w} - \mathbf{c}) \cdot \mathbf{w} \\ &= (\mathbf{y} - \mathbf{c}) \cdot \mathbf{w} = (\rho - \delta)\mathbf{n} \cdot \mathbf{w}. \end{aligned} \quad (5) $$

On one side, we know that $\mathbf{p} := \mathbf{c} + \rho\mathbf{w}$ belongs to $B$ hence also to $X$. On the other side, Corollary 2 entails that $\mathbf{p}' := \mathbf{c}' + \sqrt{dh}\mathbf{w}$ does not belong to $X$ and
more precisely that $\phi_X(\mathbf{w}) < \mathbf{p}' \cdot \mathbf{w}$. We have

$$ \mathbf{p} \cdot \mathbf{w} = (\mathbf{c} + \rho \mathbf{w}) \cdot \mathbf{w} \le \phi_X(\mathbf{w}) < \mathbf{p}' \cdot \mathbf{w} = (\mathbf{c}' + \sqrt{dh}\mathbf{w}) \cdot \mathbf{w} \\ \Rightarrow \rho - \sqrt{dh} < (\mathbf{c}' - \mathbf{c}) \cdot \mathbf{w} = (\rho - \delta)\mathbf{n} \cdot \mathbf{w}. \quad (\text{using (5)}) \quad (6) $$

Corollary 2 also implies that $\delta < \sqrt{dh}$ (otherwise $\mathbf{x}$ would be outside $X$). Since $h < \rho/\sqrt{d}$ by hypothesis, we have $\delta < \rho$ and $\sqrt{dh} < \rho$, so the left hand side of (5) is positive, and so is its right hand. This entails $\mathbf{n} \cdot \mathbf{w} > 0$. Moreover

$$ \mathbf{n} \cdot \mathbf{w} > \frac{\rho - \sqrt{dh}}{\rho - \delta} = \frac{1 - \sqrt{dh}/\rho}{1 - \delta/\rho} \ge 1 - \sqrt{d} \frac{h}{\rho}. \quad (7) $$

Let $\alpha := \angle(\mathbf{n}, \mathbf{w})$. So $\cos \alpha > 1 - \sqrt{d} \frac{h}{\rho}$. From the above expression, it can be seen that $\alpha$ tends to zero as $h$ tends to zero. Taylor expansion of $\arccos(1 - \sqrt{d} \frac{h}{\rho})$ around $h = 0$ gives $\alpha < \sqrt{\frac{2\sqrt{d}}{\rho}}h + O(h^{\frac{3}{2}})$, which concludes. $\square$

The result is tight in convergence order, and we can exhibit a simple example where the constant is almost reached (gap is less than $2^{1/4} \approx 20\%$). Just take a disk $X$ of radius $\rho = h(k + 1 - \epsilon)$, $k$ a positive integer, $\epsilon$ an arbitrary small positive real number. The convex hull $Y_h$ has a vertical edge symmetric about the $x$-axis going through the lattice point $(hk, 0)$. Due to Pythagoras theorem, its two vertices are close to $\pm(hk, h\sqrt{2k})$ (up to negligible terms). Let $\mathbf{x}$ be the closest point on $\partial X$ to the upper vertex, its normal is $\mathbf{n} \approx \frac{(k, \sqrt{2k})}{\sqrt{k^2+2k}}$. The normal to edge is $\mathbf{w} = (1, 0)$. We get $\mathbf{n} \cdot \mathbf{w} = \frac{1}{\sqrt{1+2/k}}$, thus $\angle(\mathbf{n}, \mathbf{w}) \approx \sqrt{\frac{2}{k}} \approx \sqrt{\frac{2h}{\rho}}$, to compare with $\sqrt{\frac{2\sqrt{2h}}{\rho}}$ of the theorem.

# 5 Conclusion

In this paper, we have explored links between geometrical quantities estimated at the boundary of a convex set $X \subset \mathbb{R}^d$ and similar quantities on the boundary of the convex hull of the digitization of $X$. We have shown the proximity of the digitized convex hull to $X$ in terms of Hausdorff distance and highlighted that convex hull vertices are much closer to $\partial X$ than their incident faces, explaining the visual quality of convex hulls. Our main result is that the normal vector to each facet of the digital convex hull converges towards the normal vectors of the convex shape, for small enough gridstep $h$, with explicit convergence speed (proportional to $\sqrt{h/\rho}$ for smooth convex shapes). This result indicates that the normal vector to facets of the digitized convex hull could be used as a discrete normal estimator on digitized convex shapes, and more generally in convex or concave parts of digitized shapes.

This result is related to the properties of the projection function $\pi_K$ onto the nearest point on a compact set $K$, where the difference between $\pi_K$ and $\pi_{K'}$ is shown proportional to the square root of their Hausdorff distance [4,22]. Even if
we have shown that vertices are closer than $O(h)$, this is not the case elsewhere on the shape. Our achieved result is then tight, with a constant much better than the one of Voronoi Covariance Measure [21,22], which also requires kernel integration.

The next step is to evaluate the practical accuracy of this normal estimator with respect to state-of-the art approaches [9,5,15]. Furthermore, normal vectors to facets could be combined, convolved or interpolated to design more accurate normal estimators. We intend to pursue this line of work in an extension or a subsequent paper.

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

## References

1. Balog, A., Bárány, I.: On the convex hull of the integer points in a disc. In: Proceedings of the 7th Annual Symposium on Computational Geometry. pp. 162–165 (1991)

2. Bárány, I.: Random points, convex bodies, lattices. arXiv preprint math/0304462 (2003), iCM 2002

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

4. Chazal, F., Cohen-Steiner, D., Mérigot, Q.: Boundary measures for geometric inference. Foundations of Computational Mathematics **10**, 221–240 (2010)

5. Cuel, L., Lachaud, J.O., Thibert, B.: Voronoi-based geometry estimator for 3d digital surfaces. In: Barcucci, E., Frosini, A., Rinaldi, S. (eds.) Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI’2014), Sienna, Italy. Lecture Notes in Computer Science, vol. 8668, pp. 134–149. Springer International Publishing (2014). https://doi.org/10.1007/978-3-319-09955-2_12

6. Esbelin, H.A., Malgouyres, R.: Convergence of binomial-based derivative estimation for C2 noisy discretized curves. In: Discrete Geometry for Computer Imagery: 15th IAPR International Conference, DGCI 2009, Montréal, Canada, September 30-October 2, 2009. pp. 57–66. Springer (2009)

7. Federer, H.: Curvature measures. Transactions of the American Mathematical Society **93**(3), 418–491 (1959)

8. Fernique, T.: Generation and recognition of digital planes using multi-dimensional continued fractions. Pattern Recognition **42**(10), 2229–2238 (2009)

9. Fourey, S., Malgouyres, R.: Normals estimation for digital surfaces based on convolutions. Computers & Graphics **33**(1), 2–10 (2009)

10. Huxley, M.N.: Area, lattice points, and exponential sums, vol. 13. Clarendon Press (1996)

11. Kim, C.E.: Digital convexity, straightness, and convex polygons. IEEE Transactions on Pattern Analysis and Machine Intelligence (6), 618–626 (1982)

12. Klette, R., Rosenfeld, A.: Digital straightness — a review. Discrete applied mathematics **139**(1-3), 197–230 (2004)

13. Klette, R., Žunić, J.: Multigrid convergence of calculated features in image analysis. Journal of Mathematical Imaging and Vision **13**, 173–191 (2000)
14. Lachaud, J.O., Thibert, B.: Properties of gauss digitized shapes and digital surface integration. Journal of Mathematical Imaging and Vision 54(2), 162-180 (2016). https://doi.org/10.1007/s10851-015-0595-7

15. Lachaud, J.O., Coeurjolly, D., Levallois, J.: Robust and convergent curvature and normal estimators with digital integral invariants. In: Najman, L., Romon, P. (eds.) Modern Approaches to Discrete Curvature, Lecture Notes in Mathematics, vol. 2184, pp. 293-348. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58002-9_9

16. Lachaud, J.O., Provençal, X., Roussillon, T.: Two plane-probing algorithms for the computation of the normal vector to a digital plane. Journal of Mathematical Imaging and Vision 59(1), 23-39 (2017)

17. Lachaud, J.O., Vialard, A.: Geometric measures on arbitrary dimensional digital surfaces. In: Discrete Geometry for Computer Imagery: 11th International Conference, DGCI 2003, Naples, Italy, November 19-21, 2003. pp. 434-443. Springer (2003)

18. Lachaud, J.O., Vialard, A., de Vieilleville, F.: Fast, accurate and convergent tangent estimation on digital contours. Image and Vision Computing 25(10), 1572-1587 (2007)

19. Lu, J.T., Roussillon, T., Lachaud, J.O., Coeurjolly, D.: Delaunay property and proximity results of the l-algorithm for digital plane probing. Theoretical Computer Science 1011, 114719 (2024)

20. Macbeath, A.M.: A theorem on non-homogeneous lattices. Annals of Mathematics 56(2), 269-293 (1952)

21. Mérigot, Q., Ovsjanikov, M., Guibas, L.: Robust voronoi-based curvature and feature estimation. In: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. pp. 1-12 (2009)

22. Mérigot, Q., Ovsjanikov, M., Guibas, L.J.: Voronoi-based curvature and feature estimation from point clouds. IEEE Transactions on Visualization and Computer Graphics 17(6), 743-756 (2010)

23. Minkowski, H.: Geometrie der zahlen. Teubner, Leipzig (1896), §30

24. Pottmann, H., Wallner, J., Yang, Y.L., Lai, Y.K., Hu, S.M.: Principal curvatures from the integral invariant viewpoint. Computer Aided Geometric Design 24(8-9), 428-442 (2007)

25. Provot, L., Gérard, Y.: Estimation of the derivatives of a digital function with a convergent bounded error. In: International Conference on Discrete Geometry for Computer Imagery. pp. 284-295. Springer (2011)

26. Reeve, J.E.: On the volume of lattice polyhedra. Proceedings of the London Mathematical Society 3(1), 378-395 (1957)

27. Schneider, R.: Convex bodies: the Brunn-Minkowski theory, vol. 151. Cambridge university press (2013)

28. Stelddinger, P., Köthe, U.: Towards a general sampling theory for shape preservation. Image and Vision Computing 23(2), 237-248 (2005)

29. Stelddinger, P., Latecki, L.J., Siqueira, M.: Topological equivalence between a 3d object and the reconstruction of its digital image. IEEE transactions on pattern analysis and machine intelligence 29(1), 126-140 (2006)

30. Tellier, P., Debled-Rrennesson, I.: 3d discrete normal vectors. In: Discrete Geometry for Computer Imagery: 8th International Conference, DGCI'99 Marne-la-Vallée, France, March 17-19, 1999. pp. 447-458. Springer (1999)

31. Wills, M.D.: Hausdorff distance and convex sets. Journal of Convex Analysis 14(1), 109-117 (2007)
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Distance of digitized convex hull vertices to input **sphere9** shape (left) and **ellipsoid** shape (right), as a function of the gridstep *h*: convex hull vertices are much closer to the smooth input shape boundary than most digitized points, i.e. $O(h^{3/2})$. The expected constant is $2/\sqrt{\pi\rho}$, that is $2/\sqrt{9\pi} \approx 0.376$ for **sphere9** and $2/\sqrt{45\pi/\sqrt{30}} \approx 0.394$ for **ellipsoid**. Lightest green zone indicates min/max values, medium green zone indicates the standard deviation around the median value.</figcaption></figure>

## A Proofs of some properties

**Corollary 1** Let $(\mathbf{z}, \mathbf{z}')$ be a **surfel** of $X_h$. Let $\mathbf{y}$ be the nearest point on $\partial Y_h$ to $\mathbf{z}'$ and let $\sigma$ be a **facet** of $Y_h$ containing $\mathbf{y}$, with normal vector $\mathbf{n}_\sigma$. We have:

- there exists $\mathbf{x} \in \partial X \cap [\mathbf{y}, \mathbf{z}']$, that is at distance less than $h$ from $\mathbf{y}$,

- for any $\mathbf{n} \in N_X(\mathbf{x})$, $\sin^2(\mathbf{n}, \mathbf{n}_\sigma) \le \frac{1}{1+(r/h)^2}$, if $r := d_E(\mathbf{y}, \partial\sigma)$.

*Proof.* We have $\|\mathbf{y} - \mathbf{z}'\| \le \|\mathbf{z} - \mathbf{z}'\| = h$ since $\mathbf{y}$ is the closest point of $Y_h$ to $\mathbf{z}'$ and $\mathbf{z}$ belongs also to $Y_h$. Since $\mathbf{y} \in Y_h = \text{CvxH}(X_h) \subset \text{CvxH}(X) = X$ and $\mathbf{z}' \notin X_h$ so $\mathbf{z}' \notin X$, there must be a point $\mathbf{x}$ on the boundary of $X$ on the straight segment joining $\mathbf{y}$ to $\mathbf{z}'$. It follows that $\|\mathbf{y} - \mathbf{x}\| < \|\mathbf{y} - \mathbf{z}'\| \le h$, the strict relation coming from $\mathbf{x} \ne \mathbf{z}'$. The relation between normal vectors follows from Lemma 1, replacing $\epsilon$ with the distance $h$, if $\mathbf{y}$ lies in the interior of the facet $\sigma$. However if $\mathbf{y} \in \partial\sigma$, then $r := d_E(\mathbf{y}, \partial\sigma) = 0$, and the angle relation reduces to $\sin^2(\mathbf{n}, \mathbf{n}_\sigma) \le 1$, which is always true. □

**Corollary 2** For all gridsteps $h$, $0 < h < \frac{2\rho}{\sqrt{d}}$, for $\mathbf{y} \in \partial Y_h$ and any normal vector $\mathbf{w} \in N_{Y_h}(\mathbf{y})$, define $P$ as the plane orthogonal to $\mathbf{w}$ and containing $\mathbf{y}$. then for any point $\mathbf{y}' \in P$, we have that $\mathbf{y}' + t\mathbf{w}$ is outside $X$ for $t \ge \sqrt{dh}$.

*Proof.* Indeed $\mathbf{w} \in N_{Y_h}(\mathbf{y})$ implies by definition that $\phi_{Y_h}(\mathbf{w}) = \mathbf{y} \cdot \mathbf{w}$. The Hausdorff distance between $Y_h$ and $X$ is less than $\sqrt{dh}$ (Theorem 4), so

$$ \phi_X(\mathbf{w}) < \phi_{Y_h}(\mathbf{w}) + \sqrt{dh}. \qquad (8) $$

Let $\mathbf{y}'' := \mathbf{y}' + t\mathbf{w}$, for $t \ge \sqrt{dh}$. Observe that $\mathbf{y}' \cdot \mathbf{w} = \mathbf{y} \cdot \mathbf{w}$ since $\mathbf{y}'$ belongs to $P$. It follows that $\mathbf{y}'' \cdot \mathbf{w} = \mathbf{y}' \cdot \mathbf{w} + t\mathbf{w} \cdot \mathbf{w} = \mathbf{y} \cdot \mathbf{w} + t \ge \phi_{Y_h}(\mathbf{w}) + \sqrt{dh}$. Using (8), we get $\mathbf{y}'' \cdot \mathbf{w} > \phi_X(\mathbf{w})$ and $\mathbf{y}' \notin X$ by definition of the support function. □