# Recognition of digital polyhedra with a fixed number of faces

Yan Gérard

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

To cite this version:

Yan Gérard. Recognition of digital polyhedra with a fixed number of faces. DGCI (Discrete Geometry for Computer Imagery) 2016, Apr 2016, Nantes, France. 10.1007/978-3-319-32360-2_32. hal-02023827

HAL Id: hal-02023827

https://uca.hal.science/hal-02023827

Submitted on 18 Feb 2019

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.

Public Domain
Recognition of digital polyhedra with a fixed
number of faces

Yan Gérard

LIMOS - UMR 6158 CNRS / Université d'Auvergne
Clermont-Ferrand - France,
yan.gerard@udamail.fr

**Abstract.** The main task of the paper is to investigate the question of the recognition of digital polyhedra with a fixed number of facets: given a finite lattice set $S \subset \mathbb{Z}^d$ and an integer $n$, does there exist a polyhedron $P$ of $\mathbb{R}^d$ with $n$ facets and $P \cap \mathbb{Z}^d = S$? The problem can be stated in terms of polyhedral separation of the set $S$ and its complementary $S^c = \mathbb{Z}^d/S$. The difficulty is that the set $S^c$ is not finite. It makes the classical algorithms intractable for this purpose. This problem is overcome by introducing a partial order "is in the shadow of". Its minimal lattice elements are called the *jewels*. The main result of the paper is within the domain of the geometry of numbers: under some assumptions on the lattice set $S$ (if $S \subset \mathbb{Z}^2$ is not degenerated or if the interior of the convex hull of $S \subset \mathbb{Z}^d$ contains an integer point), it has only a finite number of lattice jewels. In this case, we provide an algorithm of recognition of a digital polyhedron with $n$ facets which always finishes.

**Keywords:** pattern recognition, geometry of numbers, polyhedral separation, digital polyhedron, convex sets, polytopes

# 1 Introduction

Since Bresenham's pioneer work in the 1960s years, many digital objects or primitives have been defined [1] while a large attention has been given to the question of their recognition. Surprisingly, only small interest has been paid on the digital counterparts of the old Euclidean two-dimensional figures such as triangles, quadrangles, squares, rectangles or more generally regular or irregular polyhedra with *n* faces in the field of digital geometry (Fig. 1).

There exist many mathematical results dealing with polytopes or polyhedra and lattices. From Pick's Theorem [4] to Ehrhart quasi-polynomials [8] via Barvinok polynomial time algorithm for counting the number of vertices in a polyhedron [3] with a fixed dimension, one of the mathematical stakes of the geometry of numbers is to count the integer points in a convex polytope. There are also many general results about lattice polytopes, namely polytopes with their vertices in a lattice [13, 5].

A deep interest on lattices and polyhedra comes from computer science with Integer Programming and Operations Research. In Integer Linear Programming,
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Digital polyhedra are the intersection of the classical Euclidean polyhedra with the integer lattice. A is a digital triangle, B is a digital quadrangle, C is a digital diamond.</figcaption></figure>

a polyhedron is described by linear constraints and the question is to find integer solutions. The problem considered in this paper is the converse : a set $S \subset \mathbb{Z}^d$ of integer points is given and the request is to find a minimal number of real linear constraints which characterize it. A variant is to fix a number $n$ of constraints and to determine if it is possible to characterize $S$ with $n$ linear constraints. This problem is a completely natural question of pattern recognition : given an integer $n$ and a finite subset $S$ of $\mathbb{Z}^d$, is $S$ the Gauss digitization of a convex polyhedron of $\mathbb{R}^d$ with $n$ faces? In other words, does there exist a real polyhedron $P$ verifying $P \cap \mathbb{Z}^d = S$? Such a natural question can wait an easy solution with a quite simple algorithm. Unfortunately, even by adding some assumptions, we only provide a weak result : the problem is decidable.

We prove it in several steps. First, in Sect.2, we state the problem of recognition of a digital polyhedron with $n$ faces as a question of polyhedral separation. Secondly, in Sect.3, we investigate the geometry of the problem by introducing a partial order and prove that under some assumptions, the number of minimal lattice elements is finite. At last, in Sect. 4, we present an algorithm and prove that it terminates (under the same assumptions as in Sect.3).

