Chapter One Introduction

Computational geometry studies algorithms that solve geometric problems, and, as a consequence, problems that can be stated in terms of geometry. Some of its applications are related to computer graphics, robotics, computeraided design, machine learning or augmented reality. The earliest studies related to computational geometry date back to the second half of the 19 th century with work on quadratic forms by Dirichlet [START_REF] Lejeune | Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen[END_REF] and Sylvester [START_REF] Joseph | The Laws of Verse: Or Principles of Versification Exemplified in Metrical Translations, Together with an Annotated Reprint of the Inaugural Presidential Address to the Mathematical and Physical Section of the British Association at Exeter[END_REF].

Computation geometry emerged in the 1970's from fields such as mathematical programming [START_REF] Donald | An algorithm for convex polytopes[END_REF] and computer-aided design [START_REF] Forrest | Ii. current developments in the design and production of three-dimensional curved objects-computational geometry[END_REF]. Convex hulls were one of the first topics of attention in computational geometry with a first paper by Chand and Kapur in 1970 [START_REF] Donald | An algorithm for convex polytopes[END_REF], and then in 1972 by Graham [START_REF] Graham | An efficient algorithm for determining the convex hull of a finite planar set[END_REF]. Convexity is still to this day very present in computational geometry and will be the main topic of attention of this dissertation.

Digital geometry, a field closely related to computational geometry, studies the geometry of points with integer coordinates, those points are also known as lattice points [START_REF] Klette | Digital geometry: Geometric methods for digital picture analysis[END_REF]. The motivation behind digital geometry comes from the fact that digital devices such as cameras, lidars or scanners in medical imaging 1 provide a discrete representation of the real world. As a consequence, continuous geometry is not adapted to work on such inputs and usually involves a transformation on the inputs that implies approximations. In this context, the goal of digital geometry is to build an alternative geometry based on a restricted class of objects such as pixels, voxels, or lattice sets, and relying heavily on integer arithmetic. As a consequence, digital geometry arises a lot of questions concerning the connection that exists between the discrete and the continuous. Despite studies related to digital geometry existing since the end of the 19 th century with works such as Minkowski's on the geometry of numbers [START_REF] Minkowski | Geometrie der Zahlen[END_REF], or results like Pick's theorem [START_REF] Pick | Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines für Böhmen "Lotos[END_REF], digital geometry started in the 1960's for computer graphics, because a screen is just a lattice or a grid of pixels, with algorithms such as Bresenham's [START_REF] Jack | Algorithm for computer control of a digital plotter[END_REF] line drawing algorithm.

From there, questions arose and the field expanded with topics such as digital topology, digital manifolds, the study of properties of digital sets or tomography. Nowadays, some of the main application areas of digital geometry are in image analysis [START_REF] Klette | Digital geometry: Geometric methods for digital picture analysis[END_REF] (notably medical imaging [START_REF] Fang | Digital geometry image analysis for medical diagnosis[END_REF]), computer graphics [START_REF] Klette | A Comparative Discussion of Distance Transforms and Simple Deformations in Image Processing[END_REF], and integer linear programming [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

Not unlike in computational geometry, convexity is a core component in digital geometry. Some of the earliest work related to digital geometry where about counting points in convex polyhedra. Minkowski's theorem [START_REF] Minkowski | Geometrie der Zahlen[END_REF] relates the number of lattice points inside a convex centrally symmetric polytope to its volume. In 2 dimension, Pick's theorem [START_REF] Pick | Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines für Böhmen "Lotos[END_REF] gives an equality relating the number of lattice points inside and on the boundary of a convex polygon P , whose vertices are lattice points, to the area of P . Studies on this topic of reporting lattice points inside convex polytopes continued throughout the 20 th century and are still considered to this day, with work related to Ehrart's polynomials [START_REF] Ehrhart | Geometrie diophantienne-sur les polyedres rationnels homothetiques an dimensions[END_REF][START_REF] Liu | On positivity of Ehrhart polynomials[END_REF] and Barvinok's algorithm [START_REF] Alexander | A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed[END_REF]. A natural definition of digital convexity that arises is the following:

A lattice set S ∈ Z d is said to be digital convex if there exists a convex polytope P ∈ R d such that P ∩ Z d = S. We can easily notice that if such a polytope P exists then the convex hull of S, that we denote conv(S), also satisfies the property conv(S) ∩ Z d = S. Hence an equivalent but simpler definition of digital convexity is the following:

A lattice set S ∈ Z d is said to be digital convex if conv(S) ∩ Z d = S. This definition of digital convexity is the one that we will use throughout this dissertation. However, it is worth noting that several other definitions of digital convexity have been investigated throughout the years [START_REF] Chassery | Discrete convexity: Definition, parametrization, and compatibility with continuous convexity[END_REF][START_REF] Baran | ON THE COMPU-TATION OF THE DIGITAL CONVEX HULL AND CIRCULAR HULL OF A DIGITAL REGION[END_REF][START_REF] Kim | Convex Digital Solids[END_REF][START_REF] Kim | Digital Straight Lines and Convexity of Digital Regions[END_REF][START_REF] Kishimoto | Characterizing Digital Convexity and Straightness in Terms of Length and Total Absolute Curvature[END_REF][START_REF] Lachaud | An alternative definition of digital convexity[END_REF].

These definitions were created in order to guarantee that a digital convex set is connected (in terms of the induced grid subgraph), which simplifies several algorithmic problems. Indeed, in a digital convex set S of n points, the distance between a point p and its nearest neighbour p 1 ∈ S is not bounded by any function of n. Moreover, The diameter of a digital convex set of at least 2 points can be arbitrarily large (Fig. 1.1).

The presence of convex sets in the core of fundamental problems, as well as their peculiar geometric properties motivates the study of their properties.

Results

The main results of this dissertation are algorithms related to the recognition of digital convex sets.

First, for any unordered lattice set S of n points, we present an algorithm relying on the quickhull algorithm that tests digital convexity in linear time relative to n. Previous algorithms testing digital convexity in linear time, such as those presented in [START_REF] Brlek | Lyndon + Christoffel = digitally convex[END_REF][START_REF] Debled-Rennesson | Detection of the discrete convexity of polyominoes[END_REF] relied on a specific input representation which meant they couldn't be applied on arbitrary unordered sets. We then use this result to solve the optimal digital convex polygon problem in linear time relative to n. This problem whose decidability has been shown in 2017 [START_REF] Gerard | About the Decidability of Polyhedral Separability in the Lattice Z d[END_REF] asks, for a digital convex set S, to find a polygon P ∈ R 2 that verifies P ∩Z 2 = S such that P is minimal in regard to the number of vertices.

Finally, this dissertation considers a problem stated in 2005 in [START_REF] Chassery | Optimal shape and inclusion[END_REF], which is the digital versions of the potato peeling problem [START_REF] Chang | A polynomial solution for the potatopeeling problem[END_REF], and presents a polynomial time algorithm that finds, for any lattice set S the largest digital convex subset C ∈ S, as well as the first polynomial time algorithm that finds, for any lattice set S, and any integer k > 1 the largest subset C ∈ S defined as

C = C 1 ∪ C 2 ∪ ... ∪ C k ∈ S such that for all i ∈ 1..k C i is digital convex.
This dissertation is divided as follows.

In Section 2.1, we present the convexity and several convex hull algorithms introducing classic strategies used in computational geometry, such as "divide and conquer" and angular sorting. One of the presented algorithms will be used in the result presented in this dissertation.

In Section 2.2, we cover some basic concept associated to digital geometry, number geometry and digital convexity. Section 2.3 presents previous work on simplex range searching, with an emphasis on linear size data structures, as well as data structures that allows logarithmic query time.

In Chapter 3 we present our results on digital convex set recognition, and in Chapter ?? we do the same with our results concerning the digital potato peeling problem.

Finally, in Chapter 5 we present conclusions along with directions for future works in computational digital geometry.

Chapter Two

Literature review

In this chapter, we present terms and results that will be used throughout this dissertation, as well as some other related well known results.

In Section 2.1, we present convexity and its uses in computational geometry, along with several convex hull algorithms. In Section 2.2, we introduce digital geometry and digital convexity. In Section 2.3, we present several simplex range searching structures that are commonly used in computational geometry.

Convexity

In this section we present the concepts of convexity and convex hull, and we present several known algorithms that compute the convex hull of any set of points. In geometry, a subset S of an Euclidean space is convex if and only if for any pair of points p 1 , p 2 ∈ S, the line segment p 1 p 2 ∈ S. The convex hull of a set S, denoted conv(S) throughout this dissertation, is the smallest convex set such that S ∈ conv(S).

The QuickHull Algorithm

Quickhull is one of the many early algorithms to compute the convex hull of a given set of n points S. In dimension 2 its worst-case time is O(n 2 ). Despite its running time being vastly dependant on the number of vertices on the convex hull, quickhull has shown to be an effective algorithm for inputs having a low number of convex hull vertices relative to the number of input points, such as uniformly distributed input points for instance. Furthermore, for some inputs and variations of the algorithm, the complexity is reduced to O(n) [START_REF] De | Computational Geometry: Algorithms and Applications. 3rd ed[END_REF][START_REF] Scott | A Proof for a QuickHull Algorithm[END_REF].

In order to compute the convex hull of a given set of points S, the quickhull algorithm starts by initializing a convex polygon in the following manner. First it computes the top-most and bottom-most points of the set. Surely, these two points belong to the convex hull. Let ℓ be the line defined by these two points.

Then, the algorithm computes the farthest point from ℓ, on both sides of ℓ.

The (at most) four points we computed describe a convex polygon that we call a partial hull, which is a subset of the vertices of the convex hull of S.

All points contained in the interior of the partial hull are discarded from S as they surely do not belong to its convex hull (Fig. 2.1).

After the initialization step, the algorithm adds vertices one by one to the partial hull until it obtains the entire convex hull. For each edge e of the partial hull, the following elimination procedure is applied. Let v denote e's outwards normal vector. The algorithm searches for the extreme point in direction v.

If this point's distance from the edge e is 0, then the edge e is an edge of the convex hull. Otherwise, we add to the convex hull the farthest point found, and the points that are inside the new partial hull are discarded. (Fig. 2.2).

Graham Scan Algorithm

Graham scan [START_REF] Graham | An efficient algorithm for determining the convex hull of a finite planar set[END_REF] is a convex hull algorithm. For an input set S of n points that Graham scan runs in O(n log n) time, which is the lower bound [START_REF] Andrew | A lower bound to finding convex hulls[END_REF] for convex hull algorithms in the decision tree model. Graham scan relies on the fact that computing the convex hull of a simple polygon can easily be done picking any point p in S, and sorting the points of S angularly around p. The polygon that visits the points of S in the sorted order is a simple polygon (Fig. 2.3). Now, assuming the points are sorted clockwise, around p, in order to obtain the convex hull of S we just have to scan through the vertices of the polygon, and remove the points where the polygon makes a right turn. Note that when removing a point from the polygon, the previous vertex has to be tested again for a right turn. This occurs at most n times as any point from the set can only be removed once. The algorithm hence requires O(n log n) time in order to sort the points around p, and then an additional O(n) time in order to compute the convex hull from the simple polygon. Hence the total running time of the Graham scan algorithm is O(n log n).

Jarvis March Algorithm

Jarvis March, also known as gift wrapping is an output sensitive convex hull algorithm. In two dimensions, its running time complexity for an input set S of n points is O(nh), where h is the number of vertices on the convex hull. As a consequence, its worst-case time is O(n 2 ) when all the points are in a convex position.

Jarvis March starts by computing a point p 0 ∈ S that is on the convex hull of S, such as the left-most point of S for instance. We then, greedily compute one by one the vertices p i of the convex hull. Knowing p i-1 , and in order to compute p i , the next point of the convex hull, we simply look for the point p i such that all points of S are located to the right of the line p i-1 p i . We then repeat this process until we reach back to p 0 . As computing each p i takes O(n) time, the total running time of the algorithm is equal to O(nh).

Chan's Algorithm

Chan's algorithm [START_REF] Timothy | Optimal output-sensitive convex hull algorithms in two and three dimensions[END_REF] is an output sensitive algorithm that runs in O(n log h) time in two or three dimensions. It is not the only, nor the first, algorithm that obtains this complexity [START_REF] David | The ultimate planar convex hull algorithm?[END_REF], but it is arguably the simplest. Chan's algorithm is a combination of the Graham scan algorithm 2.1.2, and Jarvis march 2.1.3.

In a first time we describe the algorithm assuming that h, the number of vertices of the convex hull of S, is known. We will then explain how to adapt the algorithm when h is unknown.

First, we start by arbitrarily separating S into at most 1 + n h subsets S i of at most h points. Then, we compute the convex hull of each S i using Graham scan. This takes O(h log h) time for each S i , as there are at most 1 + n h , computing all those convex hulls takes O(n log h) time.

Second, we use a method similar to Jarvis March to compute the convex hull of S. Hence, knowing p i a vertex of the convex hull of S, we are looking

p 0 p j 1 p j 2 p j 3 Figure 2.
4 Jarvis march step. We are looking for the point p j such that all the other vertices of the convex hull are located to the right of p i p j . Once we computed such a p j i for each subset S i , we know that p j is one of the j i , and hence only to look among those.

for p i+1 ∈ S such that ∀p j ∈ S, j ̸ = i p j is located to the right of the line p i p i+1 .

As p i+1 is necessarily in the convex hull of a subset S i we only have to consider the points that are vertices of those convex hulls. For a given subset S i , that has at most h points, the points p k ∈ S i such that all p j ∈ S i are located to the right of the line p i p k can be computed in O(log h) using a binary search on the convex hull of S i (Fig. 2.5). Once we computed the candidate point for each subset, the usual Jarvis march step can be used on the O( n h ) candidate points to find p i+1 (Fig. 2.4). Hence, overall it takes O( n h log h) time to compute p i+1 . As we repeat this process exactly h time in order to compute the convex hull of S, the total running time of the algorithm is O(n log h) when h is known.

We now, explain how we can use the previously described algorithm, that assumes that h is known, in order to compute the convex hull of S in O(n log h) without knowing h. The idea, is to guess a value for h, and square our guess until we finally reached a value bigger than h. First, we chose a small value,

p k p k/2 p 0 p i p k p 0 p k/2 p i p k p i p k/2 p 0 a) b) c) Figure 2.
p j = p k/2 .
h 1 = 2 for instance. We then run the previously described algorithm until we reach the 3 rd step of the algorithm. At this point, the Jarvis march steps either successfully came back to the starting point, which means we found the convex hull, or we realize that h is actually bigger than h 1 = 3. In this second situation, we stop computation, and start all over again with h 2 = h 2 1 . We repeat this process until we guess a value h k larger than h, which results in us computing the convex hull. For each guess we made, the running time is equal to O(n log h i ), which result in a total running time of log log h k=0

O(n log 2 2 k ) = O(n log h).

Digital Geometry

Digital geometry is the field of mathematics that studies the geometry of points with integer coordinates, also known as lattice points [START_REF] Klette | Digital geometry: Geometric methods for digital picture analysis[END_REF]. In this section we present some common tools and notions of digital geometry that will be used throughout this dissertation.

Transformation of Z 2

In most cases, in computational geometry, the points are assumed to be in general position. This is clearly not the case in digital geometry where multiple points often have the same x or y coordinate. Not all affine transformations are bijective from Z 2 to Z 2 , but those who do are interesting in the context of digital geometry. We say that those transformations preserve the lattice grid. A transformation matrix that preserves the lattice grid must have integer coefficients, and their determinant must be equal to ±1. These transformations are called unimodular affine transformations SL 2 (Z) [START_REF] Bárány | On the number of convex lattice polygons[END_REF][START_REF] Haase | Lecture notes on lattice polytopes[END_REF] when the determinant is equal to one.

One of those transformations is called shearing or transvection [START_REF] Stephen | Generation of special linear groups by transvections[END_REF]. Horizontal shearings are the linear transformations whose transformations matrices are of the form

   1 k 0 1    , k ∈ Z * .
Similarly, we call vertical shearing a linear transformation whose transformation matrix is

   1 0 k 1    , k ∈ Z * . It is clear
that both horizontal and vertical shearing define a bijection from Z 2 to Z 2 (Fig. 2

.6).

It is interesting to note that shearings generate SL 2 (Z) [START_REF] Artin | Geometric Algebra[END_REF]. For a given linear transformation L ∈ SL 2 (Z), as the determinant of the matrix representing L is equal to 1, the composition of shearings equivalent to L can be obtained simply by using the extended Euclidean algorithm. Lemma 1 states that for any line ℓ going through any two lattice points, there is a linear transformation Proof. Let ℓ be a Diophantine line. Let p(x p , y p ) and q(x p + a, y p + b) be two consecutive lattice points on ℓ, that is the line segment pq only contains two lattice points, namely p and q. This implies that we have GCD(a, b) = 1. Let x and y be the Bézout coefficients of a and b, those are the two integers x and y such that ax + by = 1. We now consider the matrix

M =    x y -b a    . By construction det(M ) = ax + by = 1. Hence M defines a linear map L such that Im L (p) = M p =    xx p -yy p -bx p + ay p    Im L (q) =    xx p + ax -yy p + by -bx p -ab + ay p + ab    =    xx p -yy p + 1 -bx p + ay p    = Im L (p)+    1 0    Hence Im L (d) is an horizontal line and Im L (Z 2 ) = Z 2 .
We say that two Diophantine lines ℓ 1 : a 1 x+b 1 y = c 1 and ℓ 2 :

a 2 x+b 2 y = c 2 are consecutive if a 1 = a 2 , b 1 = b 2 and |c 1 -c 2 | = 1.
Lemma 2 states that no lattice point is located in between ℓ 1 and ℓ 2 , and a corollary of this lemma is that for any co-primes a and b, all points from Z 2 are located on a Diophantine line of equation ax + by = k, k ∈ Z. Proof. Consider a lattice point p(x p , y p ), as a, b, x p , and y p are integers so is ax p + by p , which hence cannot be in the interval (c, c + 1)

Digital Connectivity

Connectivity, does not have the same meaning in digital geometry as in classic Euclidean geometry. However, two simple notions of connectivity are used in digital geometry in the plane. We say that two lattice points p 1 and

p 2 are 8-connected (resp. 4-connected ) if their Chebyshev distance L ∞ (resp.
Euclidean distance) is one. We say that a set S of lattice points is 8-connected (resp. 4-connected ) if for all pair of points p 1 and p 2 in S there is a chain of 8-connected (resp. 4-connected ) points in S going from p 1 to p 2 .

Convex Not convex

Figure 2.7 Digital convexity. The first set is digital convex, while the second set is not because of the red lattice points that are inside the convex hull of the set but not in the set itself.

Digital Convexity

Although the subsets of Z d are not convex in the usual meaning of the term, a simple notion of convexity is induced by the convexity of R d [START_REF] Ronse | A Bibliography on Digital and Computational Convexity (1961-1988)[END_REF]. A set of lattice points S ⊂ Z d is digital convex if conv(S) ∩ Z d = S, where conv(S) denotes the convex hull of S in R d (Fig. 2.7). In other words, S is digital convex if it is the intersection of a convex subset of R d with the lattice Z d . Digital convex lattice sets are then directly related to the lattice polytopes investigated in geometry of numbers since the works of Minkowski [START_REF] Minkowski | Geometrie der Zahlen[END_REF]. Digital convexity is preserved by homeomorphisms of Z d .

Let us remark that a digital convex set S is not necessarily connected while the convex sets of R d are arc-connected or simply connected. In Z 2 and Z 3 , the lack of connectivity has, throughout the years and today still, motivated the introduction of some alternative definitions of digital convexity [START_REF] Chassery | Discrete convexity: Definition, parametrization, and compatibility with continuous convexity[END_REF][START_REF] Baran | ON THE COMPU-TATION OF THE DIGITAL CONVEX HULL AND CIRCULAR HULL OF A DIGITAL REGION[END_REF][START_REF] Kim | Convex Digital Solids[END_REF][START_REF] Kim | Digital Straight Lines and Convexity of Digital Regions[END_REF][START_REF] Kishimoto | Characterizing Digital Convexity and Straightness in Terms of Length and Total Absolute Curvature[END_REF][START_REF] Lachaud | An alternative definition of digital convexity[END_REF]] that we will not consider here. Despite this lack of connectivity, different bounds have been established between the different characteristics of a digital convex set S. We denote n be the number of lattice points in any lattice set S, h the number of edges of conv(S), and r the diameter (largest Euclidean distance between two points) of S. It is clear that for a given number of edges h, the number of points n and the diameter r are not bounded (consider for instance very long and skinny triangles). Similarly, for a given number of points n, the diameter r is not bounded (consider the pair of points (0, 0) and (1, r)). However the number of vertices (or edges) h is bounded by O(n 1/3 ) [START_REF] Colbourn | A note on bounds on the minimum area of convex lattice polygons[END_REF]. At last, given the diameter r, the number of points n is clearly at most O(r 2 ) and h is at most O(r 2/3 ) [START_REF] Žunić | Notes on Optimal Convex Lattice Polygons[END_REF]. Some other measures, specific to digital geometry, also exists. For instance, the lattice diameter ℓ(S) of a digital convex set S is the measure of the longest string of co-aligned lattice points in S. The width also has its digital analogous, and the lattice width is defined as follow in digital geometry. We first define ω u (S) the width of S along a direction u ̸ = (0, 0) as:

ω u (S) = max x,y∈S (u(x -y))
More intuitively, the width of S along a direction u is equal to -1 plus the number of consecutive parallel line supported by lattice points and of direction orthogonal to u that are required to cover S (Fig. 2.8). The lattice width of S is:

ω(S) = min u∈Z 2 \(0,0) ω u (S)
It is worth noting that both lattice diameter and lattice width are invariant under the group of unimodular affine transformations, and that ω(S) ≤

ω u (S) = 7 u v ω v (S) = 3 ω(S) = 2

Range Searching

In this section we present existing works on range searching. Section 2.3.1 describes a triangle range counting algorithm that we will make use of in Section 4.1, whereas Section 2.3 proposes a quick overview of existing work on simplex range searching.

Triangular Range Counting

In this section, we present a preprocessing method in O(n 2 ) time and space, that for a set of points S allows to retrieve the number of points inside any triangle in S in constant time. Note that the triangles requested must have their vertices in S, which is why the query time is better than the known lower bound on generic polytope range searching [START_REF] Chazelle | Lower Bounds on the Complexity of Polytope Range Searching[END_REF]. The structure introduced in -For all p i in order, we compute below(p i r) in the following manner:

If p i lies to the left of p i-1 then below(p i r) = below(p i-1 r) + below(p i p i-1 ) + 1.
Else p i lies to the right of

p i-1 then below(p i r) = below(p i-1 r) -below(p i-1 p i ).
As p i-1 and p i are consecutive in the clockwise ordering around p, we know that the triangle p i-1 p i r does not contain any other point from S,