## 2 Problem statement

Let us first recall some basics of the geometry of polytopes and polyhedra: a polytope of $\mathbb{R}^d$ is the convex hull of a finite set of points of $\mathbb{R}^d$ while a polyhedron is usually defined as the intersection of finitely many closed half-spaces $v_i \cdot x \ge h_i$ for $i$ going from 1 to $n$. The main difference is that polyhedra can be unbounded while polytopes are always compact. Nevertheless Minkowski-Weyl theorem [14] states that bounded polyhedra (bounded means here for instance that they do not contain any half-lines) are polytopes and conversely.

Now, we introduce the lattice $\mathbb{Z}^d$. The objects investigated in the paper are the intersection between a real convex polyhedron $P$ and $\mathbb{Z}^d$. This intersection is usually called the Gauss digitization of $P$ and we prefer to introduce a specific notation taking into account the number of constraints:

**Definition 1.** A set $S \subset \mathbb{Z}^d$ is a **digital n-polyhedron** if there exist $n$ closed half-spaces $H_i$ defined by linear inequalities $v_i \cdot x \ge h_i$ with $v_i \in \mathbb{R}^d / \{(0)_{1 \le i \le d}\}$
and $h_i \in \mathbb{R}$, such that the polyhedron $P = \bigcap_{1 \le i \le n} H_i$ has an intersection with the lattice $\mathbb{Z}$ equal to $S$:

$$S = P \cap \mathbb{Z}^d = \{x \in \mathbb{Z}^d | \forall i \in \{1 \cdots n\}, v_i \cdot x \ge h_i\}.$$

Definition 1 is restricted to polyhedra and not polytopes although the paper deals mainly with finite sets $S$. The reason is that it is more convenient for our purpose and the difference is slight. There exist some finite subsets of $\mathbb{Z}^d$ which are digital $n$-polyhedra and not $n$-polytopes (the intersection of a polytope with $n$ faces and the lattice). These digital polyhedra remain, however, pathological. Their recession cone is for instance degenerated with an irrational direction (otherwise, it can be proved that an unbounded digital $n$-polyhedron contains an infinite number of integer points).

We notice now that if $S$ is a digital $n$-polyhedron, it is also a $m$-polyhedron for all $m \ge n$ (just by adding useless linear constraints). Thus, given a finite subset $S$ of $\mathbb{Z}^d$, a question is to determine the minimum $n$ for which $S$ is a digital $n$-polyhedron. There is of course a first condition on the convexity of $S$. If $S$ is not digitally convex (the intersection of the real convex hull conv($S$) of $S$ with the lattice $\mathbb{Z}^d$ is exactly $S$), then $S$ is not a digital $n$-polyhedron. Moreover, if $S$ is convex, it is by definition the intersection of its convex hull with the lattice. This convex hull conv($S$) is a polytope. If its affine dimension is $d$, then, it has some faces of dimension $d-1$. Their cardinality provides an upper bound for the minimal number of faces $n$ of a polyhedron $P$ verifying $P \cap \mathbb{Z}^d = S$.

The problem investigated in this paper is the following:

**Problem 1 (DigitalPolyhedronRecognition(d, n, S)).**

**Input:** A dimension $d$, an integer $n$ and a finite subset $S$ of $\mathbb{Z}^d$.

**Output:** Is $S$ a digital $n$-polyhedron? If yes, find a satisfying polyhedron $P \subset \mathbb{R}^d$ with $n$ faces and $S = P \cap \mathbb{Z}^d$.

We can also state Problem 1 as a specific instance of a more generic problem of separation of two sets by a polyhedron with $n$ faces.

**Problem 2 (PolyhedralSeparation(d, n, S, T)).**

**Input:** A dimension $d$, an integer $n$ and two subsets $S$ and $T$ of $\mathbb{R}^d$.

**Output:** Find a polyhedron $P$ defined by $n$ linear inequalities with $S$ inside $P$ and $T$ outside.