r p i-1 p i r p i-1 p i Figure 2
.10 Range counting preprocessing. In both cases the dark red cones contain no points from S. On the left: The points below p i r are the points below p i p i-1 and the points below p i-1 r. One the right: The points below p i r are the points below p i-1 r minus the points below p i-1 p i . and hence the method we just describe correctly computes the number of points below the edges whose right-most point is r (Fig.

Simplex Range Searching

In this section, we propose an overview of the history of data structures used to solve simplex range searching problems. We will first look at data structures that allow a logarithmic query time, and then will consider the data structures that only use linear space. More often than not, the data structures used in order to solve simplex range searching problem are partition trees. A partition tree T is a data structure that partitions a point set S into subsets. Each point of S is stored in exactly one leaf of T , and each leaf contains at most a constant number of points. Each node N of T stores a polyhedron P (N ) of size O(1).

All points stored in the leaves underneath N are enclosed by P (N ), and no other point in S is enclose by P (N ). In addition, each node N stores the number of points enclosed by P (N ).

Given a set H of n hyperplanes H 1 , H 2 , ..., H n , an ϵ-cutting C is a division of R d into simplices C 0 , C 1 , ...C k such
that the C i are mutually disjoint and the interior of any C i is intersected by at most ϵn hyperplanes H i .

Linear size data structures

The majority of linear size data structures used to solve simplex range searching problems are based on partition trees. Given a set S of n points in R d , a partition tree partitions the space into a small number of regions, each containing approximately the same number of points, then recursively partition each region in a similar way. Partition trees where first introduced in the plane in [START_REF] Willard | Polygon retrieval[END_REF] and relied on the following ham-sandwich theorem [START_REF] Edelsbrunner | Algorithms in combinatorial geometry[END_REF].

Theorem 3. For any two sets S 1 and S 2 of n 1 and n 2 points in the plane, there is a halfplane h such that

S 1 ∩ h = n 1 2 and S 2 ∩ h = n 2 2 .
Using the ham-sandwich theorem, we find two hyperplanes h 1 and h 2 such that each one of the four quadrants induced by h 1 and h 2 contains n 4 points. The root of the partition tree stores h 1 , h 2 and n. Then, for each quadrant, we recursively construct a subtree in the same manner. The total size of the data structure is proportional to log 4 n k=0 4 k and is hence linear, and can be computed in O(n log n) time. Using this partition tree, a halfplane h range counting query can be answered as follows. For each of the four quadrants Q i attached to the root of the tree we do the following. If the line l h induced by the halfplane h intersects the quadrant, then we visit the children of A data structure that reaches an optimal worst case query time of

Q i . If Q i ∩ h = ∅, then we do nothing. Finally, if Q i ⊂ h,
O(n 1-1/d ),
where d is the dimension, for linear structure [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF] in the arithmetic model was presented in [START_REF] Matoušek | Range searching with efficient hierarchical cuttings[END_REF]. This data structure is based on the following partition tree theorem from [START_REF] Matoušek | Efficient partition trees[END_REF] Theorem 4. For any set S of n points in R d , and any r such that 1 < r < n 2 there is a family of pairs set/simplex Γ = (S 1 , P 1 ), ..., (S i , P i ), ..., (S k , P k ) such that for each i, S i ⊂ S is located inside P i , for all i ̸ = j S i ∩ S j = ∅, and

n r ≤ |S i | ̸ = 2n
r , and there is a constant c such that any hyperplane crosses at most cr 1-1 d P i .

A partition tree can be built by computing the partition described in the previous theorem 4. For each simplex P i , we recursively construct a subtree in the same manner. The total size of the data structure is linear, and can be computed in O(n log n) time. Using this partition tree, a halfspace h range counting query can be answered as follows. For each simplex P i attached to the root of the tree we do the following. If the hyperplane l h that is the boundary of the halfplane h intersects P i , then we visit the children of

P i . If P i ∩ h = ∅,
then we do nothing. Finally, if P i ⊂ h, we add all the points in P i to the global count. As l h crosses at most cr 1-

1 d simplex, the query time is O(n 1-1 d +log r c ), by choosing r = n ϵ , this results to a query time of O(n 1-1 d log O(1) n).
Finally, a data structure with O(n 1-1/d log n) query time, O(n) space, and O(n log n) preprocessing was presented by Chan [START_REF] Timothy | Optimal partition trees[END_REF], and is based on the two following results.

Logarithmic query time data structures

In order to solve simplex range searching, we will first consider the simpler halfspace range counting problem, in which we only want to retrieve the number points in a given halfspace. Using duality, and the following property of duality that states that a point p is above a hyperplane h if and only if the dual point h * of h is above the dual hyperplane p * of p, we can see that the halfspace range counting problem is actually equivalent to counting the number of halfplanes that are located above a query point.

To do so, we make use of the following cutting theorem presented in [START_REF] Chazelle | Cutting hyperplanes for divide-and-conquer[END_REF]: By choosing r = n log 2 n , and constructing the cuttings from theorem 7 Chazelle [START_REF] Chazelle | Cutting hyperplanes for divide-and-conquer[END_REF] achieved a data structures of size O(

Theorem 7.
n d log d-1 n
) that can answer a halfspace range query in O(log n) time in the following manner, using the dual. For each simplex S of C i , we store the simplices of C i+1 that are located in C i , and the number of hyperplanes located above S. For the last layer of the cutting, C k , we also have to store the list of hyperplanes that intersects each simplex.

In order to answer a query, we simply go through the tree in order to find the simplex S ∈ C k that contains our query point p. We then simply return the number of hyperplanes above S plus the number of hyperplanes intersecting S above p.

Chapter Three Digital Convex Set Recognition

In this chapter, we develop algorithms to recognize digital convex sets.

In Section 3.1, we present a near linear time algorithm to test digital convexity. The algorithm is based on the quickhull algorithm presented in Section 2.1.1.

In Section 3.2, we present a near linear time algorithm that given any digital convex set S finds a polygon P with vertices in R 2 with minimum number of edges such that P ∩ Z 2 = S.

Testing Digital Convexity

In this section, we consider the question of determining whether a given finite lattice set S is digital convex. Previous related works considered structured data in which S is assumed to be connected [START_REF] Brlek | Lyndon + Christoffel = digitally convex[END_REF][START_REF] Debled-Rennesson | Detection of the discrete convexity of polyominoes[END_REF]. Notice also that if the set is ordered, its convex hull can be computed in linear time. In this section we consider the input to be an unstructured lattice sets.

Problem Test Convexity

Input: A set S ⊂ Z 2 of n lattice points given by their coordinates.

Output: Determine whether S is digital convex or not.

Herein we present an algorithm that solves the Test Convexity problem in O(n + h log r) time, where n = |S|, h is the number of edges of conv(S), and r is the diameter of S. The algorithm makes use of the quickhull algorithm and relies on the following Theorem 8 that states that the quickhull algorithm is able to find the convex hull of any digital convex set S in linear time and space relative to the cardinality of S. Proof. During the quickhull algorithm, we discard from S the points located inside the partial hull, and add some of them as vertices of the partial hull.

Theorem 8 is a consequence of the following two propositions, which we prove next: (i) At least half of the remaining points are discarded at each iteration.

(ii) At each step, the running time is linear in the number of points remaining in S. We start by proving proposition (i).

We consider one step of the quickhull algorithm as described in 2.1.1. Let ab be the edge of this step. When the point a was added to the hull, it was the farthest point in a given direction. Hence, there is no point beyond the line orthogonal to this direction going through a. We call this line ℓ a (Fig. For proving (ii), the computation of the farthest point from the line ab among the remaining points of S in the triangle △abc takes linear time. For all points in the triangle we test if they are in the interior of either the triangles △ade or △dbf (or △d ′ bf in the second case). We allocate them to their containing triangle or discard them. The operation takes constant time per point. In the second case, where we have two extreme points d and d ′ , these two points are also computed in linear time; This proves (ii). Consequently, the number of operations at each step is proportional to the number of remaining points, which is at most half the number of points of the previous step. Therefore the total number of operations is bounded by n

∞ i=0 ( 1
2 ) i = 2n, hence the quickhull algorithm runs in linear time for digital convex sets.

By running quickhull on any given set S, and stopping the computation if any step of the algorithm discards less than half of the remaining points, we ensure both that the running time is linear, and that quickhull finishes for any set S that is digital convex. However, if the computation finishes for S, we still need to test its digital convexity. To do so, we use the computed convex hull.

If the number of convex hull vertices h is larger than (8π 2 n) 1/3 , then S is not digital convex (see [2,[START_REF] Rabinowitz | O(n 3 ) Bounds for the Area of a Convex Lattice n-gon[END_REF], the upper bound h ≤ (8π 2 A) 1/3 is given according to the area A of the convex hull of a digital convex set S, but if S is not a set of colinear points, Pick's formula gives A < n which gives h ≤ (8π 2 n) 1/3 for convex lattice sets where n = |S|). We can assume that h is lower than [START_REF] Pick | Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines für Böhmen "Lotos[END_REF]. The set Proof. As we run the quickhull algorithm, but stop if less than half of the remaining points have been removed, the running time of the quickhull part is bounded by the series n

(8π 2 n) 1/3 . Then we compute | conv(S) ∩ Z 2 | using Pick's formula
S is digital convex if | conv(S) ∩ Z 2 | = |S|.
∞ i=0 ( 1
2 ) i = 2n, and is hence linear. If the quickhull algorithm has been stopped, then the set S is not digital convex. Otherwise, if the number of convex hull vertices h is larger than (8π 2 n) 1/3 , then we know that the set S is not digital convex. We now consider the remaining case where h ≤ (8π

Optimal Digital Convex Polygon

In this section, as in Section 3.1, we consider the fundamental question of pattern recognition that is the recognition of digital convex polygons. In this version of the problem, we are given a set S ⊂ Z 2 of n points and an integer q, the goal is to determine the existence of a convex polygon P with q edges such that P ∩ Z 2 = S. Notice that in this problem the vertices of P are not necessarily lattice points. We provide an algorithm to solve the planar recognition of digital convex polygons in linear time. The algorithm is more general and actually solves the following minimization problem:

Problem 1. Edge Minimization

Input: Set S ⊂ Z 2 of n lattice points given by their coordinates.

Output: A convex polygon P with minimum number q of edges verifying

P ∩ Z 2 = S.
We note that the problem Edge minimization can be rephrased as the following polygonal separation problem with the set IN = S and its complement OUT = Z 2 \ S (Fig. 3.3).

Problem 2. Polygonal Separation

Input: A set IN ⊂ Z 2 of inliers and a set OUT ⊂ Z 2 of outliers. In the third step we separate OUT ′ from S using the smallest number of edges possible. To do so we could use the polygonal separability algorithm from [START_REF] Edelsbrunner | Minimum polygonal separation[END_REF], but that would lead to a running time of O(n log r + n log n) = O(n log r). Instead, we provide an algorithm that takes benefit of the lattice structure to achieve a running time of O(h log r) for this step. After the convex hull computation and digital convexity tests of the first step, the whole algorithm takes O(n+h log r) time. However, if the convex hull of S is provided the algorithm runs in O(h log r) time.

As the first step, i.e. testing the digital convexity, is already addressed in the previous Section 3.1, we present the second and third steps of the algorithm in the two following sections.

Outliers Reduction

In this section we assume that the set S is digital convex and show how to reduce the set of outliers OUT = Z 2 \ S to a finite set of O(n) points. To do this, we use the notion of jewels introduced in [START_REF] Coeurjolly | An elementary algorithm for digital arc segmentation[END_REF][START_REF] Gérard | Recognition of Digital Polyhedra with a Fixed Number of Faces[END_REF] for testing digital circularity and recognizing digital polyhedra. We say that a point p ∈ Z 2 \ S is a b Figure 3.4 Jewel's hull. In black, the set S, its convex hull is in dark red. The point a is not a jewel because of the red point, any convex polygon that includes both S and a also includes the red point. The point b is a jewel because its union S ∩ {b} with S is still convex. In other words, the convex hull of the union S ∩ {b} does not contain any other lattice points. a jewel of S if conv(S ∪ p) ∩ Z 2 = S ∪ p (Fig. 3.4). The set of all the jewels of S is denoted Jewel(S) and it has the property that a convex set separates S from Z 2 \ S if and only if it separates separates S from Jewel(S) [START_REF] Gérard | Recognition of Digital Polyhedra with a Fixed Number of Faces[END_REF]. Hence, the infinite set of the outliers of our separability can be reduced from OUT = Z 2 \S to OUT ′ = Jewel(S).

It has been proven that the number of jewels is infinite if and only if S is the intersection of a line segment and Z 2 [START_REF] Gérard | Recognition of Digital Polyhedra with a Fixed Number of Faces[END_REF]. In this case it is clear that the set S forms a digital triangle. A simple way to establish bounds on the number of jewels has been discovered by French high school students during the national contest TFJM2017 https://tfjm.org/editions-precedentes/edition-2017. They presented the following structure of the set of jewels: the jewels of the lattice set S are the lattice points located on the edges of a polygon J surrounding the convex hull of S. This surrounding polygon J ⊃ conv(S) is the arithmetic dilation of conv(S) obtained by moving the support lines of the edges of the conv(S) to the next Diophantine lines towards the exterior (Fig. 3.5). We define J as the jewel hull of S (Fig. 3.5) and define it more formally as follows.

Figure 3.5 Jewels. In black, the set S, its convex hull is in dark red. The halfplanes H ′ i are delimited by the dashed lines, and form the jewel hull that surrounds the convex hull of S. The jewel hull has three properties: its edges are parallel to the ones of the convex hull of S, there are no point between the convex hull and the jewel hull and all the jewels (drawn in red) are on its boundary.

Given S, let E = {e 1 , e 2 , ...e h } be the edges of conv(S). For each i from 1 to h, let HP i : a i x + b i y + c i ≤ 0 (a i and b i co-prime integers) be the closed supporting halfplane associated with the edge e i such that S ⊂ HP i . Notice that conv(S) = i HP i . Consider the open halfplanes HP ′ i : a i x + b i y + c i < 1. Notice that there is no integer point in HP ′ i \ HP i . The jewel hull of S is the closure of the intersection of the half-planes HP ′ i (Fig. 3.5). The jewel hull J of S has three main properties. (i) By construction, its edges are parallel to the edges of conv(S). (ii) It is clear that there is no integer point in the surface located between conv(S) and the jewel hull J. Finally, (iii) A corollary of the next lemma is that the jewels of S are a subset of J, more precisely jewel(S) = (J ∩ Z 2 ) \ S. Proof. Up to a lattice preserving affine isomorphism, we can assume p 1 = (0, 0) and p 2 = (0, u) while the images of the two lines are x = -1 and x = 1.

We assume p 3 is located on the right of p 1 p 2 (the other case is identical by symmetry). Hence, there exists three integers u, v, w with u, v > 0 such that p 1 = (0, 0), p 2 = (0, u), and p 3 = (v, w) and we want to prove that the triangle

u(v -1) ≥ v -1.
The area of the jewel hull of S is finite unless all the points of S are colinear.

However, in this case there exists a triangle with vertices in R 2 that separates that not all h halfplanes appear on the boundary of the jewel hull, which is the dual of the fact that some points may be in the interior of the convex hull.

S from Z 2 \ S.

Jewel Separation

The jewel separation is the final step to solve the Edge minimization prob- The jewels are determined in counterclockwise order according to their order of appearance in the jewel hull. Their cyclic index i goes from 0 to |jewel(S)| -1. Furthermore, any pair of indices i, j with i < j defines two intervals of indices, the interval I i→j containing the indices of the successors of i until j and the interval I j→i containing the indices of the successors of j until i. We introduce now the precise meaning of separation. We say that a real line ℓ separates some jewels from S if S is located entirely on one side of ℓ while the jewels are located strictly on the other side. The fact that all jewels are located on the boundary of a convex polygon leads to the following simple lemma:

Lemma 11. If ℓ is a line separating the jewels of indices i and j from S, then the line ℓ separates S from either the jewels with indices in I i→j or the jewels with indices in I j→i .

A naive approach to solve the polygonal separation problem of the sorted set of jewels from S is the following: Choose a starting jewel of index i 0 . Search for the index j 0 such that the jewels with indices in the interval I i 0 →j 0 can be separated from S and |I i 0 →j 0 | is maximized. The method used to compute j 0 in constant time using our representation of the jewels will be detailed later. We then define i 1 as the successor of j 0 and repeat the process: search for j 1 such that I i 1 →j 1 can be separated from S and the number of jewels in the interval is maximized. We repeat until we find an interval I i k →j k which contains the predecessor of i 0 . The number of lines of the solution is the number k + 1 of intervals considered. This algorithm is illustrated Fig. 3.6. We call this greedy algorithm the turn routine since the strategy is to turn around the set S from a starting jewel p i 0 .

The difficulty of this approach is that different choices of the starting point p i 0 may lead to different numbers of separating lines (actually, they may differ by at most 1 line). The strategy to find the minimum number of separating lines is to test several starting jewels. Dynamic programming approaches might Algorithm 1 turn(conv(S), Jewel(S),i 0 )

Require: the convex hull conv(S), the ordered list of its jewels Jewel(S), and a starting jewel p of index i 0 .

Ensure: A separating polygon with S inside and Jewel(S) outside.

1: Initialize i 0 as the index of the starting jewel, k = 0 and I i -1 →j -1 as an empty interval

2: while predecessor(i 0 ) ̸ ∈ I i k-1 →j k-1 do 3:
Compute j k such that the jewels with indices in the interval I i k →j k can be separated from S and |I i k →j k | is maximized.

4:

i k+1 ← successor(j k )

5:

k = k + 1 6:
return The polygon obtained from the separating lines be used to find an optimal solution as in [START_REF] Feschet | On the min DSS problem of closed discrete curves[END_REF], but in the framework of our

Edge minimization problem in the lattice, we are able to obtain a major simplification.

The strategy to simplify the problem is the following. There are two families of jewels: the ones which chosen as starting jewel in the turn routine provide a minimal number of lines, their indices are denoted I OPT , and the ones that provide a non optimal number of lines. Notice that if the index i 0 is in I OPT , then all the indices i k computed during the turn routine are also in I OPT since it can be easily seen that they provide also optimal solutions.

In the general case of polygonal separability, a large set of starting points has to be investigated until finding one leading to an optimal solution but in the framework of the separation of IN = S and OUT ′ = Jewel(S), we can provide We start from a chosen starting jewel p i 0 and search for its last successor p j 0 that can be separated from S simultaneously with p i 0 by a single line. We then take the successor of p j 0 as new starting jewel p i 1 and search for the last successor p j 1 of p i 1 that can be separated with p i 1 ... We repeat the process until reaching the predecessor of p i 0 .

a subset of at most 4 jewels containing at least one in I OPT . It means that testing these four jewels as starting points of the turn routine is enough to find the optimal solution. The properties of the set I OPT are presented in the next two lemmas.

The first lemma states that there is no line that simultaneously separates two jewels of a line ℓ i and two jewels of ℓ i+1 .

Lemma 12. Let ℓ 1 and ℓ 2 be two jewel lines. (i) If ℓ 1 ∩ ℓ 2 / ∈ Z 2 then there is no line that separates two jewels of ℓ 1 and two jewels of

ℓ 2 . (ii) If ℓ 1 ∩ ℓ 2 ∈ Z 2
then there is no line that separates three jewels of ℓ 1 and three jewels of ℓ 2 .

Proof. (i) Let order the jewels on ℓ 1 : J 1 = {p 1_1 , p 1_2 , ...} according to their distance to ℓ 2 , and order the jewels on ℓ 2 : J 2 = {p 2_1 , p 2_2 , ...} according to their distance to ℓ 1 . Assume that there is a line l such that l separates two jewels of ℓ 1 and two jewels of ℓ 2 from conv(S). Then l separates p 1_1 , p 1_2 , p 2_1 and p 2_2 from conv(S). Hence the triangle △p 1_1 p 1_2 p 2_2 is located inside the jewel hull and outside of conv(S) (Fig. 3 are two consecutive lattice points of ℓ 1 , this means that there is a lattice point strictly inside the jewel hull and outside conv(S), which is impossible. Hence l does not exist. The proof of (ii) is the same, we just have to consider

p 1_0 = p 2_0 = ℓ 1 ∩ ℓ 2 .
We complete Lemma 12 with a lemma about the separation of jewels which are not in consecutive lines ℓ i and ℓ i+1 . Lemma 13. If ℓ i and ℓ j are two non consecutive jewels lines: j ≥ i + 2, then there is no line that separates any jewel that belongs only to ℓ i and any jewel that belongs only to ℓ j .

Proof. Consider ℓ i+1 and its associated edge on conv(S): e i+1 . By construction, there is no lattice point between ℓ i+1 and e i+1 (Fig. 3.7.b ). Assume that there is a line l that separates jewels of both ℓ i and ℓ j As all the jewels belonging only to ℓ i and all the jewels belonging only to ℓ j are located on the same side s j of e i+1 as S, l has to be in s j to separate jewels of ℓ i , then has to leave s j in order to not intersect conv(S), and finally has to go back in s j to separate jewels of ℓ i+1 . Hence l intersects e i+1 twice which is impossible.

We now explain how to use Lemmas 12 and 13 to determine at most four jewels such that at least one of them leads to an optimal solution with the turn routine. In other words, we provide four indices with the guarantee that at least one of them is in I OPT . For convenience, the successor of the index s is now simply denoted s + 1 and so on with the successor of the successor denoted s + 2. In the same manner, we also use s -1, s -2, ... to denote the predecessors of s. When looking for a jewel in I OPT , several cases might occur:

1. The jewel hull J has an edge e i which does not contain any integer point. If we denote s the index of the first jewel after this edge, then I OPT contains s. It is a corollary of Lemma 13. Considering an optimal solution, the vertex of index s cannot be included in the interval I ir→jr containing s -1 because the interval would contain jewels of the lines ℓ i-1 and ℓ i+1 which is excluded by Lemma 13. Hence the index s is a starting index namely an index of the form i r of the considered optimal solution. As the indices i r of the intervals I ir→jr computed from an optimal starting index i 0 are also optimal, s is included in I OPT .

2. The jewel hull J has an edge e i with only one jewel s, hence I OPT contains either s or s + 1. Considering an optimal solution, it follows from Lemma 13 that s -1 and s + 1 cannot be in an interval of the form I ir→jr since they are on distant lines ℓ i-1 and ℓ i+1 . Hence, there exist either an index i r equal to s or to s + 1. It proves that one of these two indices s or s + 1 is in I OPT .

3. The jewel hull has an edge with only two jewels. Their indices are s and s + 1. Considering an optimal solution, according to Lemma 13 the indices s -1 and s + 2 cannot be in the same interval I ir→jr because they belong to the distant lines ℓ i-1 and ℓ i+1 . Hence, there is at least a beginning of interval in s, s + 1 or s + 2. One of these three indices s, s + 1, s + 2 is in I OPT 4. The edges of the jewel hull all contain at least three jewels. We choose any edge e i and denote s, s + 1, s + 2 the indices of its three firsts jewels.

According to Lemma 12 the indices s + 2 and s -2 cannot be in the same interval I ir→jr . Hence, there is at least a beginning of interval in s -1, s, s + 1 or s + 2. One of these four indices s -1, s, s + 1, s + 2 is in I OPT .

In any case, we can determine a set of at most four starting jewels with the guarantee that the turn algorithm provides an optimal solution for at least one of them. We now explain how, in the turn algorithm 1, for a given jewel p i we compute its last successor p j that can be separated alongside him with a single line. Let p i be on the jewel line ℓ i , and let v i be the end vertex of the edge of the convex hull parallel to ℓ i . Consider the line p i v i . S is located on one side of p i v i , all the jewels that are located strictly on the other side can be separated alongside p i (Fig. 3.6). It is clear that all jewels located on ℓ i can be separated with p i , and using Lemma 13 we know that the jewels located on ℓ i+2 cannot. Hence, all we have to do is determine the last jewel of ℓ i+1 that is located on the correct side of p i v i . This is easily done by computing the intersection point q of p i v i and ℓ i+1 and expressing q as d i+1 + λ(-b i+1 , a i+1 ) (We remind that the jewels on ℓ i+1 are expressed as:

k d i + k(-b i , a i )).
From there a separating line can be computed by rotating slightly p i v i around any points in between p i and v i .

The time complexity of the turn algorithm 1 is hence O(h) = O(n 1/3 ).

This follows from the fact that h is an upper bound to the number of edges of the solution of the Edge minimization problem and h = O(n 1/3 ). Starting from any jewel, the algorithm computes a polygon that has at most one edge more than the optimal solution and each edge is computed in O(1) time.

As the jewel hull is computed in O(h log r) time, the set of O(1) starting jewels can be computed in constant time, and the turn algorithm 1 runs in O(h) time. Hence the edge minimization algorithm, once provided with the convex hull of S, runs in O(h log r) time.

Algorithm 2 edge minimization(S)

Require: S a set of points.

Ensure: A minimal separating polygon if S is digital convex. Compute the minimal separating polygon using the given starting jewel using algorithm 1 6: return The minimal separating polygon ones with the maximum number of points. However the algorithms described can easily be adapted to instead maximize the area, or even the convex hull's perimeter.

Digital Potato Peeling

In this section, we present an algorithm to solve the digital potato-peeling problem in O(n 3 + n 2 log r) time, where n is the number of input points and r is the diameter of the point set. We define the digital potato-peeling problem as follows:

Problem 3. Digital potato-peeling

Input: A set S ⊂ Z 2 of n lattice points given by their coordinates.

Output:

The largest set K ⊆ S that is digital convex (i.e., conv(K)∩Z 2 = K), where largest refers to |K|.

We note that a digital convex set K can be described by its convex hull conv(K), and that the vertices of conv(K) are lattice points. In order to solve the digital potato-peeling problem, instead of explicitly building K, our algorithm constructs conv(K). We also note that any convex polygon P with k vertices can be triangulated using k -2 triangles that share a common vertex, the bottom-most vertex ρ of P for instance. We name such a triangulation a fan triangulation (Fig. 4.1). In order to solve problem 3 we first consider the following rooted variation of the digital potato-peeling problem, where the point ρ has been given as part of the input. programming algorithm which is based on the same construction. In order to avoid confusion with the geometric terms, we will refer to the graph vertices as nodes, and the graph edges as arcs (Fig. 4.2).

G is built in the following way:

-Each node N i of G represents a valid rooted triangle. Analogously, all valid rooted triangles are represented by a node in G -There is an arc A ij from the node N i towards the node N j if and only if:

(i) The union of the triangle △ i associated to N i and the the triangle △ j associated to N j is a convex quadrilateral q ij , and (ii) △ i is the first triangle in the clockwise rooted fan triangulation of

q ij .
-The weight of an arc A ij is equal to the number of lattice points in △ j not in △ i , that is the number of lattice points in △ j minus the number of lattice points on the edge shared by △ i and △ j .

-A starting node A ∅ is added to G -Initialization arcs A ∅,i are added from the starting node towards each other node N i . Their weight is equal to the number of lattice points in

△ i
Solving the rooted digital potato-peeling problem is equivalent to finding the longest path in G. This property is a corollary of the following lemma. Example of a DAG built to solve the rooted peeling problem for 6 valid triangles. For two triangles to be connected by an arc in the graph, they need to have a common edge that starts from ρ, and their union must be a convex polygon. The weight of each arc is equal to the number of lattice points inside the right-most triangle that are not located on the common edge between the two triangles.

Lemma 14. (i) Every path in G represents a digital convex set. The length of the path is equal to the number of lattice points in the digital convex set.

(ii) Each digital convex subset of S is represented by a path in G Proof. Let △ i be the triangle represented by the node N i in G. Note that ρ is a vertex of △ i . Let p 1 and p 2 be the two other vertices of △ i such that the points ρp 1 p 2 are oriented clockwise. We call ρp 1 the left edge of △ i , and ρp 2 the right edge. By construction, all arcs starting from N i end into a node representing a triangle whose left edge is ρp 2 . Furthermore, if we denote p 3 the third vertex of this triangle, we have the point p 1 p 2 p 3 oriented clockwise.

Hence, every path

(N ∅ , N i 1 , N i 2 , N i k-1
) in G represents the fan triangulation of a polygon P = (p 1 , p 2 , ..., p k ) such that the points ρ, p 1 , p 2 , ..., p k are all in convex positions. As only the valid triangles are represented in G, all lattice points inside P are in S, and hence P ∩ S is digital convex. The length of the path is equal to the sum of the number of lattice points inside each triangle, minus the lattice points on the edges: (ρp2, ρp3, ..., ρp k-1 ), which is equal to the number of lattices inside P (Fig. 4.2). This proves (i).

Let P be the convex hull of a digital convex subset of S. Let △ 1 △ 2 ...△ k be the rooted fan triangulation of P . By construction, for each i from 1 to k we know that △ i is represented by N i in G, and for each i from

1 to k -1,
we know that there is an arc from N i to N i+1 . Hence, there is a path in G representing P . This proves (ii). For each i from 1 to n, we do the following. First, we sort all values of C h,i for h < i by decreasing value into a list C i . Then, we consider every △ i,j in the order given by T i , testing each C h,i from the largest area to the smallest. If C h,i ∪ △ i,j is convex, then we set C i,j = C h,i ∪ △ i,j . Otherwise, we permanently remove C h,i from the list C i (Fig. 4.3). Next, we justify the correctness of this procedure, especially the fact that we are allowed to remove the aforementioned values of C h,i from C i .

ρ i h 0 h 1 h 2 h 3 j 0 j 1 j 2 j 3 We assume C h3i > C h2i > C h1i > C h0i ρ i h 3 j 0 ρ i h 3 j 1 ρ i h 3 j 2 ρ i j 2 h 2 ρ i j 3 h 0 ρ i j 3 h 1 a) b) c) d) e) ρ i h 2 j 3 f) g) h)
Figure 4.3 Dynamic algorithm for the rooted peeling. a) At this step, we consider the point i .The four largest convex polygons ending at the point i: C h 0 i , C h 1 i , C h 2 i , and C h 3 i were previously computed by the algorithm. They are sorted according to their respective score. We will consider them in order from largest to smallest. In this step, we are computing C ij 0 , C ij 1 , C ij 2 , and C ij 3 . The points j 0 , j 1 , j 2 , and j 2 are sorted around i. We will treat them in their sorted order. b) We test ρij 0 with the largest polygon C h 3 i . Their union is a convex polygon therefore