In problem 2, the question is to find $n$ vectors $v_i \in \mathbb{R}^d$ and constants $h_i \in \mathbb{R}$ verifying $\forall x \in S, \forall i \in \{1 \cdots n\}, v_i \cdot x \le h_i$ and $\forall x \in T, \exists i \in \{1 \cdots n\}, v_i \cdot x > h_i$. This problem of polyhedral separability has been intensively investigated in the 1980s and 1990s years. The question of separating two sets by an hyperplane, namely PolyhedralSeparation(d, 1, S, T) can be solved with linear programming with a worst case linear-time complexity in fixed dimension [11]. In dimension $d=2$, an algorithm with a worst case complexity in $O(k \log(k))$ ($k$ is the total number of points $|S| + |T|$) is given in [7] for finding the minimum feasible number of faces $n$. It solves PolyhedralSeparation(2, n, S, T) in polynomial time. In
arbitrary dimension, the problem *PolyhedralSeparation(d, n, S, T)* becomes NP-complete [12] even with *n* = 2: the 2-separability *PolyhedralSeparation(d, 2, S, T)* is NP-complete. In fixed dimension *d* = 3, as far as we know, the complexity of the problem remains open.

There exist other results in the framework of nested polyhedra introduced
by Victor Klee. In this class of problems, the two sets of points *S* and *T* given in
the input are replaced by two polyhedra *S'* and *T'*. The solution has to contain
*S’* and be contained by *T’*. The problem is solved efficiently in dimension *d* = 2
[2], and is NP-complete from the fixed dimension *d* = 3 [6].

For general polyhedral separation *PolyhedralSeparation(d, n, S, T)*, a brute-force approach is to proceed in the following way:

- Solve *PolyhedralSeparation(d, 1, S, T')* with linear programming for all subsets *T'* of *T*.

- Find *n* subsets $T^i$ with $T = \bigcup_{1 \le i \le n} T^i$ and where for each index $i \in \{1 \cdots n\}$, the instance *PolyhedralSeparation(d, 1, S, T^i)* is feasible.

Even if *PolyhedralSeparation(d, n, S, T)* is NP-complete, we need an algorithm
for solving the problem with finite sets *S* and *T* because it is used as routine
in Sect.4. *PolyhedralSeparation(d, n, S, T)* provides also a generic way to express
the problem *DigitalPolyhedronRecognition(d, n, S):*

**Lemma 1.** Let *S* be a subset of *Z*^d and *S*^c its complementary in *Z*^d. The problems *DigitalPolyhedronRecognition(d, n, S)* and *PolyhedralSeparation(d, n, S, S*)^c* are equivalent.

Lemma 1 is straightforward. It shows that our task is to tackle a specific
instance of *PolyhedralSeparation(d, n, S, T)* with the integer points outside from
*S* as outliers. Its main feature is that the set *S*^c is infinite. It makes this instance
intractable for the usual algorithms of computational geometry. Hence, the goal
of the paper is now to determine how we can deal with it.

A first idea is to reduce the set of outliers $T = S^c$ to a smaller subset, for instance, by using of the outer contour of $S$ (we do not precise the notion of neighborhood yet). We consider the instance *Separation(d, n, S, OuterContour(S))* where the set of outliers is the outer contour of $S$. As *OuterContour(S)* is a subset of the complementary $S^c$ of $S$, a solution *Separation(d, n, S, S*)^c$ is also a solution of *Separation(d, n, S, OuterContour(S))* but the converse is false. Although such counterexamples are specific (in dimension $d = 2$, the counterexamples $S$ should have an acute angle $\theta < \frac{\pi}{4}$), they can be easily built (Fig.2). Thus, the infinite set $S^c$ can not be replaced by the outer contour of $S$ without precautions. It requires at least a better understanding of the geometry of the problem and of the properties of the lattice sets in this framework.

3 The shadows and the jewels

Let us consider the general problem *PolyhedralSeparation(d, n, S, T)* of polyhe-
dral separation of two subsets *S* and *T* by a polyhedron with *n* faces.
<figure><img src="image_3.png" /><figcaption>Fig. 2. On the left, a finite subset $S \subset \mathbb{Z}^2$ and its outer contour, in red. On the right, the polyhedron $P$ is a solution of Separation(2, 3, S, OuterContour(S)) but it is not a valid solution of Separation(2, 3, S, S<sup>c</sup>) because there are integer points $x$ in $P$ outside from the outer contour of $S$.</figcaption></figure>

## 3.1 A partial order

We first notice that, in an instance PolyhedralSeparation(d, n, S, T), the set $S$ can be replaced by its real convex hull conv(S) without changing the set of solutions. The convex hull of $S$ and its vertices play an important role in the problem. On the side of $T$, there is no interest in considering its convex hull conv(T) but there exists another interesting structure -a partial order- that we introduce now. Let us start with the notion of shadow. Given a point $x \in \mathbb{R}^d$, we define its shadow relatively to $S$ as the points $y$ of $\mathbb{R}^d$ partially hidden from $S$ by $x$, as if the convex hull of $S$ was a light source and $x$ a point generating a shadow (Fig.3):

**Definition 2.** Let $S$ be a subset of $\mathbb{R}^d$ and $x$ a point of $\mathbb{R}^d$. The shadow of $x$ relatively to $S$ is the set of points $y \in \mathbb{R}^d$ whose convex hull with $S$ contains $x$:

$$ \text{shadow}_S(x) = \{y \in \mathbb{R}^d / x \in \text{conv}(S \cup \{y\})\}. $$

If $x$ is in the convex hull of $S$, its shadow is the whole space $\mathbb{R}^d$. The definition is interesting only if the point $x$ does not belong to the convex hull of $S$. We provide another characterization of the shadow of $x$:

**Lemma 2.** Let $S$ be a subset of $\mathbb{R}^d$ and $x$, $y$ two points of $\mathbb{R}^d$ different from each other. The point $y$ belongs to the shadow of $x$ if and only if the half-line starting from $y$ and passing through $x$ crosses the convex hull of $S$.

*Proof.* By definition, $y$ is in the shadow of $x$ if the convex hull of $\{y\} \cup S$ contains $x$. It follows from Caratheodory theorem that there exists a $m$-simplex $\Delta$ with its vertices in $\{y\} \cup S$ containing $x$. Its vertices are denoted $x_k$ with $k$ going from 0 to $m$. If we assume that $x$ is not in the convex hull of $S$, then we can state $x_0 = y$ since $y$ is necessarily one of the vertices of the simplex. The property $x \in \Delta$ provides the existence of $m + 1$ reals $\lambda_k \in [0, 1]$ with a sum $\sum_{k=0}^d \lambda_k = 1$ and $x = \sum_{k=0}^m \lambda_k x_k$. As $x_0$ is $y$, it follows $x - \lambda_0 y = \sum_{k=1}^m \lambda_k x_k$. After reorganization, we have

$$ y + \frac{1}{\sum_{k=1}^{m} \lambda_k} (x - y) = \frac{1}{\sum_{k=1}^{m} \lambda_k} \sum_{k=1}^{m} \lambda_k x_k $$
which proves the lemma.

□

We observe many other nice properties. First, the shadow of a point is convex (Lemma 2 allows to prove that if $y$ and $y'$ are in the shadow of $x$, then the segment $[y, y']$ is also included in it). Secondly, the set $S$ being fixed, the binary relation "is in the shadow of" defined on $(\mathbb{R}^d/\text{conv}(S))^2$ is reflexive, transitive and antisymmetric (again with Lemma 2). It is a partial order and the set of its minimal elements is going to play an important role (cf the jewels).

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** On the left, the shadow of $x$ is the set of points whose convex hull with $S$ contains $x$. On the right, given two subsets $S$ and $T$, the shadow of $T$ (in grey) is the union of the shadows of the points of $T$. Some of the points of $T$ are in the shadow of others. The minimal elements of $T$ according to this partial order are called the *jewels* of $T$. They are colored in red.</figcaption></figure>