C ij 0 = C h 3 i ∪ ρij 0 . c) We test ρij 1 with C h 3 i .
Their union is a convex polygon therefore

C ij 1 = C h 3 i ∪ ρij 1 . d) We test ρij 2 with C h 3 i .
Their union is not a convex polygon. We forget about C h 3 i for the remainder of the step, and we move on to the next largest convex polygon. e) We test ρij 2 with C h 2 i . Their union is a convex polygon therefore

C ij 2 = C h 2 i ∪ ρij 2 . f) We test ρij 3 with C h 2 i .
Their union is not a convex polygon. g) We test ρij 3 with C h 1 i . Their union is not a convex polygon. h) We test ρij 3 with C h 0 i . Their union is not a convex polygon. As there is no convex polygons left we can conclude that C ij 3 = ρij 3 .

Since we sorted the list T i of △ i,j counter-clockwise by p j around p i , we have the following key property. For each △ i,j preceding △ i,k in the ordering T i , we have that for all h < i if C h,i ∪ △ i,j is not convex, then C h,i ∪ △ i,k is not convex either. Hence, the values of C h,i removed from C i cannot form a convex polygon with the triangles △ i,j that appear later in the list T i .

The running time of the dynamic programming part for each value of i is the following. First, we retrieve the angular sorted list of valid triangles