The shadow of a set $T$ is defined as the union of the shadows of its elements: $\text{shadow}_S(T) = \bigcup_{x \in T} \text{shadow}_x(T)$. It is fully determined by the minimal elements of $T$ (minimal according to the relation "is in the shadow of"). We call these minimal elements the *jewels* of $T$:

**Definition 3.** Let $S$ and $T$ be two subsets of $\mathbb{R}^d$. A point $x \in T$ is a *jewel* of $T$ if there exist no point $x' \in T$ verifying $x \in \text{shadow}_S(x')$ (Fig. 3). We denote $\text{jewels}_S(T)$ their set.

The jewels of $T$ are the counterparts of the vertices of the convex hull of $S$ on the side of $T$. By construction, we have the following equivalence:

**Lemma 3.** Let $S$ and $T$ be two subsets of $\mathbb{R}^d$. We have the equivalence between $\text{PolyhedralSeparation}(d, n, S, T)$ and $\text{PolyhedralSeparation}(d, n, S, \text{jewels}_S(T))$.

*Proof.* Let the polyhedron $P$ be a solution of $\text{PolyhedralSeparation}(d, n, S, T)$. As the set $\text{jewels}_S(T)$ of the jewels is a subset of $T$, $P$ is also a solution of $\text{PolyhedralSeparation}(d, n, S, \text{jewels}_S(T))$. To prove the converse, let us assume that $P$ is a solution of $\text{PolyhedralSeparation}(d, n, S, \text{jewels}_S(T))$. If $P$ is not a
solution of *PolyhedralSeparation*(*d*, *n*, *S*, *T*), it means that *P* contains a point *x* of *T*. Two cases can occur : First case, *x* is a jewel, but it contradicts that *P* is a solution of *PolyhedralSeparation*(*d*, *n*, *S*, *jewels*<sub>*S*</sub>(*T*)). Second case, *x* is not a jewel. Then, it is not minimal in *T* according to the partial order. Let *y* be a jewel of *T* such that *y* in the convex hull of {*x*} ∪ *S*. It follows that *y* is in *P*. It contradicts that *P* is solution of *PolyhedralSeparation*(*d*, *n*, *S*, *jewels*<sub>*S*</sub>(*T*)). □

**3.2 About the number of lattice jewels**

We are mainly interested in the problem *PolyhedralSeparation*(d, n, S, T) with a
lattice set S ⊂ Z^d and its complementary T = S^c in Z^d. The main difficulty is
that the set T = S^c is infinite which makes it intractable for usual algorithm.
Lemma 3 leads to consider the jewels of the complementary of S in the lattice.
As there is no ambiguity in the following, we provide some lighter expressions
and notations:

**Definition 4.** Let $S$ be a subset of $\mathbb{R}^d$. The **lattice jewels** of $S$ are the jewels of the complementary $S^c = \mathbb{Z}^d / (\mathbb{Z}^d \cap S)$ of $S$ in the lattice $\mathbb{Z}^d$ relatively to $S$ (Fig.4). We denote **jewels**$_S$ the set $\text{jewels}_S(S^c)$.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Three lattice sets in dimension *d* = 2 in blue, their convex hulls in green, their lattice jewels in red and their crown in grey.</figcaption></figure>

Thanks to Lemma 3, we can replace the set $T = S^c$ by its lattice jewels
$jewels_S$ and solve *PolyhedralSeparation*(*d*, *n*, *S*, *jewels*<sub>*S*</sub>). There are some cases
where this reduction is not sufficient to make the instance tractable: the set
of the lattice jewels is still infinite (Fig.5). We can, nevertheless, prove that it
can not happen under some assumptions. This result is within the area of the
geometry of numbers:

**Theorem 1.** Let $S$ be a finite subset of $\mathbb{Z}^d$.

- If the interior of the convex hull of S contains an integer point (i)

- or, if $d = 2$, and the affine dimension of $S$ is 2 (ii),