k-Digital Potato Peeling

In this section we give interest and present an algorithm to solve the k-digital potato-peeling problem that we define as follows. Output: k subsets K i ∈ S that are digital convex (i.e., conv(K) ∩ Z 2 = K), such that K = i K i is the largest, where largest refers to |K|.

Note that the 1-digital potato peeling problem is the potato peeling problem that we solved in O(n 3 +n 2 log r) time in Section 4.1. In 2018, we published a specific algorithm for the 2-digital potato peeling [START_REF] Crombez | Peeling Digital Potatoes[END_REF], its running time is roughly O(n 9 ). Here we present the first algorithm that solves the more general k-digital potato peeling. Its running time is O(n 4k + n 2 log r), which improves our previous best known algorithms for the 2-potato peeling problem [START_REF] Crombez | Peeling Digital Potatoes[END_REF]. The k-potato peeling introduces some new complications compared to the simpler digital potato peeling. Some of those complications come from the fact that the convex hull of two sets in a solution can intersect an arbitrarily large number of times, or that holes can be present in the middle of the union of several convex hulls (Fig. 4.4).

Once again, as in Section 4.1, we will characterize a digital convex subset by its convex hull. We note that any convex hull can be separated into two

x-monotone polylines that we respectively name the upper hull, which is the For two x-monotone polylines P L 1 , P L 2 both going from p 1 to p n to represent a convex hull, it is necessary and sufficient that one polyline always turns right and that the other polyline always turns left. Using this representation, we can incrementally build any convex polygon. While incrementally building the upper and lower hulls, we can ensure the convexity by simply testing the orientation of the angle when appending edges to the upper or lower hull. This means that during the construction of the hull, and at any time only the last appended edge needs to be known for each partial half hull. The construction is finished once both half hulls ends at the same point.

Computing the number of points inside the hull

The previous method, allows to build a set of edges that represent a convex polygon P while only maintaining the knowledge of 2 edges at any time. In this section, we show how we can use this method to compute the surface inside P while only maintaining the knowledge of 2 edges at any time.

Unlike the appending done in Section 4.1 in order to solve the digital potato peeling problem, the method we just described does not directly append surfaces together, but edges. Hence, using the method as is, the number of points inside P cannot be computed. In order to do so, we add the following ordering rule during the construction.

When choosing whether we append an edge to the top hull or to the bottom hull, we chose to only append an edge to the least advanced of the two currently known edges. We define the least advanced edge as follows:

Given two edges e 1 and e 2 respectively delimited by the points (p 1 (x In other words, the least advanced edge is the one with the smallest maximal

x-coordinate. This definition can be extended to more than two edges.

We now explain how this least advanced edge rule allows us to effectively compute the surface of the convex polygon P we are building, while only maintaining the knowledge of at most two edges at a time. We call horizontal span of any geometrical object O the smallest interval I such that for each point p(x, y) ∈ O, x ∈ I.

At each step of the computation only two edges are known: one for the upper hull and one for the lower hull. We define I u (resp. I l ) to be the horizontal span of the currently known upper edge (resp. lower edge), and

I = I u ∩ I l .
Let H u (resp. H l ) be the half plane that is located below the upper edge (resp. above the lower edge), and let V be the vertical strip of ∞ height whose horizontal span is I. In order to compute the surface inside P , what we do is that when appending an edge, we compute the trapezoid defined as: H u ∩ H l ∩ V (Fig. 4.6).

P is equal to the union of all the trapezoid, in deed: Consider any edge e u of the upper hull. By only appending an edge to the least advanced half hull we ensure that for every edges of the lower hull e l such that e u and e l have an intersecting horizontal span, both e u and e l , at some point during the construction, will be known at the same time. Hence the entirety of the surface inside the convex hull will be considered, without any overlap.

As P is equal to the union of all the trapezoid, and as the intersection on any two adjacent trapezoid is a segment that is known during the computation, we can compute the area, or the number of lattice point inside P .

We now generalize this method in order to compute the surface of the union of any fixed number k of convex polygons. This time the construction requires us to know 2k edges at any time, that is 2 edges for each polygon, one for each half hull. The idea stays exactly the same as for one convex polygon. At each step of the computation, only the least advanced of the 2k edges is allowed to advance, and we only compute the area in the vertical strip of common xcoordinates to all the 2k edges. However, a special attention must be paid to polygons that have not started yet, or have already been finished. Those two situations are detected and dealt with in the following manner: if the upper edge and the lower edge of a same convex polygon start (resp. end) at the same point, this means that those are the starting (resp. ending) edges of said polygon. In this case we consider that the abscissa of those edges spans starts from -∞ (resp. goes until ∞)) when computing the common horizontal span.

We know that all convex polygons have been computed when, for each convex polygon, the upper edge and the lower edge end at the same point (Fig. 4.7). Now, we will show how using the aforementioned representation, we can build the succession of edges (that we call convex path) that describes and allows to compute the cardinality of any union of k digital convex polygons in S, while working with only 2k edges at a time. In order to solve the k-potato peeling problem, we want to find the convex path that leads to the largest union of k digital convex sets. We call partial convex path the beginning of any convex path. Unlike a convex path, the end upper edges and lower edges of a partial path does not necessarily meet.

An upper edge u e and a lower edge l e are said compatible if there is a convex

a) b) c) f ) e) g) d)
Figure 4.7 Visualisation of the k-peeling algorithm. Only the surface in the abscissa common to all edges is computed. When the two edges of a same convex polygon start from the same point (as seen in a) ), we extend the abscissa of those edges from -∞. Similarly when the two edges of a same convex polygon end at the same point (as seen in f ) and g) ), we extend the abscissa of those edges towards ∞.

polygon P such that in the construction we previously described both u e and l e can appear at the same time under the least advanced constraint(Fig. 4.8), that is if:

• the lower edge is located entirely within the half plane below the upper edge, and if

• the upper edge is located entirely within the half plane above the lower edge, and

• if the lower edge and the upper edge have at most one common point (namely the starting or ending point), and if

• the intersection of their horizontal span different to ∅, and if

• the intersection of the convex hull of the two edges with S is digital convex. Furthermore, in the context of the k-digital potato peeling, in order to ensure that the result polygon P is not only convex, but also represents a digital convex subsets of S, we add the constraint that conv(u e , l e ) ∩ Z 2 ⊂ S.

We now present two algorithms that solve the k-digital potato peeling problem using the aforementioned construction to describe a union of k convex polygons. The first algorithm embeds the problem in a DAG and runs in roughly O(n 4k+1 ) time. The second algorithm relies on dynamic programming for a total running time of roughly O(n 4k ).

Using a DAG

The strategy is to encode the problem in a DAG G(V, E) whose longest path corresponds to the solution of the problem. Once again, to avoid confusion, we use the terms node and arc when referring to a DAG and keep the terms corresponding to the common horizontal span of all the edges of a given node N . Let S i be the surface in between the upper edge N (C i (u i )) and the lower edge N (C i (l i )) of the i th convex polygon within the horizontal span defined by I (Fig. S i minus the number of lattice points in S union whose x-coordinate are equal to the minimal x-coordinate in S i , unless the lattice point is the starting point of both the currently known edges of the same convex polygon (and hence is the starting point of both partial hull). This represents the lattice points inside the surface of the intersection of all the different convex polygons in the common horizontal span minus those that where already accounted for in the previous node.

We add to G a start node and an end node. There is an arc from the start node to N if ∀i N (C i (u i )) and N (C i (l i )) start from the same point, that is if all convex polygons are still being represented by their first pair of edge. Similarly, there is an arc from N towards the end node if ∀i N (C i (u i )) and N (C i (l i ))

end at the same point, that is if all convex polygons are being represented by their last pair of edge.

We now explain, in Lemma 16 why each path in G represents the union of k digital convex sets and why the number of lattice points of the intersections of the convex hull of those sets is properly computed. Lemma 16. Every path in G going from the start node to the end node represents the union of k digital convex sets. And the length of the path is equal to to the number of lattice points inside the union of those k digital convex sets.

Proof. We consider any path in G that goes from the start node to the end node. The first node visited after the start node gives, two edges for each one of the k convex polygons we are building. For each polygon, these two edges are the start of the bottom hull and the start of the top hull. From now on, thanks to the way the arcs were added to the graph, each node visited, to the exception of the end node, will change exactly one edge to one polygon in the representation of the k convex polygons. This edge is added in such a way that ensures convexity with the one it replaces. As for each of the k polygons P i , their top hull T i and bottom hull B i do start at the same point s i and end at the same point e i , we know that they do represent a convex polygon. Now, the fact that the number of lattice points in the union of the k convex polygons is properly computed comes from the fact that:

• At each node, we only considered the surface in the common horizontal span (A special attention is given to the left limit of this horizontal span). This ensure that no overlap exists between two different nodes of the same path.

• Each arc only allows to change the least advance edge. This makes sure that, for every node, the common horizontal span is adjacent to the common horizontal path of its predecessor. This ensure that all the surface of the union of the convex polygons is considered (Fig. 4.7).

Finally, as only pairs of compatible edges are present in every node of G, we know that every convex polygon represented in a path in the graph is a digital convex subset of S.

Dynamic programming

We can use the same strategy that we used in Section 4.1 that allowed us to go from an O(n 4 ) time algorithm using a DAG representation to roughly an O(n 3 ) time algorithm using dynamic programming. This way, we can propose a roughly O(n 4k ) time algorithm to solve the k-digital potato peeling problem.

To do so, we consider the following sub-problem: Problem 6 (partial k-digital potato peeling). Given k pairs of compatible edges, what is the maximal partial convex path that has those edges as currently known edges. p i clockwise. This order gives us the following property which will be useful later.

Lemma 17. For any given pair of points p h and p j such that h < i < j: if p h p i p j turns right then:

• For each p ′ h preceding p h in the ordering p ′ h p i p j turns right

• For each p ′ j preceding p j in the ordering p h p i p ′ j turns right also if p h p i p j does not turn right then:

• For each p ′ h following p h in the ordering p ′ h p i p j does not turn right

• For each p ′ j following p j in the ordering p h p i p ′ j does not turn right

We then fetch the O(kn 4k-1 ) previously computed largest partial convex paths that have p i as one of their upper hull end point of an upper edge, such that p i is the left most of all the 2k end points of edges, and such that all the pair of edges are compatible. We split those O(kn 4k-1 ) partial convex paths into O(n 4k-2 ) lists, so that all the members of a same list have their 4k -2 points that are not part of the upper edge that ends with p i identical.

For a given partial convex path, let p h be the point located on the same upper edge as p i . The lists are sorted according to the position of p h around p i clockwise. Those lists are now effectively ordered according to the orientation of the edge that ends at p i , and effectively their easiness to "turn right", and hence preserve convexity. All the O(kn 4k-2 ) lists will be treated iteratively in the same manner. Let consider one of those list and name it L. At this point, the weight of each partial convex path on L is the largest that ends precisely

Chapter Five Conclusion

In this dissertation we investigated algorithms for finding convexity in digital sets. We investigated two problems related to this topic and presented the first generic linear time algorithm for digital convex set recognition and solving the optimal digital convex polygon problem in 2 dimensions. The approach we use relies on two properties.

The first one is the quickhull algorithm and the fact that, in 2 dimensions, quickhull runs in linear time relative to the number of points for digital convex sets. A question worthy of investigation that naturally arises from this question is the complexity of the 3 dimensional quickhull algorithm on digital convex sets. While known bounds on the number f of faces of any digital convex set S in 3 dimensions, f = O(V 1/2 ), where V is the volume of the convex hull S [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF] might help proving that the worst case scenario for the quickhull algorithm for digital convex set in 3 dimension is not O(n 2 ), this approach seems unable to prove, nor disprove, that the time complexity upper bound for 3d digital convex sets might be lowered to O(n).

The second property used, allowed us to reduce the edge minimization subset whose convex hull has only 3 vertices. Despite the apparent simplicity of the problem, it is not trivial to find a better approach than naively testing all triplets of points in S and leads to the same complexity as the potato peeling algorithm.

Another, arguably more interesting example is the recognition of the union of two digital convex sets. While the problem can be solved in roughly O(n 8 ) time using the digital 2-potato peeling algorithm, it seems unlikely for this method to be optimal. Furthermore, in continuous geometry, the recognition of the union of two convex polygons can be solved in O(n) time [START_REF] Shermer | On recognizing unions of two convex polygons and related problems[END_REF], while solving the continuous potato peeling problem takes O(n 7 ) time [START_REF] Chang | A polynomial solution for the potatopeeling problem[END_REF]. While comparing the complexities of the continuous and digital version of the problems is not really relevant due to the different nature of the inputs (a set of vertices representing a polygon in continuous geometry, and a set a lattice points in the digital) the apparent simplicity of the problem in continuous geometry seems to be an indication that a better approach is possible for the digital problem. Moreover, while the continuous approach for the recognition of the union of two convex polygons can not be directly used for the digital version of the problem due to the fact that a clear unique contour is not defined for a lattice set, similar techniques deserve to be investigated.

Beyond the fact that the principle of computational digital geometry that consists in treating problems with digital inputs might lead to better results, investigating the connections between problems in computational geometry and digital geometry, such as covering and packing problems [START_REF] Brass | Research problems in discrete geometry[END_REF][START_REF] Jia | Validation of a digital packing algorithm in predicting powder packing densities[END_REF] for instance, could lead to new tools for both communities.

Figure 1 . 1

 11 Figure 1.1 Digital Convex Sets. Example of two digital convex sets that are not connected in term of induce grid subgraph.

Figure 2 . 1 Figure 2 . 2

 2122 Figure 2.1 Quickhull initialization. Points inside the partial hull (light brown) are discarded. The remaining points are potentially part of the hull.

11 Figure 2 . 3

 1123 Figure 2.3 Simple polygon from sorting. By sorting all the points around p, we can obtain a simple polygonization of the set S.

Figure 2 . 6 Lemma 1 .

 261 Figure 2.6 Shearing. On the left: A set of points before a horizontal shearing of three. Relatively to the bottom row, points from the second row are moved to the right by three, points from the third row are moved to the right by six, and so on. On the right: The same set of points after the shearing.

Lemma 2 .

 2 For any pair a and b of co-prime numbers, for any two consecutive Diophantine lines ℓ 1 : ax + by = c and ℓ 2 : ax + by = c + 1. There are no lattice points located in between ℓ 1 and ℓ 2 .

Figure 2 . 8

 28 Figure 2.8 Lattice width. Example of width of a lattice set along two directions, and its lattice width.

Figure 2 . 9

 29 Figure2.9 Range counting. The two possibilities for the triangle pqr. On the left: we have to remove the points below pq and qr from the points below pr. On the right: we have to remove the points below pr from the points below pq and qr.

  2.10). Sorting all points clockwise around each point can be done in O(n 2 ) time using the dual [8, Chapter 11]. The remaining of the computation takes O(n) time for each of the O(n) right-most points, hence the total preprocessing time is O(n 2 ).

  we add all the points in Q i to the global count. As the quadrant are induced by two lines, l h intersects at most three quadrants, the query time is O(n log 4 3 ). The same procedure can be applied to answer simplex range counting queries in the same time complexity, and simplex range reporting in O(n log 4 3 + k), where k is the number of points reported.