the set of the lattice jewels *jewels*<sub>S</sub> of *S* is *finite*.
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** An example of a finite lattice set with an infinite number of lattice jewels: on the left, the pyramid $S = \{(-1, -1, 0), (-1, 0, 0), (-1, 1, 0), (0, -1, 0), (0, 0, 0), (0, 1, 0), (1, -1, 0), (1, 0, 0), (1, 1, 0), (0, 0, 1)\}$. On the right, the complementary of the pyramid $S^c$ has infinitely many jewels colored in brown: each point $(a, b, 1) \in \mathbb{Z}^3$ with coprime a and b is a lattice jewel.</figcaption></figure>

*Proof.* We assume that the set of the lattice jewels of $S$ is infinite and prove a contradiction with (i) or (ii). Under this assumption, we can consider a sequence of lattice jewels $x_k \in jewels_S$ with $x_k$ different from $x_{k'}$ if $k \neq k'$ and for any $k \in \mathbb{N}, x_k \neq (0)_{1 \le i \le d}$. We consider the direction $y_k = \frac{x_k}{\|x_k\|_2}$ which belongs to the hypersphere $\mathbb{S}^d$ centered at the origin and of radius 1. As $\mathbb{S}^d$ is compact, the sequence $y_k$ admits a convergent subsequence $y_k'$ with a non null limit $z$: $\lim_{k \to +\infty} y_k' = z$. It means that the corresponding subsequence of points $x_k' \in jewels_S$ is going in direction $z$ (A).

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** Case (i) : On the left, a set $S$ of $\mathbb{Z}^d$, its convex hull $\text{conv}(S)$ and the polyhedron $\text{conv}(S) + \mathbb{R}^+z$. In the middle, an integer point $x$ in the interior of $(\text{conv}(S) + \mathbb{R}^+z)/\text{conv}(S)$. On the right, a ball in the convex hull of $S$ and an integer point on the half-line from its center in direction $z$. By construction, the shadow $\text{shadow}_B(x)$ of $x$ relatively to the ball $B$ contradicts the existence of jewels tending in direction $z$.</figcaption></figure>

In the case of (i), where the interior of the convex hull of $S$ contains an integer point $s$, let us prove that there exists an integer point in the interior of $(\text{conv}(S)+\mathbb{R}^+z)/\text{conv}(S)$ (B1). If the direction $z$ is rational (the line $\mathbb{R}z$ contains integer points), then by translation, the half-line $s+\mathbb{R}^+z$ contains infinitely many integer
points. The ones which are not in the convex hull of $S$ and on the good side
towards it are in the interior of $(\operatorname{conv}(S) + \mathbb{R}^+z)/\operatorname{conv}(S)$. Let's take such a point
and call it $x$ (B1). We have $x = s + \lambda z$ and we notice that by definition of $s$, there
is a ball $B$ centered at $s$ with a strictly positive radius $r$ included in the convex
hull of $S$ (B2). Now let us investigate the sub-case of an irrational direction: if
$z$ is not a rational direction, we use a classical result of simultaneous rational
approximation. As $s$ is in the interior of the convex hull of $S$, there exists a ball
$B_r(s)$ centered at $s$ of radius $r > 0$ included in the interior of the convex hull of
$S$. Then, we consider the Minkowski sum $B_r(s) + \mathbb{R}^+z$. By construction this set
is in the interior of $\operatorname{conv}(S) + \mathbb{R}^+z$. The simultaneous rational approximation, for
instance with Dirichlet's approximation theorem, allows to prove that $B_r(s) +
\mathbb{R}^+z$ contains infinitely many integer points. Another proof of this result can be
obtained with Minkowski's theorem by using a sequence of symmetric cylinders
$B_{r_k}(s) + \mathbb{R}z$ with $r_k$ tending to 0. Due to its infinite volume, $B_{r_k}(s) + \mathbb{R}z$ contains
at least two symmetric integer points $x_k$ and $2s - x_k$ different from $s$ and by
stating $r_{k+1} < d(x_k, s + \mathbb{R}z)$, we obtain two new ones... and so on. It proves
that $B_r(s) + \mathbb{R}^+z$ and then also $\operatorname{conv}(S) + \mathbb{R}^+z$ contain infinitely many integer
points. As they cannot be all in the convex hull of $S$, it proves (B1) in the
sub-case of an irrational direction: we have an integer point $x$ in the interior of
$(\operatorname{conv}(S) + \mathbb{R}^+z)/\operatorname{conv}(S)$. We can also notice that $x$ can be written $s' + \lambda z$
with a ball $B$ centered at $s'$ contained by the convex hull of $S$ (B2).

With (A), (B1) and (B2), the last step of the proof is to show that the
shadow of $x$ in the interior of $(\operatorname{conv}(S) + \mathbb{R}^+z)/\operatorname{conv}(S)$ contradicts the existence
of lattice jewels $x'_k$ going to infinite in direction $z$ (Fig.6). The sequence of the
integer points $x'_k$ is necessarily going to infinite since there is only a finite number
of lattice points in discrete balls of finite radius. It follows that the equality
$$ \lim_{k \to +\infty} \frac{x_k - x}{||x'_k - x||} = \lim_{k \to +\infty} \frac{x'_k}{||x'_k||} = z. $$
Since the convex hull of $S$ contains the
ball $B$ centered at $s$ (rational sub-case) or $s'$ (irrational sub-case), the shadow
$\text{shadow}_S(x)$ of $x$ contains the shadow $\text{shadow}_B(x)$. As the points $x'_k$ are lattice
jewels of $S$, they don't belong to the shadow of any other integer point and thus,
they are not in $\text{shadow}_B(x)$ which is a cone centered around the direction $z$ and
with $x$ as vertex. It is in contradiction with the limit $\lim_{k \to +\infty} \frac{x'_k - x}{||x'_k - x||} = z$.

In the case of (ii), the same arguments are used. If $S$ is not degenerated, since
we are in dimension $d=2$, the polyhedron $\operatorname{conv}(S) + \mathbb{R}^+z$ is bounded by two
half-lines $y + \mathbb{R}^+z$ and $y' + \mathbb{R}^+z$. If the direction $z$ is rational (Fig.7), then there
are integer points $x$ and $x'$ on each half-line. Their shadows $\text{shadow}_S(x)$ and
$\text{shadow}_S(x')$ cover two angular sectors around the polyhedron $\operatorname{conv}(S) + \mathbb{R}^+z$.
As the jewels are not in the shadows of other integer points, the only possibility
for the sequence of jewels $x'_k$ to go to infinite in direction $z$ is to be in the strip
$\operatorname{conv}(S) + \mathbb{R}^+z$. It follows that we have an integer point $x'_k$ in the interior of
$\operatorname{conv}(S) + \mathbb{R}^+z$ and outside from the convex hull. As in case (i), it leads to a
contradiction. If the direction $z$ is irrational, the existence of an integer point
in $(\operatorname{conv}(S) + \mathbb{R}^+z)/\operatorname{conv}(S)$ is a consequence of the density of $\mathbb{Q}$ in $\mathbb{R}$. It leads
again to a contradiction as in case (i). $\square$
by adding one or more point of $X$. This addition is however not sufficient to ensure at the end that the algorithm finishes. We add in $T$ all the integer points of the complementary of $S$ which are in a ball $B_X$ centered at the barycenter of $S$ (the only thing which matters here is that the center of the ball is fixed, it could even be outside from $S$) and containing at least a point $x$ of $X$. We proceed again to the resolution *PolyhedralSeparation*($d, n, S, T$) and repeat the process until finding a negative answer or a valid polyhedron $P$.

<caption>**Algorithm 1 Incremental recognition :** *DigitalPolyhedronRecognition*(*d*, *n*, *S*)</caption>

1: $T \leftarrow \text{OuterContour}(S)$
2: polyhedron $\leftarrow F_{\text{separation}}(d, n, S, T)$
3: **if** (polyhedron = null) **then**
4:     **return** null
5: $X \leftarrow \text{polyhedron} \cap S^c$
6: **while** $\text{card}(X) > 0$ **do**
7:     $T \leftarrow T \cup B_X$
8:     polyhedron $\leftarrow F_{\text{separation}}(d, n, S, T)$
9:     **if** (polyhedron = null) **then**
10:     **return** null
11: $X \leftarrow \text{polyhedron} \cap S^c$
12: **return** polyhedron

**Theorem 2.** Let $S$ be a finite subset of $\mathbb{Z}^d$.

- If the interior of the convex hull of $S$ contains an integer point (i)

- or, if $d = 2$, and the affine dimension of $S$ is 2 (ii),

then Algorithm 1 ends in a finite time.

*Proof.* Under the assumptions (i) or (ii), according to Theorem 1, the set $S$ has only a finite set of lattice jewels. As the set $T$ is containing growing balls $B_X$ at each step of the algorithms, if it is running an infinite number of times, there is a step after which $T$ is going to contain all the lattice jewels of $S$. According to Lemma 3, a polyhedron $P$ obtained at this step cannot contain any other integer point than the ones of $S$.

## 4.1 Conclusion

The main task of the paper is to investigate the question of the recognition of digital polyhedra with a fixed number of facets. This natural question of pattern recognition leads to the world of the geometry of numbers which has been deeply investigated in the framework of Integer Programming. We have introduced the new notion of lattice jewel. They are the minimal lattice points under the partial order "is in the shadow of". Our main result is that under some assumptions, a
lattice set $S$ has only a finite number of lattice jewels. It is significant because it allows to reduce a problem of polyhedral separation with an infinite set of outliers to a finite set. Even if we don't compute explicitly the lattice jewels of $S$, it provides an algorithm of recognition of digital $n$-polyhedra with the guarantee that it finishes (under some assumptions on $S$).

This work should be continued in several directions:

- Determine the complexity of the problem in fixed dimensions $d > 2$ and provide some algorithms, perhaps based on the explicit computation of the jewels.

- Provide weaker assumptions in Theorem 1, for instance with the lattice width.

- Consider the problem of recognition of rectangles, squares, rotated polyominos or other figures in dimension 2 or 3.

This work is a first step in a very wide range of open questions that relate to both the geometry of numbers, computational geometry and digital geometry.

## References

1. DGtal: Digital geometry tools and algorithms library, url http://dgtal.org

2. Aggarwal, A., Booth, H., O'Rourke, J., Suri, S., Yap, C.: Finding minimal convex nested polygons. Information and Computation 83(1), 98–110 (1989)

3. Barvinok, A.I.: Lattice points and lattice polytopes. In: Handbook of Discrete and Computational Geometry, Second Edition., pp. 153–176. Chapman and Hall/CRC (2004)

4. Beck, M., Robins, S.: Computing the Continuous Discretely. Undergraduate Texts in Mathematics, Springer (2007)

5. Blichfeldt, H.F.: A new principle in the geometry of numbers, with some applications. Transactions of the American Mathematical Society 15, 227–235 (1914)

6. Das, G., Joseph, D.: The complexity of minimum convex nested polyhedra. In: Proceedings of the 2nd Canadian Conference of Computational Geometry. pp. 296–301 (1990)

7. Edelsbrunner, H., Preparata, F.: Minimum polygonal separation. Information and Computation 77(3), 218–232 (1988)

8. Ehrhart, E.: Sur les polyèdres rationnels homothétiques à n dimensions. Comptes Rendus de l'Académie des Sciences 254, 616–618 (1962)

9. Haase, C., Ziegler, G.: On the maximal width of empty lattice simplices. European Journal of Combinatorics 21, 111–119 (2000)

10. Lenstra, H.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 538–548 (1983)

11. Megiddo, N.: Linear-time algorithms for linear programming in $\mathbb{r}^3$ and related problems. SIAM J. Comput. 12(4), 759–776 (1983)

12. Megiddo, N.: On the complexity of polyhedral separability. Discrete and Computational Geometry 3(4), 325–337 (1988)

13. Scarf, H.E.: Integral polyhedra in three space. Mathematics of Operations Research 10, 403–438 (1985)

14. Ziegler, G.: Lectures on Polytopes. Graduate Texts in Mathematics, Springer (1995)