Lemma 5 .Theorem 6 .

 56 For any set S of n points in R d , there is a set H of n O(1) hyperplanes such that for any collection of disjoint cells each containing at least one point p ∈ S, if k is the maximum number of cells crossed by a hyperplane in H, then the maximum number of cells crossed by any hyperplane is O(k). For any set S of n points, let H be a set of m hyperplanes in R d . Given l disjoint cells covering S such that each cell contains at most 2n/l points of S and each hyperplane in H crosses at most k cells. Then, for any constant c, every cell can be subdivided into O(c) disjoint subcells such that each subcell contains at most 2n/(cl) points in S, and each hyperplane crossesat most O((cl) 1-1/d + c 1-1/(d-1) k + c log l log m)Using the set H of hyperplanes from Lemma 5, and successively applying Theorem 6 to the tree consisting of simply a root cell containing all n points of S, we successively construct hierarchies denoted Π 1 , Π c , Π C 2 ... of 1, c, c 2 , ... cells. Π c gives the first depth of a partition tree, then Π c 2 results in the second depth and so on. In the end, we obtain a partition tree of degree O(c). Let k(c j ) denote the maximum number of cells of Π c j crossed by any hyperplane, then: k(c j+1 ) ≤ O((cl) 1-1/d + c 1-1/(d-1) k(c j ) + c log l log n). The resulting tree has height O(log n), order (1 -1/d) and query cost O(n 1-1/d log n).

  For any set of n hyperplanes H in R d , r ≤ n, and constant b > 1, there exist k = log b r cuttings C 1 , C 2 , ..., C k such that C i is a 1 b i cutting of size O(b id ). Each C i is composed of simplices each contained in a simplex of C i-1 , and each simplex C i contains a constant number of simplices of C i+1 . Such a cutting can be computed in O(nr d-1 ) time.

Theorem 8 .

 8 If the input is a digital convex set of n points, then the quickhull algorithm has O(n) time and space complexities.

3. 1 Figure 3 . 1 Figure 3 . 2

 13132 Figure3.1 Quickhull regions. The preserved region (region in which we look for the next vertex to be added to the partial hull) is a triangle. This stays true when adding new vertices to the hull (as shown here in the bottom right corner). The partial hull (whose interior is shown in light brown) grows at each vertex insertion to the partial hull. The points in or on the boundary of the new region of the partial hull are discarded.

Theorem 9 .

 9 The digital convexity of a set S can be tested in O(n + h log r) time, where h = | conv(S)| ≤ O(n 1/3 ) and r is the diameter of S.

  2 n) 1/3 . Computing | conv(S) ∩ Z 2 | using Pick's formula requires the computation of both the area of conv(S) in O(h) time and the number of boundary lattice points, which requires the computation of a greatest common divisor for every edge. Hence, this takes O(h log r) time where h = | conv(S)| and r is the diameter of S. As S is digital convex if and only if |S| = | conv(S)∩ Z 2 |, we can effectively test digital convexity in O(n + h log r) time.

Figure 3 . 3

 33 Figure 3.3 Edge Minimization and Polygonal Separation. To the left, an example of the edge minimization problem. The lattice set represented by the blue points is separated from the remainder of Z 2 by the black triangle. To the right, an example of the polygonal separation problem. The black triangle encloses all points from the blue set and none from the red set.

Lemma 10 .

 10 For any three lattice points p 1 , p 2 , p 3 such that p 1 , p 2 are located on the line ax + by + c = 0 (coefficients a and b are coprime) and p 3 does not, we have that the triangle p 1 p 2 p 3 either contains a lattice point on the line ax + by + c + 1 = 0 or on the line ax + by + c -1 = 0.

p 1 p 2 p 3

 3 contains an integer point on the line x = 1. The lower and upper points of the triangle in the line x = 1 are the two intersection points of x = 1 and each of the two segments p 1 p 3 and p 2 p 3 . Their coordinates are respectively (1, w v ) and (1, u+ w-u v ). Then the intersection of the line x = 1 and the triangle p 1 p 2 p 3 contains an integer point if and only if the interval [ w v , uv+w-u v ] contains an integer namely if the interval [w, w + u(v -1)] contains a multiple of v, which is trivially true since there is necessarily a multiple of v in any interval [w, w + v[ and then in [w, w + v -1] ⊂ [w, w + u(v -1)] as u ≥ 1, and thus

  The jewel hull consists of the intersection of a set of h halfplanes. Computing the vertices of the intersection of halfplanes is the dual[START_REF] De | Computational Geometry: Algorithms and Applications. 3rd ed[END_REF] Chapter 8] of the computation of the convex hull of a given points set. In the general case, computing the intersection of h halfplanes takes O(h log h) time [8, Chapter 4]. However, since we already have the h halfplanes sorted by slope, we can use Graham scan [8, Chapter 1] to compute the jewel hull in O(h) time. Notice

  lem. The jewel hull J has been computed and the problem is the polygonal separation of IN = S and the jewel set OUT ′ = Jewel(S). The previous step does not provide the set of jewels but the ordered list of edges of the jewel hull J as a sequence of linear equalities ℓ i : a i x + b i y + c i = 1 with coprime integers a i and b i . An initial lattice point d i of each given Diophantine straight line ℓ i can be computed with the extended Euclid algorithm in O(log r) time. We can go from this first point to the other integer points of the line ℓ i through translations of vectors k -----→ (-b i , a i ) where k ∈ Z. Nevertheless, J is a rational polytope. Its vertices are the intersection points of consecutive Diophantine lines ℓ i but they are not necessarily integer points. It is even possible that some edges of the jewel hull do not contain any integer point. By computing the vertices of each edge e i we can count all the jewels on ℓ i and obtain a generating formula for them in O(1) time and space for each edge. The jewels on ℓ i are: k d i + k(-b i , a i ). The computation of an integer point d i per line ℓ i for each one of our at most h Diophantine lines takes O(h log r) time. The computation of the vertices of J takes O(h) time, and hence the computation of the formulas generating the jewels takes O(h log r) time and O(h) space.

Figure 3 . 6

 36 Figure3.6 Turn algorithm. We start from a chosen starting jewel p i 0 and search for its last successor p j 0 that can be separated from S simultaneously with p i 0 by a single line. We then take the successor of p j 0 as new starting jewel p i 1 and search for the last successor p j 1 of p i 1 that can be separated with p i 1 ... We repeat the process until reaching the predecessor of p i 0 .

Figure 3 . 7

 37 Figure 3.7 Jewel separation.a) If a single line separates both p 1_2 and p 2_2 , then the triangle △p 1_1 p 1_2 p 2_2 is larger than △p 1_1 p 1_2 p 2_1 and hence must contain a fourth lattice point, which is impossible. b) No jewels are located between e i+1 and ℓ i+1 hence it is impossible to separate simultaneously jewels from ℓ i and jewels from ℓ j .

1 : 2 : 3 :

 123 Test the digital convexity of S and compute conv(S) using quickhull Compute the jewel hull of S using Graham scan Compute at most four starting jewels 4: for all starting jewels do 5:

Figure 4 . 2

 42 Figure 4.2 Rooted peeling graph.Example of a DAG built to solve the rooted peeling problem for 6 valid triangles. For two triangles to be connected by an arc in the graph, they need to have a common edge that starts from ρ, and their union must be a convex polygon. The weight of each arc is equal to the number of lattice points inside the right-most triangle that are not located on the common edge between the two triangles.

  Computing the longest path in the DAG G takes linear time in the number of arcs in G. The number of nodes in G is at most O(n 2 ), and each of these nodes has at most n incoming arcs. Hence the number of arcs in G is O(n 3 ) and the rooted digital potato peeling problem can be solved in O(n 3 ) time after O(n 2 log r) time preprocessing. Now, in order to solve the digital potato-peeling problem, we solve the rooted digital potato-peeling for each of the n possible roots. As the preprocessing is common to each instance of rooted potato-peeling problem, we only have to preprocess once. Which leads to an O(n 4 + n 2 log r) algorithm to solve the digital potato-peeling problem. angular sequences can be done in O(n 2 ) time using the dual[8, Chapter 11]. Moreover, testing the validity of each triangle takes O(1) time, which gives a total running time of O(n 2 ). Next, we explain the dynamic programming part of the algorithm.

TTheorem 15 .

 15 i . This step only takes O(n) time as we preprocess the angular sorting of all points around i. The remaining part also takes O(n) time since at each step, we either remove a convex polygon C h,i from C i or we advance through the list of triangles T i . Considering all n values of i and the initial sorting, the total time to solve Problem 4 is O(n 2 ). In order to solve Problem 3, we test all n possible values of ρ ∈ S, proving the following theorem. There exists an algorithm to solve Problem 3 (digital potato peeling) in O(n 3 + n 2 log r) time, where n is the number of input points and r is the diameter of the input.

Problem 5 .Figure 4 .

 54 Figure 4.4 k-peeling solutions. The convex hulls can intersect any number of times as shown in a). Furthermore, for 3 or more polygons, holes can appear as shown in b).

Figure 4 . 5

 45 Figure 4.5 Upper and lower hull. The upper hull (in blue) and the lower hull (in red) that both go from the leftmost point(p 1 ) to the rightmost point (p n ).

Figure 4 . 6

 46 Figure 4.6 Edge advancing. Of the two edges, only the least advanced one moves forward. Then the surface of the trapezoid (shown in dark orange) located between the upper edge and the lower edge is computed.

Figure 4 . 8

 48 Figure 4.8 Compatible edges.In a) the lower edge is not located below the upper edge. In b) the upper edge is not located above the lower edge. In c), the upper and lower edge have more than one point in common. In d) the horizontal spans of the lower and upper edge are distinct. In e) The intersection of S (shown in blue crosses) with the trapezoid is different from the intersection of Z 2 with the trapezoid. One lattice point is missing.

  4.6). The weight of a given node N is equal to the number of lattice points in: S union = i∈[1..k]

Furthermore, as all

  compatible edges are considered in the graph, naturally all unions of k convex digital subsets are indeed represented by a path in G, and hence finding the longest path in G is equivalent to solving the kdigital potato peeling problem. Since there are O(n 4k+1 ) arcs in G this part of the algorithm takes O(n 4k+1 ) time. In addition, in order to compute G, the algorithm requires to compute the compatible pair of edges. This can be done by iterating on all of the O(n 4 ) pairs of edges, and testing whether their convex hull represents a digital convex subset of S or not. This test takes O(1) time after a preprocessing time of O(n 2 log r) required in order to compute the number of lattice point on each edge, and an extra preprocessing time of O(n 2 ) required for the triangular range counting algorithm presented in Section 2.3.1. Solving the k digital potato peeling using a DAG hence result in a time complexity of O(n 4k+1 + n 2 log r) using O(n 4k+1 ) space.

  [START_REF] Bárány | On the number of convex lattice polygons[END_REF] Binary search. We are looking for the point p j such that all the other vertices of the convex hull are located to the right of p i p j . a) p k/2-1 is on the left of p i p k/2 , hence p j is in between p 0 and p k/2 . b) p k/2+1 is on the left of p i p k/2 , hence p j is in between p k/2 and p

k . c) Both p k/2-1 and p k/2+1 are on the right of p i p k/2 , hence

  .7.a). As the triangle △p 1_1 p 1_2 p 2_1 is not degenerated we have Area(△p 1_1 p 1_2 p 2_1 ) ≥ 1 2 . Hence the inequality Area(△p 1_1 p 1_2 p 2_2 ) > Area(△p 1_1 p 1_2 p 2_1 ) leads to Area(△p 1_1 p 1_2 p 2_2 ) > 1 2 . Using Pick's theorem we can conclude that △p 1_1 p 1_2 p 2_2 contains at least four lattice points. However, since p 1_1 p 1_2

  1 , y 1 ), p 2 (x 2 , y 2 )), and the points (p 3 (x 3 , y 3 ), p 4 (x 4 , y 4 )), such that xmax e1 = M ax(x 1 , x 2 ) and xmax e2 = M ax(x 3 , x 4 ). e 1 (resp. e 2 ) is the least advanced edge if and only if xmax e1 ≤ xmax e2 (resp. xmax e2 ≤ xmax e1 ).

3 ℓ(S) + 1[START_REF] Bárány | On the lattice diameter of a convex polygon[END_REF].

Chapter Four Digital Convex Subsets

In this chapter, we develop algorithms to compute digital convex subsets. More precisely, we investigate a digital version of the potato peeling problem [START_REF] Chang | A polynomial solution for the potatopeeling problem[END_REF] that we call digital potato peeling and in which the goal is, given a set S, to find the largest digital convex subset of S. This problem has been stated in 2004, and a first heuristic given in 2005 [START_REF] Chassery | Optimal shape and inclusion[END_REF].

In Section 4.1, we propose an embedding of the digital potato peeling problem in a directed acyclic graph (DAG) that leads to an O(n 4 + n 2 log r) algorithm to solve the digital potato peeling problem. Then, using the same strategy, we present an optimization of the algorithm that leads to a dynamic programming algorithm that runs in O(n 3 + n 2 log r) time.

In Section 4.2, we consider the k-digital potato peeling problem in which we look for the largest union of k subsets of S. Once again, we propose an embedding of the problem in a DAG, leading to an O(n 4k+1 + n 2 log r) algorithm. We then show how a similar optimization as in Section 4.1 leads to a dynamic programming algorithm that runs in O(n 4k + n 2 log r) time.

In this chapter, we consider the largest digital convex subsets to be the ρ The difference between the digital potato-peeling problem and its rooted variation is that in the digital potato peeling the bottom-most point is not necessarily in the solution, whereas the bottom-most point is forced to be in the solution in the rooted version of the problem. The idea we develop in this section consists in solving the digital potato peeling problem by testing all possible roots for the rooted version of the problem.

In the rooted version of the problem, we only have to consider points in S that are located either above ρ or on the same row as ρ to its left. We refer to this subset of S as S ρ , and we refer of ρ as the root. Let p 1 , . . . , p n denote the points of S ρ sorted clockwise around ρ, starting from the left.

Let △ i,j denote the (closed) triangle whose vertices are ρ, p i , p j with i < j.

We say that a triangle △ i,j is valid if △ i,j ∩ Z 2 = △ i,j ∩ S, that is if all the lattice points inside △ i,j are in S. To algorithmically verify that △ i,j is valid, we compare |△ i,j ∩ S| and |△ i,j ∩ Z 2 |. The value of |△ i,j ∩ Z 2 | is determined as follows. Pick's theorem states that the area of a triangle with lattice vertices is equal to n b /2+n i -1, where n b is the number of boundary lattice points and n i is the number of interior lattice points. The value of n b can be computed using a GCD computation for each edge in O(log r) time, where r is the diameter of the triangle. Plugging in the area of the triangle, we obtain the number of lattice points |△ i,j ∩ Z 2 | = n b + n i . To compute |△ i,j ∩ S| we use a triangle range counting query described in Section 2.3.1. We remind that those queries can be answered in O(1) time after preprocessing S in O(n 2 ) time [START_REF] Eppstein | Finding minimum areak-gons[END_REF]. Hence, the total time to test the validity of a triangle (after preprocessing) is O(log r).

However, on the account that there is O(n 3 ) triangles and only O(n 2 ) edges, we preprocess the number of lattice points on each edge in O(n 2 log r) time and are able to test the validity of triangle in O(1) time after a preprocessing of O(n 2 log r) time.

We now consider K i , a digital convex subset of S ρ whose root is ρ. We can build conv(K i ) by appending the triangles of its fan triangulation clockwise.

All the triangles used have lattice vertices, are valid, and their bottom-most vertex is ρ. Now; in order to solve the rooted digital potato-peeling problem, we want to find the appending that results in the largest K i possible.

Directed Acyclic Graph embedding

We start by showing how to find the largest digital convex subset K i by building a DAG G that represents all the possible ways to append rooted triangles in a convex manner. Then, in a second time, we will present a faster dynamic

Dynamic programming

We now show that the same idea of fan triangulation and clockwise triangles appending can lead to a dynamic programming algorithm that runs in O(n 3 + n 2 log r) time. This algorithm makes use of the same precomputation as the DAG one we just presented.

Once again, we present an algorithm that solves the rooted potato-peeling problem, and we then use this algorithm to solve the potato-peeling problem by trying every root possible.

The algorithm incrementally builds the fan triangulation of conv(K) by appending valid triangles in clockwise order using dynamic programming. At each step, we ensure the digital convexity through the following property. Let conv(K ′ ) be the convex hull of a digital convex set K ′ rooted at ρ with △ h,i as the right-most triangle. If △ i,j is valid and △ h,i ∪ △ i,j is convex, then

First, we sort all the points around ρ clockwise. The idea of the algorithm is the following: for all pairs of points p i , p j ∈ S ρ with i < j such that △ i,j is valid, we want to compute the largest convex polygon amongst that have △ i,j as their last triangle in the clockwise rooted fan triangulation. We refer to this largest convex polygon as C i,j . The key property to efficiently compute C i,j is

In order to compute C i,j , we do the following. For each value of i, we sort all valid △ i,j for j > i in counter-clockwise order of p j around p i into a list of triangles T i , obtaining n lists of O(n) triangles each. Sorting all vertex and edge when referring to polygons.

We build G in the following manner. Each node of G represents k ordered pairs of compatible edges. Within a node, each pair of compatible edge represents the upper edge and the lower edge of a convex polygon. As there are O(n 4 ) pairs, we have at most O(n 4k ) nodes in G.

a pair of compatible edges, and where u i (resp. l i ) denotes the upper edge (resp. lower edge) associated to the representation of the i th convex polygon.

We put an arc from the node N 1 towards the node

and N 1 (C j (l j )) ends at the same points that N 2 (C j (l j )) starts, and such that N 1 (C j (l j )) and N 2 (C j (l j )) forms a convex angle. We also put an arc between from

and N 1 (C j (l j )) = N 2 (C j (l j )), and N 1 (C j (u j )) ends at the same points that N 2 (C j (u j )) starts, and such that N 1 (C j (u j )) and N 2 (C j (u j )) forms a convex angle. In more simple terms, we put an arc between two nodes if and only if only one edge changes between these two nodes, the changed edge has to be the least advanced one in order to respect the least advanced rule, and the new edge has to be compatible with both: the edge it replaces (preserving convexity), and its associated lower/upper edge.

As there are at most n arcs exiting a node, there are at most O(n 4k+1 ) total arcs in G.

We now explain how we weight the nodes in G. Let I be the interval Once all the compatible pair of edges are computed, we sort all the points of S, from left to right. Let p i denote the i th point of S in this sorted order.

We then iterate on the p i in their sorted order and will consider the partial path that ends at p i . We hence consider two distinct possibility: p i is in a upper edge and p i is in a lower edge. As those two situations are treated with the exact same approach, we only describe the case where p i in an upper edge. At this point, we fetch every point p j , j > i and sort them around p i counter-clockwise, we also fetch all the points p h , h < i and sort them around with p h p i (and the other 4k -2 points associated to L), we now update those weights so that they represent the size of the largest partial convex path that ends with p h p i (and the given 4k -2 points associated to L) or a harder to turn right edge than p h p i . To do so, iteratively we update the weight of each element in the following manner: If the weight of the element is lower than the weight of the element directly before it, we set the weight of this element to the weight of the element directly before it. After this, the weight of each element is effectively the max of its own weight and the weight of all the elements before it. Now, for all p j , j > i, taken iteratively in their counter-clockwise sorted order we look for the largest partial convex path that ends with p h p i (and the 4k -2 other points) in L, starting from the end. We then replace the edge p h p i with the edge p i p j (if p i p j is compatible with the associated lower edge), and add the weight associated to the addition of this edge, and update the largest partial convex path that ends with p i p j (and the 4k -2 associated points). When moving forward to the next p j , we do not have to start from the back of L all over again, we can simply continue from where we were with the previous point thanks to Lemma 17.

Complexity analysis

We first compute the compatible pair of edges by iterating on all of the O(n 4 ) pairs of edges, each verification takes O(1) time, but requires O(n 2 log r)

preprocessing. We then iterate on O(n) points p i . For each of those points we sort two lists in O(n log n) time (Note that all angular sorting could be obtained in O(n 2 ) time instead of the O(n 2 log n) time described in this algorithm, but this does not change the global complexity of the algorithm), we then fetch O(n 4k-1 ) elements that we sort into O(n 4k-2 ) lists each of size O(n) (as all the sorting is done according to the previously computed angular sorting, this step takes only O(n 4k-1 ) time), then for each of those O(n 4k-2 ) lists we update the weight and do the appending to the p j , j > i in O(n) time. Hence the following theorem: Theorem 18. The k-potato peeling problem can be solved in O(n 4k + n 2 log r) time where r is the diameter of S, and n its cardinality.

problem to a polygonal separation problem with a linear number of points relative to the size of the input. This property is tightly tied to Diophantine lines and Pick's theorem, as a consequence the lack of result similar to the Euclidean algorithm in 3 dimension makes a similar approach unlikely to work in higher dimensions.

We then changed the topic from finding smallest enclosing convex polygons to finding the largest included ones. Our investigation of this topic resulted in us presenting the first polynomial time algorithm running in roughly O(n 3 ) time for the digital potato peeling problem, and the first polynomial time algorithm for the digital k-potato peeling problem (when k is fixed). The approach used to solve the potato peeling is similar to the one used to solve the optimal island problem [START_REF] Bautista-Santiago | Computing optimal islands[END_REF], with an adaptation to test the digital convexity. However, using the same technique of embedding the problem in a DAG, but using another representation of the convex hulls, moving from a fan triangulation approach to a top-bottom hull separation we were able to propose a polynomial time algorithm for the k-potato peeling problem. Note that the approach used to solve the digital k-potato peeling can also be adapted to solve an extension of the optimal island problem where the goal would be to find the largest union of k monochromatic islands instead of simply the largest monochromatic island.

Interestingly, several problems simpler than digital potato peeling have no known algorithms that are quicker than the use of the digital potato peeling algorithms presented in this dissertation. Given a lattice set S, one such problem asks to find the largest digital convex triangle, i.e. a digital convex