Je Remercie

Imre Bàràny

Pierre Calka

Philippe Duchon

Christian Sohler D'

Analyses de complexité d'enveloppes convexes aléatoires

Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne (c'est à dire le nombre moyen de faces de toutes dimensions) d'enveloppes convexes de points choisis dans un convexe. La taille moyenne de l'enveloppe convexe est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse»; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée.

Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d'analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l'algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire , ainsi que dans le cas de perturbations gaussiennes en dimension 2.

Le comportement asymptotique de la taille moyenne d'une enveloppe convexe de points choisis uniformément dans un convexe est polynomial pour un convexe «lisse» et polylogarithmique pour un polytope. Dans la deuxième partie, nous montrons comment construire un convexe tel que la taille moyenne de l'enveloppe convexe de points choisis uniformément dans ce convexe oscille entre ces deux comportements lorsque le nombre de points augmente.

Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque, ainsi que l'analyse de sa complexité moyenne en temps et en mémoire. Cet algorithme permet d'obtenir rapidement une enveloppe convexe aléatoire sans avoir à engendrer explicitement tous les points. Il a été implémenté en c++ et intégré dans la bibliothèque cgal.

In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and an upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2.

The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases.

In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in c++ and integrated in the cgal library.

Introduction

In computational geometry, an important interest is to evaluate the size complexity of the geometric objects used by an algorithm. For a given structure, the worst-case can be very pessimistic, making the structure complicated to deal with. However, the worst-case, sometimes, does not reflect the behavior in practice. For example, a realistic terrain of triangles usually have a linear visibility map complexity, even if the worst-case is quadratic. The same problem appears when dealing with the running time of algorithm: the worst-case of the simplex algorithm is known to be exponential, even if it works well in practice. In these cases, the worst-case complexity does not seem to be a good quality measure of the general behavior.

A first attempt to explain a good behavior in practice is the average case. Suppose that the input data are randomly distributed, what is the expected complexity? If the worst cases appears with small probability, you can hope that the expected complexity becomes more optimistic. One of the most famous example for every computer science student is the complexity of the quicksort algorithm: the worst-case is quadratic (for example if the datas are already almost sorted), however if the pivot is chosen uniformly at random, the expected complexity becomes quasilinear.

Even if the average case is sometimes more optimistic, it can still be a bad quality measure, if the random hypothesis is not realistic. Especially, asking the input data to be randomly and independently distributed 1 can be too much to ask when the data are supposed to come from the "real world".

A new notion of complexity, the smoothed complexity, has been introduced as an intermediate notion between the worst-case complexity and the average complexity. The main insight is to suppose that the input data are arbitrary (like in the worst-case) but are slightly perturbed by a random noise. Now, computing the smoothed complexity resumes to bound the expected complexity of the noisy data (the expectation being taken according to the noise). It's a kind of interpolation between the worst-case and the average case: taking no perturbations corresponds to the study of the worst-case, and taking a huge perturbation roughly corresponds to the average case (the perturbation is so huge that the initial input value does not play a role anymore). This kind of complexity analysis works well when the 1 For quicksort, the randomness comes only from the choice of the pivot.

1

INTRODUCTION

worst-case is really unstable: perturbing the data a little bit decreases the order of magnitude of the complexity. As real data come from measures and are rounded to be stored in a computer, they will be sligthly perturbed so it's really unlikely that the user get a bad input. We describe some results of the smoothed complexity in Section 1.2.

In this thesis, we focus on the complexity analysis of convex hulls. This geometric structure is fairly used in computational geometry, computer graphics, so that's an interesting question to get informations about its number of faces. The worst-case is known and increases exponentially with the dimension, so this is a very pessimistic bound.

Stochastic geometry gives several results on the average complexity of convex hulls, under several random distributions in arbitrary dimension. We describe some of their result in Section 1.1. In the case where the points are initially chosen uniformly in an arbitrary convex set, the exact behavior is known only if the set is a polytope or a smooth convex set. If the convex set is not in these categories, then the expected size of the convex hull is, most of the time, unpredictable. In Chapter 3, we construct such a bad convex set, where the expected size of a convex hull of points uniformly chosen in oscillates asymptotically between two regimes.

We propose, in Chapter 4, an algorithm that generates a random convex hull, made of random points in a disk. A trivial way to do it would be to generate all the points in the disk, and then compute the convex hull. However, once you generate a small number of points, you already know that every point falling inside the convex hull of these first points will not be part of the final convex hull. Our algorithm reduces the number of points to generate, by estimating how many points will fall on a region where we already know that they will not be part of the output.

The main results of the thesis are describe in Chapter 2, where we focus on the smoothed complexity of convex hulls. These results, proved using the Witness & Collector technique, give an upper and lower bound on the smoothed complexity for two kind of random perturbations: the uniform distribution in a ball and the Gaussian distribution. The uniform case will be considered in arbitrary dimension, and the Gaussian case will be done in dimension 2. Since the Witness & Collector technique is defined with general settings, we can adapt it to obtain classic stochastic geometry results, but with a very simpler proof.

INTRODUCTION

Chapter 1

State of the Art

In this chapter, we describe some results on stochastic geometry, computational geometry and algorithmics, that are related to the presented work.

Section 1.1 presents some results in stochastic geometry, where we consider the convex hull of points indentically distributed. In particular, we describe the tools and intermediate results used to find the expected number of faces of these convex hulls. Section 1.2 and Section 1.3 describe the notion of smoothed analysis, and give applications to several problems. We focus on the analysis of algorithms with bad worst-case complexity, as well as the analysis of geometric structures. We also outline the proof for each example. The Sylvester's four-point problem is, maybe after the Buffon's needle problem, the first and most famous problem in stochastic geometry. In 1865, Sylvester [START_REF] Sylvester | On a special class of questions on the theory of probabilities[END_REF] asked the probability, for four points randomly chosen in the plane, to be in convex position. Several answers have been sent with different results. Actually, the result depends on the method chosen to "pick a random point in a plane", so the problem is not well-defined.

Since then, numerous results have been proved, if we restrict the random points to be chosen uniformly in a convex set, for example, so that the probability measure is well defined. Blaschke [START_REF] Blaschke | Vorlesungen über Differenzialgeometrie II. Affine Differenzialgeometrie[END_REF] showed that for any convex set (with non-empty interior) K ⊂ R 2 , the probability, for four points independently and uniformly chosen in K, to be in convex position, is lower bounded by the case where K is a triangle, and upper bounded by the case where K is a disk.

Valtr [START_REF] Valtr | The probability that n random points in a triangle are in convex position[END_REF] found the explicit formula for the probability, for n points uniformly chosen in a triangle, to be in convex position. Recently, Marckert [START_REF] Marckert | Probability that n random points in a disk are in convex position[END_REF] found a recursive formula to compute the probability, for n points uniformly chosen in a disk, to be in convex position. The formula is explicit only for n very small. This result shows that even in very simple settings, the problem is still not completely understood.

More generally, the Sylvester problem started the fertile research on the properties of the convex hull of n random points.

Random polytopes

Let X 1 , . . . , X n be n points independently and identically chosen according to some distribution function. Let K n = CH (X 1 , . . . , X n ) (1.1) be the convex hull of these random points. We use the standard notation f ℓ (K n ) to be the number of ℓ-dimensional faces of K n and vol (K n ) its d-dimensional volume.

Properties of such a polytope (e.g. its number of faces or its volume) have been a well studied topic during the last decades and has several applications in algorithmics, optimization, biology. . . References for such applications can be find in the introduction of the survey of Reitzner [START_REF] Reitzner | Random polytopes[END_REF]. If several properties have been studied (e.g. central limit theorems), in this section we only describe some results about the expected number of faces of K n .

A random polytope defined as the convex hull of points uniformly chosen in a disk Convex Hulls of Uniform Points. Let K a compact convex set of R d with nonempty interior (such a set is called a convex body). We choose the distribution of the points X 1 , . . . , X n to be uniform in K. The properties of K n will (in general) depend on the shape of K. However, a very useful formula, proved by Efron [START_REF] Efron | The convex hull of a random set of points[END_REF] in 1965, transforms the computation of the expected number of vertices of K n into the computation of an expected volume for any arbitrary convex body K:

E [f 0 (K n )] = n vol (K) E [vol (K \ K n-1 )] . (1.2)
The first result on the expected volume of K n (and so on its number of vertices) comes from Rényi and Sulanke in 1963 [START_REF] Rényi | Über die konvexe Hülle von n zufällig gewählten Punkten I[END_REF][START_REF] Rényi | Über die konvexe Hülle von n zufällig gewählten Punkten II[END_REF]. They computed the asymptotic behavior of E [vol (K n )] when K is "smooth" and when K is a polygon, in dimension 2.

These results has been generalized for higher dimensions, the best estimation being the one given by Reitzner [START_REF] Reitzner | The combinatorial structure of random polytopes[END_REF]:

• If K is a smooth convex body, i.e K has a twice differentiable boundary with positive Gaussian curvature, for any ℓ ∈ {0, . . . , d -1},

E [f ℓ (K n )] = c 1 (d, ℓ, K)n d-1 d+1 + o(n d-1 d+1 ) (1.3) • If K is a polytope, then E [f ℓ (K n )] = c 2 (d, ℓ, K) ln d-1 n + o(ln d-1 n) (1.4)
where c 1 (d, ℓ, K) and c 2 (d, ℓ, K) are positive constants depending only on d, ℓ and on K. The dependence in K can be given explicitly: c 1 depends on the curvature of ∂K, while c 2 depends on the combinatorial structure of K.

Floating Bodies. A way to compute an asymptotical estimation of E [f 0 (K n )] is the notion of floating body. Let the function v : K → R: v(x) = min{vol (K ∩ H) : H is a half-space and x ∈ H} to be the function that, given a point of K, measures the minimum volume of a cap containing the point. The floating body is the level set

K(v ≥ t) = {x ∈ K : v(x) ≥ t}
and the wet part is

K(t) = K(v ≤ t) = {x ∈ K : v(x) ≤ t}.
Imagine that K is, say, an inflated balloon containing a small quantity t of water. Thanks to gravity, the part that contains the water will corresponds to some cap K ∩ H (where H is a half-space) with volume t. Then, if you turn the balloon on all directions, the water will stand on every possible cap K ∩H with volume t. The union of these "wet" caps corresponds to K(t). The floating body corresponds to the volume inside the balloon that is never wet, and so floats above the water.

Gravity

Gravity

Wet part

Floating body

Efron's formula (1.2) allows to consider only the expected volume E [vol (K \ K n )] in order to compute E [f 0 (K n+1 )]. Bárány and Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF], showed that K 1 n and E [vol (K \ K n )] are related, so computing E [f 0 (K n )] becomes a pure geometrical problem:

Theorem 1 (Bárány, Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF]). Let K ⊂ R d be a convex body, vol (K) = 1. There exist some constants c 1 , c 2 (d) and n 1 (d) such that for n ≥ n 1 (d),

c 1 vol K 1 n ≤ E [vol (K \ K n )] ≤ c 2 (d) vol K 1 n . As a result, E [f 0 (K n )] is Θ n vol K 1 n
, where the constants depend only on the dimension.

Economic cap covering An important tool used in the proof of Theorem 1 is the so-called economic cap covering. Bàràny and Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF] proved that we can cover the wet part of K, without "over covering too much". More formally: Theorem 2 (Bárány, Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF]). Let K be a convex body in R d , vol (K) = 1, and 0 < ε < (d 2d ) -1 . There are caps C 1 , . . . , C m and pairwise disjoint convex sets C ′ 1 , . . . , C ′ m such that for each i, C ′ i ⊂ C i and:

• ∪ m i=1 C ′ i ⊂ K (ε) ⊂ ∪ m i=1 C i , • vol (C ′ i ) = Ω (ε) and vol (C i ) = O (ε), • Every cap C of volume ε is contained in some C i .
The caps C i cover the wet part K(ε) economically in the sense that

K(ε) = Θ (mε) .
This technique appears to be, in some ways, similar to the Witness & Collector technique developped in Section 2.2.

Estimation of the wet part

In this paragraph we suppose vol (K) = 1 for simplicity. The computation of the volume of the wet part has been done by Schütt and Werner [START_REF] Schütt | The convex floating body[END_REF] if K is smooth, and by Schütt [START_REF] Schütt | The convex floating body and polyhedral approximation[END_REF] if K is a polytope:

• If K is a smooth convex body, then for t ≥ 0, vol (K (t)) = c 3 (d, K)t 2 d+1 (1 + o(1)), • If K is a polytope, then for t ≥ 0, vol (K (t)) = c 4 (d, K)t ln 1 t d-1 (1 + o(1)).
These results, combined with Theorem 1, give the order of magnitude of E [f 0 (K n )] given in Equation (1.3) and (1.4). It appears that these two behaviors are extremal, since for any convex body K, and for t small enough,

K(t) = Ω t ln 1 t d-1
and

K(t) = O t 2 d+1
where the constants involved depends only on the dimension. This result has been proved by Bàràny and Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF]. Actually, if K is neither a polytope nor a smooth convex body, the behavior can be proved to be usually unpredictable. We construct such a convex body in Chapter 3.

Convex Hulls of Gaussian Points. Let's now define X 1 , . . . , X n as n random points in R d chosen according to the centered Gaussian distribution with variance -covariance matrix I d . Again we define K n as the convex hull of these points. This kind of polytopes are called Gaussian polytopes. The expected number of ℓ-faces of K n has been studied in arbitrary dimensions:

E [f ℓ (K n )] = c(d, ℓ) ln d-1 2 n (1 + o(1)) (1.5)
where c(d, ℓ) is a constant depending only on d and ℓ that can be explicited. This result comes from the work of Rényi and Sulanke [START_REF] Rényi | Über die konvexe Hülle von n zufällig gewählten Punkten I[END_REF][START_REF] Rényi | Über die konvexe Hülle von n zufällig gewählten Punkten II[END_REF] and Raynaud [START_REF] Raynaud | Sur l'enveloppe convexe des nuages de points aleatoires dans R n[END_REF].

Smoothed Analysis

Motivation

To understand and predict the practical behavior of an algorithm, a first step is to analyze how the amount of resources it requires grows with the size of the input. The basic building blocks of geometric algorithms are combinatorial structures induced by geometric data such as convex hulls or Voronoi diagrams of finite point sets, lattices of polytopes obtained as intersections of half-spaces, intersection graphs or nerves of families of balls... The size of these structures usually depends not only on the number of geometric primitives (points, half-spaces, balls...), but also on their relative position: for instance, the number of faces of the Voronoi diagram of n points in R d is Θ(n) if these points form a regular grid but Θ n ⌈d/2⌉ if they lie on the moment curve. (We assume here a Real RAM model of computation, so the points have arbitrary real coordinates and the input size is simply the number n of points.) There are two traditional approaches to account for how the complexity of a structure depends on the position of the points that induce it: the worst-case complexity, which measures the maximum of the complexity function over the input space, and the average-case analysis, which averages the complexity function against a suitable probability distribution on the space of inputs. Unfortunately, both approaches have shortcomings: the worst-case may be exceedingly pessimistic when the maximum is achieved only by constructions that are so brittle that it is unlikely they arise in practice,1 whereas the input distributions considered for the average complexity are often unconvincing for lack of relevant and tractable statistical models to work with.

The smoothed complexity model, proposed by Spielman and Teng [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF] in the early 2000's, interpolates between the worst-case and the average case model.

Informally, it is defined as the maximum over the inputs of the expected complexity over small perturbations of that input. Intuitively, this "local averaging" mechanism disposes of configurations that vanish under small perturbation and models more accurately the behavior on "real data", which is usually given with bounded precision and subject to measurement noise. In other words, the smoothed complexity quantifies the stability of bad configurations.

If we are given a complexity measure C(x) for a given input x, and if X n is the set of possible inputs with size n, then the smoothed complexity function

f (n, σ) is f (n, σ) = max x∈Xn E g [C(x + σg)]
where σg is a vector of random variables of mean 0 and standard deviation σ x ;

x being some measure of the magnitude of x. (This measure of magnitude depends on the problem, and can sometimes be simply 1.) Taking σ = 0 gives the worst-case complexity. On the other side, if we choose σ large enough (so that the contribution of x is negligeable compared to σg), one would expect to obtain the same behavior as the average-case. The smoothed complexity is said to be polynomial if f (n, σ) is a polynomial in n and 1/σ.

Smoothed Analysis of the Simplex Algorithm

We consider the problem of solving linear programming problems in the form

max z t x subject to Ax ≤ y (1.6)
using the simplex algorithm, introduced in 1947 by Dantzig [18]. This algorithm is known to work well in practice, even if its number of steps can be exponential in the dimensions of the matrix A [START_REF] Klee | How Good is the Simplex Algorithm?[END_REF]. Spielman and Teng [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF] investigate the case of arbitrary data noised with small Gaussian noise.

The Simplex Algorithm. The basic idea of the simplex algorithm is to walk over the vertices of the polytope defined by the constrains, so that the objective function z t x is increasing at each step. If there is a solution to the linear problem, then the algorithm will stop at one vertex of the polytope, which will be the optimal solution for the objective function. At each step, the algorithm has to take a decision in order to choose the next vertex. There are several methods to do that, but the one considered in [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF] is called the Shadow Vertex Method.

The Shadow Vertex Method. The Shadow Vertex Method consists on projecting the polytope defined by the inequalities of Problem (1.6) onto a plane spanned by the objective function z and another objective function t, such that we know a vertex x of the polytope that optimizes t. This projection (which is a polygon) is called the shadow.

We start from the image of x on the shadow, and we walk along the vertices of the shadow, until we reach the vertex whose pre-image vertex on the polytope optimizes the objective function z. As we are only walking on the vertices that are the vertices of the shadow, the running time of this method will depends on the size of the shadow.

Shadow of a polytope

Smoothed Complexity. Spielman and Teng computed the expected running time of the simplex algorithm (with a shadow vertex pivot) for linear programing problems in the form

max z t x subject to (A + G) i , x ≤ (y + h) i for 1 ≤ i ≤ n (1.7)
with G and h be a matrix and a vector of independant Gaussian random variables with mean 0 and standard deviation σ max i (y i , a i ) .

Theorem 3 (Spielman, Teng [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF]).

Let n > d ≥ 3, σ > 0, A ∈ R n×d and z ∈ R d .
The expected number of steps for the simplex algorithm to solve the problem (1.7) is at most polynomial in n, d and 1 σ . Thus, the Simplex algorithm has a polynomial smoothed complexity for Gaussian perturbations.

Outline of the Proof. The first step of the proof is to show that if z and t are independent (non random) vectors, then we can bound the expected size of the shadow of the polytope defined by the noised inequalities of Problem (1.7), projected on the plane spanned by z and t.

Note that in this case, z and t are fixed and do not depend on the data. For the Shadow Vertex Method, this will not be the case, so the first step cannot be applied straightforwardly. The second part of the proof consists of dealing with this issue, using the first part as a black box.

Smoothed Analysis of the Gaussian Elimination

One of the first other result of smoothed analysis has been performed by Sankar, Spielman and Teng [START_REF] Sankar | Smoothed analysis of the condition numbers and growth factors of matrices[END_REF]. Let Ā an n × n matrix, let A be a random Gaussian perturbation of Ā.

They consider the problem of solving the linear system Ax = y by Gaussian elimination with a final accuracy of b bits, and compute the expected number of bits needed during the elimination. The worst-case is O(bn) bits of precision [START_REF] Grotschel | Geometric Algorithms and Combinatorial Optimization[END_REF], and we can construct examples that produce large entries [START_REF] Trefethen | III. Numerical Linear Algebra[END_REF]. However, in practice, the Gaussian elimination does not usually require more than a double precision. For example, the lapack library uses only 64 bits of precision [4]. The authors proved that the expected number of bits of precision to solve the perturbed linear system Ax = y is only O(b + ln n):

Theorem 4 (Sankar, Spielman, Teng [START_REF] Sankar | Smoothed analysis of the condition numbers and growth factors of matrices[END_REF]). For n > e 4 , let Ā be an n × n matrix with Ā 2 ≤ 1. Let A = Ā + G with G i,j ∼ N (0, σ 2 ), with σ 2 ≤ 1 4 . Then, the expected number of bits of precision necessary to solve Ax = y to b bits of accuracy using Gaussian elimination without pivoting is at most

b + 11 2 log 2 n + 3 log 2 1 σ + log 2 (1 + 2 √ nσ) + 1 2 log 2 log 2 n + 6.83
Outline of the Proof. The strategy is to use the result of Wilkinson [START_REF] Wilkinson | Error analysis of direct methods of matrix inversion[END_REF], which states that the number of necessary bits is

b + log 2 (5nκ(A)ρ U (A) + 3),
where:

• LU is the LU -decomposition of A obtained without pivoting,

• κ(A) is the condition number of A, κ(A) = A 2 A -1 2 ,
• ρ U (A) is the growth factor of A in U :

ρ U (A) = U ∞ A ∞ , • ρ L (A) is the growth factor of A in L: ρ(L) = L ∞ .
It remains to show that with high probability, the condition number and the growth factors small when A is a perturbed matrix.

Application: A Robust Algorithm for Linear System. The above result can lead to an algorithm that solves efficiently a linear system [START_REF] Aho | Complexity theory[END_REF]. Given a matrix Ā, add a Gaussian perturbation with a well chosen standard deviation. Then, solve the perturbed linear system with a well chosen precision. Then, with probability as close to 1 as you want, the perturbed solution will be a solution of the original linear system with an accuracy of b bits:

Theorem 5 (Sankar, Spielman, Teng [START_REF] Aho | Complexity theory[END_REF]). Let Ā be an n × n matrix and y ∈ R n .

Let A be the perturbed version of Ā with Gaussian noise of standard deviation

δ 2 b+3 n 1 2 κ(A) -1
. Let's solve the perturbed system Ax = y using Gaussian elim-ination without pivoting, with 4b + 10 ln n + 3 ln κ(A) + 5 ln 1 δ + 7 bits of precision. Then, with probability at least 1δ, the obtained solution is a solution of Āx = y accurate to b bits.

Smoothed Analysis of the k-means Algorithm

Let X be a set of n points in R d . Given a parameter k, the k-clustering problem consists of finding a partition of X into k clusters C 1 , . . . , C k such that every point is "close" to the centroid of its cluster. More formally, an optimal solution would be to find the set of cluster C opt such that

C opt = arg min C={C 1 ,...,C k } ∪ k i=1 C i =X φ(C, X ), φ(C, X ) = k i=1 x∈X ∩C i x -µ i 2 (1.8)
where µ i is the centroid of the cluster C i . This problem is known to be NP-hard [2,[START_REF] Mahajan | The planar k-means problem is np-hard[END_REF], even if k or d is fixed (but if both k and d are fixed, the problem can be solved in polynomial time [START_REF] Inaba | Applications of weighted voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)[END_REF]). The k-means algorithm is a well used iterative heuristic algorithm to solve this problem, even if the optimal solution is not guaranteed. This algorithm is said to be efficient in practice, but the number of iterations, in the worst-case, is exponential in n [START_REF] Vattani | k-means requires exponentially many iterations even in the plane[END_REF]. Thus, this algorithm is a good candidate for the smoothed analysis.

An example of clustering with k = 3

Algorithm. The basic idea of the algorithm is to start from an arbitrary clustering, and then try to modify it so that it decreases the potential function φ of Equation (1.8). Once the potential cannot be decreased anymore, the algorithm stops.

1. Select k points c 1 , . . . , c k arbitrary in R d . 2. x ∈ X is in C i if for all j = i, x -c i < x -c j 3. c i := 1 card C i x∈C i x 4.
If the c i 's or the clusters have changed, goto 2, otherwise return C 1 , . . . , C k .

Smoothed Analysis. Arthur, Manthey and Röglin [START_REF] Arthur | Smoothed analysis of the kmeans method[END_REF], performed a smoothed analysis on the k-means algorithm: Theorem 6 (Arthur, Manthey, Röglin [START_REF] Arthur | Smoothed analysis of the kmeans method[END_REF]). If the set of point X is noised by a Gaussian perturbation of mean 0 and standard deviation σ, then the expected number of iterations of the k-means algorithm is bounded by a polynomial in n, d and 1

σ . In other words, the smoothed complexity is polynomial.

Outline of the Proof. The idea of the proof is to have a look on how much the potential function of Equation (1.8) decreases in every sequence of a few consecutive iterations. The authors proved that the minimal improvement appears only with a very small probability.

The main insight is to encode each possible iteration in a transition blueprint. A transition blueprint is basically a graph2 where each vertex corresponds to a cluster, and each oriented edge between two clusters corresponds to a point that moves from a cluster to another one. Then, the transition blueprints are classified with only six possible cases (a general case and five special cases that do not fit in the general one), according to some of their combinatorial properties. The main challenge is then, under these combinatorial assumptions, to bound the probability of the smallest improvement to be small.

Smoothed Analysis of Geometric Structures

Smoothed Analysis of Visibility Map of Realistic Terrains

A terrain is a surface obtained by, given a triangulation in the plane, assigning to each vertices an elevation. This geometric structure can be used to model moutainous regions. Let T be a terrain of n triangles, and p be a viewing point. The visibility map of T from p is the projection of the triangles of T , visible from p, onto a plane. We define the complexity of the visibility map as the number of vertices of the visibility map from p (such vertices can be vertices or edge intersection in T ). In the worst case, this complexity is known to be quadratic. However, in practice, the complexity seems to be close to linear.

Credits: GeoSolutions, Inc.

de Berg, Haverkort and Tsirogiannis [START_REF] Berg | Visibility maps of realistic terrains have linear smoothed complexity[END_REF] showed that the smoothed complexity of visibility maps, under some random uniform perturbation of the vertices elevation:

Theorem 7 (de Berg, Haverkort, Tsirogiannis [START_REF] Berg | Visibility maps of realistic terrains have linear smoothed complexity[END_REF]). Let T be a terrain of n triangles. Then, a visibility map of T under perspective projection has smoothed complexity

O tan θ c + 1 sin φ σn
under the addition of noise to each vertex's elevation that is uniformly distributed in an interval [-c, c], where:

• The fatness φ > 0 is the smallest angle in the triangles of the underlying triangulation;

• The steepness θ < π 2 is the largest dihedral angle between any triangle and the horizontal plane,

• The scale factor σ ≥ 1 is the length of the longest edge divided by the length of the shortest edge of the triangulation;

• The constant c is a fixed constant fraction of the minimum edge length of the triangulation.

If we assume the fatness, the steepness and the scale factor to be constant in n, the smoothed complexity of visibility maps is linear. These assumptions on the terrain are used in several contexts and seem to be experimentally realistic. However, they are not sufficient, alone, to explain the linear behavior in practice, since the worst-case of visibility maps of realistic terrains is still Θ(n √ n).

Outline of the Proof. The number of terrain vertices is already O(n), so it remains to compute the expected number of visible edge-intersections. Take two edges e and f of T that do not share a vertex (otherwise these edges cannot intersect). A first step is to bound the probability, by perturbing e, that e creates a visible intersection with f . This probability can be bounded by some local geometric constants. Then, the authors deduced that the expected number of visible intersections with e can be bounded as well. Summing up and bounding the local constants by the global ones θ, σ and φ give the result.

Smoothed Analysis of the Number of Extremal Points

Let p * 1 , . . . , p * n be n points chosen in a d-dimensional hypercube. Let p 1 , . . . , p n be the noisy version of the point set under some random distribution and compute the expected size of the convex hull of the noisy points. The problem seems to be similar to Section 1.1.2, however in this case the points are not identically distributed: the mean value of p i is p * i . In other words, this corresponds to the smoothed complexity of the convex hulls.

In the worst case, the number of vertices of a convex hull of n points in R d is

Θ n ⌈ d 2 ⌉
, and the average-case corresponds to Section 1.1.2. Damerow and Sohler [START_REF] Damerow | Extreme points under random noise[END_REF] computed an upper-bound of the expected number of vertices of the convex hull (called extremal points) for Gaussian perturbations and uniform perturbations in a cube. They proceed by bounding the expected number of maximal points (a point is maximal if each of its orthants contains no points). Since every extremal point is maximal, their bound is also valid for the expected number of extremal points.

Theorem 8 (Damerow, Sohler [START_REF] Damerow | Extreme points under random noise[END_REF]). Let P * = {p * 1 , . . . , p * n } be a set of n points of R d for fixed dimension d, in the d-dimensional unit hypercube. Let P = {p 1 , . . . , p n } its noisy version under some noise distribution ∆.

• if ∆ is the d-dimensional Gaussian distribution with standard deviation σ, then the expected number maximal points is

O 1 σ d ln 3/2•d-1 n ,
• if ∆ is the uniform distribution in a hypercube of side length ε, then the expected number of maximal points is

O n ln n ε d d+1
.

Outline of the Proof. First, the authors compute the average number of maximal points if the points are chosen according to the distribution ∆. Under some assumption on ∆ (which are valid for the one considered in the final theorem), they proved that the average complexity is O ln d-1 n . Now, fix a parameter δ, and split the unit hypercube into 1 δ d smaller hypercubes of size δ. For each small hypercube C j , we consider the points (p * i ) C j that are in C j , and compute the expected number of maximal points of (p j ) C j δ For each cell Cj, we consider the initial points in Cj (in black) and their noisy version (in red).

The main idea is that if δ is small enough, then the points (p i ) C j will behave almost like in the average-case. Summing up the maximal points of all the C j gives an upper bound of the total number of maximal points. This idea, summerized in a lemma, can be applied for the two considered distributions. Let P * be a finite set of points in R d and consider a random perturbation P = {p * + η(p * ) : p * ∈ P * } where each point p * is moved by some random vector η(p * ), typically chosen independently. We are interested in the asymptotic behavior of the expected number of faces (of all dimensions) of the convex hull of P , as a function of the number n of points and some parameter that describes the amplitude of the perturbations.

Formally, the smoothed complexity of convex hulls relative to a probability distribution µ on R d is defined as

S(n, µ) = max p * 1 ,p * 2 ,...,p * n ∈R d diam{p * 1 ,p * 2 ,...,p * n }≤1 E [card CH ({p * 1 + η 1 , p * 2 + η 2 , . . . , p * n + η n })]
where diam denotes the diameter, card S denotes the cardinality of a set S, CH(X) denotes the set of faces, of all dimensions, of the convex hull of X, and η 1 , η 2 , . . . , η n 19 are random variables chosen independently from the distribution µ.We present upper and lower bounds on S(n, U δB ), where U δB is the uniform distribution on the ball of radius δ centered in the origin in R d , and S(n, N (0, σ 2 I 2 )), where N (0, σ 2 I 2 ) is the Gaussian distribution centered in the origin and with covariance matrix σ 2 I 2 .

New Results

Our main results are a technique to analyze random geometric hypergraphs, which we call the witness-collector technique, as well as its application to the analysis of the smoothed complexity of convex hulls. Before we spell them out we need to clarify some terminology.

Random Geometric Hypergraphs. Let X be a set, (X , R) a range space (i.e. R is a family of subsets (ranges) of X ) and P a finite set of random elements of X . The random geometric hypergraph induced by (X , R) on P is the set H = {P ∩ r : r ∈ R}; that is, a subset Q ⊂ P is a hyperedge of H if and only if there exists r ∈ R such that r ∩ P = Q. Our analyses of random convex hulls proceed by analyzing random geometric hypergraphs where X = R d , R is the set of all half-spaces of R d , and the elements of P are chosen independently (but not identically distributed!). Any face of the convex hull of P is a hyperedge of H, but the converse is not true. It turns out, however, that the average size of H is close enough to that of CH(P ) that our technique yields meaningful upper and lower bounds on the smoothed complexity of convex hulls (cf. Section 2.2.3).

Notations for Orders of Magnitude. Our goal is to understand how the order of magnitude of the smoothed complexity depends on the number n of points and the amplitude δ or σ of the perturbation. For the sake of the presentation, we do not keep track in our analyses of additive or multiplicative constants depending on fixed quantities such as the dimension of the space. Throughout the chapter, we therefore write a = O(b), a = Ω(b) and a = Θ(b) to mean that there exist positive reals c and c ′ such that, respectively, a ≤ cb, a ≥ cb and cb ≤ a ≤ c ′ b; we also use Θ(b) (and similarly for O() and Ω()) as a shorthand for a quantity x for which x = Θ(b) holds. These notations do not carry any asymptotic meaning (since several variables may assume large and unrelated values); when used without stating any condition on n, σ or δ, these notations mean inequalities that hold for any n ≥ d + 1, δ > 0 and σ > 0.

The Witness-Collector Technique. Let (X , R) denote a range space. Our analyses are based on the following notion: Definition 9. A system of witnesses and collectors for a covering

R 1 ∪R 2 ∪. . .∪R m of R is a family {(W j i , C j i )}1≤i≤m
1≤j≤ℓ of pairs of subsets of X such that (a) for all i, j, any r ∈ R i contains W j i or is contained in C j i , (b) for all i, W 1 i ⊆ W 2 i ⊆ . . . ⊆ W ℓ i , (c) for all i, j, W j i ⊆ C j i . We denote by H (k) the set of hyperedges of cardinality k of a hypergraph H. Our analyses are based on the following theorem, which we prove in Section 2.2: Theorem 10. Let (X , R) be a range space, let P be a set of n random elements of X chosen independently and let H denote the hypergraph induced by R on P .

(i) If {(W j i , C j i )}1≤i≤m 1≤j≤ln 2 n
is a system of witnesses and collectors for a covering

R 1 ∪ R 2 ∪ . . . ∪ R m of R such that W j i ∩ P and C j i ∩ P have average size Ω(j) and O(j) respectively then E card H (k) = O(m).
(ii) If every element of H (1) is in at least one element of H (k) , and

{W 1 i } 1≤i≤m is a family of disjoint subsets of X such that E card W 1 i ∩ H (1) = Ω(1) then E card H (k) = Ω(m).
In several of our applications we first construct a system {(W j i , C j i )} of witnesses and collectors satisfying the assumptions of Theorem 10 (i), then use a subfamily of the W 1 i 's that are disjoint to apply Theorem 10 (ii).

Applications. We present, in Sections 2. We also analyze the convex hull of perturbations of points in convex position and delineate the main regimes in terms of the number of points and the amplitude of the perturbation; this provides lower-bounds on the Euclidean and Gaussian smoothed complexities of convex hulls.

Large Perturbations. We show that for δ = Ω n 2 d+1 the smoothed complexity of convex hulls relative to U δB is of the same order of magnitude as the expected complexity of the convex hull of random points chosen i.i.d. from U δB , the classical model of random polytope. Our smoothed complexity upper bound also implies a similar result for Gaussian perturbation with σ = Ω(1).

Simple Analysis of Classical Random Polytopes. The classical model of random polytopes corresponds to the case where all points of p * i coincide. There, our systems of witnesses and collectors yield the order of magnitude of the expected number of faces with considerably less effort than earlier analyses.

A Surprising Phenomenon. We observed experimentally (Figure 2.2c) that the expected size of the convex hull of perturbations of points in convex position consistently decreases with the amplitude of the noise in the Gaussian model, whereas some non-monotonicity appears in the Euclidean model. Our analyses of perturbations of points in convex position provide a theoretical confirmation of this difference in behaviours (see Figures 2.1b and 2.2a).

As evidence that the witness-collector technique is relevant for the study of other geometric hypergraphs, we outline a design of witnesses and collectors that yields the order of magnitude of the number of faces in the Delaunay triangulations of a set of random points chosen uniformly and independently from the unit ball (Theorem 22); again, this is a well-known result but the proof (only sketched here) is considerably shorter than the original one.

Related Works

The results presented here appeared in preliminary form in research reports [START_REF] Attali | The Effect of Noise on the Number of Extreme Points[END_REF][START_REF] Devillers | Complexity analysis of random geometric structures made simpler[END_REF] and proceedings of conferences [START_REF] Devillers | Complexity analysis of random geometric structures made simpler[END_REF][START_REF] Devillers | On the smoothed complexity of convex hulls[END_REF]. Note that the shift from static to adaptative witness-collectors in Section 2.2.2 is based on an idea which we learned from [START_REF] Glisse | Silhouette of a random polytope[END_REF] and systematize here. We briefly position our results with respect to prominent related previous work.

Smoothed Number of Maximal Points. The only previous bound on the smoothed complexity of convex hulls is due to Damerow and Sohler [START_REF] Damerow | Extreme points under random noise[END_REF], see Section 1.3.2.

They study the number of maximal points under Gaussian and ℓ ∞ perturbations (we included the results for the Gaussian case in Figures 2.1d and 2.2b). Their technique requires that the perturbation acts independently on each coordinate (thus restricting possible perturbations) so that the analysis of point dominance reduces to considerations on independent random permutations. The number of maximal points bounds from above the number of extreme points, but in probabilistic setting these two quantities typically have different orders of magnitude. As a consequence, the upper bounds are not sharp and there is no lower bound. One may expect that when the magnitude of the perturbations is sufficiently large compared to the scale of the initial input, the initial position of the points does not matter and smoothed complexity is subsumed by some average-case analysis (up to constant multiplicative factors). The main insight of Damerow and Sohler [START_REF] Damerow | Extreme points under random noise[END_REF] is a quantitative version of this claim. Specifically, they show that if n points from a region of diameter r are perturbed by a Gaussian noise of standard deviation Ω(r √ ln n) or a ℓ ∞ noise of amplitude Ω(r 3 n/ ln n) then the expected number of maximal points is the same as in the average-case analysis. A smoothed

any d Range of δ 0, n 2 d+1 -1 d-1 ⌊ d 2 ⌋ n 2 d+1 -1 d-1 ⌊ d 2 ⌋ , 1 1, 3n 2 d+1 3n 2 d+1 , +∞ S(n, U δB ) O n ⌊ d 2 ⌋ O n 2 d-1 d+1 δ -(d-1) O n 2 d-1 d+1 Θ n d-1 d+1 any d E card H (1) = O n d-1 d+1 + δ -2d d+1 n 1+2 d-1 (d+1) 2 d = 2 Range of δ [0, 1 √ n ] [ 1 √ n , 1] [1, n 5/12 ] [n 5/12 , n 2/3 ] [n 2/3 , +∞] S(n, U δB ) O(n) O δ -2 3 n 2 3 O n 2/3 O δ -4 3 n 11 9
O n 1/3

(a) Upper bounds on the smoothed complexity relative to Euclidean perturbations (Theorem 13 and Corollary 14).

Range of δ 0 ≤ δ ≤ n 2 1-d n 2 1-d ≤ δ ≤ 1 1 ≤ δ ≤ n 2 d+1 n 2 d+1 ≤ δ E [card CH(P )] Θ(n) Θ n d-1 2d δ 1-d 2 4d Θ n d-1 2d δ (1-d) 2 4d Θ n d-1 d+1
(b) Expected complexity of a Euclidean perturbation P of a regular sample of the unit sphere in R d (Theorem 15). This gives a lower bound on the smoothed complexity for Euclidean perturbation.

any d d = 2 δ ≥ δ 0 ⇒ average-case behavior δ 0 = O n 2 d+1 δ 0 = O n 2/3
(c) Amplitude of a Euclidean perturbation for which the smoothed complexity behaves as the averagecase complexity (Lemma 2.3.8).

Our bounds (d = 2)

Previous bound [START_REF] Damerow | Extreme points under random noise[END_REF] a σ ≥ σ 0 ⇒ average-case behavior

σ 0 = O (1) σ 0 = O √ ln n S(n, N (0, σ 2 I 2 )) O √ ln n + σ -1 √ ln n O ln n + σ -2 ln 2 n
(d) Upper bounds for Gaussian perturbations (Theorem 18).

a This bound applies to maximal point, cf. the comparison to earlier work. (a) A comparison of our smoothed complexity bound for Euclidean perturbation (Theorem 13 and Corollary 14) and two lower bounds, where the initial points are placed respectively at the vertices of a unit-size n-gon (Theorem 15) and in the origin. A data point with coordinates (x, y) means that for a perturbation with δ of magnitude n x the expected size of the convex hull grows as n y , subpolynomial terms being ignored. The worst-case bound is given as a reference. The constants in the O() and Ω() have been ignored as their influence vanishes as n → ∞ in this coordinate system.

Range of σ

0 ≤ σ ≤ 1 n 2 1 n 2 ≤ σ ≤ 2 ln 4 n n 2 2 ln 4 n n 2 ≤ σ ≤ 1 √ ln n 1 √ ln n ≤ σ E [card CH(P )] Θ(n) O(n), Ω 4 √ ln(n √ σ) √ σ Θ 4 √ ln(n √ σ) √ σ Θ √ ln n (
- [START_REF] Damerow | Extreme points under random noise[END_REF]) and the lower bound perturbing the regular n-gon (Theorem 19). A data point with coordinates (x, y) means that for a perturbation of magnitude σ = ln x n the expected size of the convex hull grows as ln y n. complexity bound then follows by a simple rescaling argument: split the input domain into cells of size r = O(σ/ √ ln n), assume that each cell contains all of the initial point set, and charge each of them with the average-case bound.

1 2 1 2 0 1 2 1
Our technique yields a similar subsuming of the smoothed complexity analysis by the average-case analysis for the number of faces (Lemma 2.4.5) with the same threshold, thus extending Damerow and Sohler's main insight; we also obtain a similar statement in the Euclidean model (Lemma 2.3.8). The smoothed complexity bound we obtain by the rescaling argument (Corollary 17) is better than the one of Damerow and Sohler because the average number of extreme points is asymptotically smaller than the number of maximal points. It should be noted that the rescaling argument only applies to bound the number of vertices of the convex hull since faces of higher dimension may come from more than one cell; in any case, we further improve the bound obtained from the rescaling argument by a more direct analysis that accounts for faces of arbitrary dimension (Theorem 18).

Smoothed Complexity of a Simplex Algorithm. A substantial literature in the analysis of algorithms was devoted to explain the very good practical performance of the simplex algorithm, given that most of the pivoting rules had exponential worst-case complexity. This motivated the study of various models of random polytopes, and eventually the introduction of the smoothed complexity analysis model by Spielman and Teng [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF]. We encourage the interested reader to consult their discussion of earlier literature, and simply compare our work to the smoothed complexity bound for convex hulls that is at the core of their analysis of the shadowvertex pivot rule. As seen on Section 1.2.2, they estimate the expected number of vertices of an arbitrary two-dimensional projection of a polytope given as an intersection of n halfspaces in d dimensions and perturbed by a Gaussian noise of standard deviation σ using techniques quite different from ours, see [START_REF] Spielman | Smoothed analysis: Why the simplex algorithm usually takes polynomial time[END_REF]Th 4.1]. Neither n nor d are fixed, so the number of vertices may be exponential in the input; their analysis shows that it is polynomial in n, d and 1

σ . The question we consider is therefore, from the point of view of the model, of a rather different nature: we consider the dimension to be fixed rather than variable, specify the polytope as a convex hull of vertices rather than intersection of half-spaces, and estimate the number of faces rather than the two-dimensional silhouettes. More importantly, our intent is to understand a transition within the polynomial domain rather than identify a polynomial behavior in place of an exponential worst-case bound.

Floating Bodies and Economic Cap Coverings. As seen on Section 1.1.2, Bárány and Larman [START_REF] Bárány | Convex bodies, economic cap coverings, random polytopes[END_REF] established that the expected number of faces of the convex hull of n random points chosen uniformly from a convex body K is Θ nK 1 n , where K(t) denotes the volume of the wet part of K with parameter t: the union of the intersections of K with a half-space that intersects it with volume at most t. This connection allowed them to transfer to the study of random polytopes various results from convex geometry, for which wet parts, or their complements the floating bodies, are classical objects.

When the ranges are half-spaces in R d , our systems of witnesses and collectors are essentially equivalent to the economic cap covers on which Bárány and Larman's proof is based (Bárány and Vu [10, § 5] also use the same idea in the proving of a central limit theorems for Gaussian polytopes). A first difference is that the analogue of our Condition (a) for economic cap covers is formulated in terms of wet parts, so the role of the range space is implicit. This has little effect as far as the ranges are half-spaces, but we note that the analogue of wet parts for other range spaces is not straightforward to define and study, whereas our presentation naturally extends to other range spaces (as the case of Delaunay triangulation sketched in Section 2.5 demonstrates). We also note that the constructions of systems of witnesses and collectors differ from the constructions of economic cap covers, but believe that this is a less essential distinction.

Witnesses and Collectors

In this section we first explain the idea behind Theorem 10 in a simpler setting in Section 2.2.1, then prove Theorem 10 in Section 2.2.2, then clarify its use for the analysis of convex hulls of random point sets in Section 2.2.3. Let (X , R) be a range space, P a random set of n elements of X chosen independently, H the hypergraph induced by R on P , and

Principle

k ∈ N. Let R 1 ∪ R 2 ∪ . . . ∪ R m be a covering of R and {(W 1 i , C 1 i )} 1≤i≤m
a system of witnesses and collectors for that covering. Since ℓ = 1, we shorten

W 1 i into W i and C 1 i into C i and note that Condition (b) is trivial. Conditioning on Loaded Witnesses. If card (W i ∩ P ) is at least k then Condi- tion (a) ensures that every hyperedge of size k in {r ∩ P : r ∈ R i } is contained in C i ,
so there are at most E card (C i ∩ P ) k such hyperedges; otherwise we can use the trivial upper bound n k . Conditioning on the event that card (W i ∩ P ) is at least k for all i we therefore get

E card H (k) ≤ P [∃i, card (W i ∩ P ) < k] n k + P [∀i, card (W i ∩ P ) ≥ k] • m i=1 E card (C i ∩ P ) k so if the witnesses are chosen so that card (W i ∩ P ) ≥ k with probability 1 - O(n -k ), E card H (k) = O m i=1 P [card (W i ∩ P ) < k] • n k + P [∀i, card (W i ∩ P ) ≥ k] • m i=1 E card (C i ∩ P ) k = O m + m i=1 E card (C i ∩ P ) k . (2.

1)

Role of W i ∩ P and C i ∩ P. Chernoff's multiplicative bound implies that if W i ∩ P has average size Ω(k ln n) then indeed card (W i ∩ P ) ≥ k with probability 1 -O(n -k ). More generally:

Lemma 2.2.1. Let P be a set of random elements of X chosen independently and W a subset of X . (a)

P [W ∩ P = ∅] ≤ e -E[card(W ∩P )] . (b) If E [card (W ∩ P )] ≥ k + 1 then P [card (W ∩ P ) < k] ≤ e -Ω(E[card(W ∩P )]) .
(We defer the proof to Section 2.2.

[V ] ≥ 1 then E V k = O E [V ] k .
(Again, the proof is postponed to Section 2.2.4.) In the situations we consider, one can construct witnesses and collectors such that W i ∩ P and C i ∩ P both have expected size Θ(k ln n); see [START_REF] Devillers | Complexity analysis of random geometric structures made simpler[END_REF] for several examples. Equation (2.1) and Lemma 2.2.2 then yield that E card H (k) is of order m up to some logarithmic factors.

Shaving Log Factors. The use of a Chernoff bound to control the probability that witnesses contain fewer than k elements increases the expected size of the W i ∩P so that all of them are large for most realizations of P . By Condition (c), W i ⊆ C i , so this also overloads the collectors, resulting in the extra log factors. The idea that leads to the sharper bounds of Theorem 10, which we learned from [START_REF] Glisse | Silhouette of a random polytope[END_REF], is to make W i and C i random variables depending on P . By adapting the witness-collector pairs used in the analysis to each realization of P , very few collectors will need to be large, and their contribution to the total will remain negligible.

It is perhaps worth pointing out that the above analysis holds for several of our constructions when only the first layer (j = 1) of witnesses and collectors is considered. Our proofs can therefore be further simplified should one not care about some extra logarithmic factors.

Proof of Theorem 10: Adaptative Witnesses and Collectors

We first prove the upper bound, in a format that will allow slightly more flexibility. Lemma 2.2.3. Let (X , R) be a range space, let P be a set of n random elements of X chosen independently and let H denote the hypergraph induced by R on

P . If R 1 ∪ R 2 ∪ . . . ∪ R m is a covering of R and {(W j i , C j i )}1≤i≤m 1≤j≤ln 2 n
is a system of witnesses and collectors for that covering with

P card W j i ∩ P < k = O e -Ω(j) and E card C j i ∩ P = O(j) then E card H (k) is O(m).
Proof. Let i ∈ {1, 2, . . . , m}. We let d i denote the smallest j such that W j i contains at least k points and C i = C d i i , or, if no such W j i exists, d i = ∞ and C i = X . (So d i and C i are random variables depending on P .) By Condition (a) and the definition of d i , every hyperedge of H of size k induced by R i is contained in C i so:

E card H (k) ≤ m i=1 E card (C i ∩ P ) k . (2.2)
Moreover, by Condition (b) we have

P [d i ≥ j] = P card W j i ∩ P < k = O e -Ω(j) . We claim that E card C j i ∩ P | d i ≥ j ≤ E card C j i ∩ P + k = O(j). (2.3)
Indeed, working with the complement Cj

i of C j i , E card Cj i ∩ P = p∈P P p / ∈ C j i .
For any T ⊂ P we have

E card Cj i ∩ P | W j i ∩ P = T = p∈P \T P p / ∈ C j i | p / ∈ W j i ≥ p∈P \T P p / ∈ C j i ,
the last inequality following from Condition (c). Thus,

E card Cj i ∩ P ≤ E card Cj i ∩ P | W j i ∩ P = T + card T.
By Condition (b), d i ≥ j if and only if card W j-1 i ∩ P < k. Total probabilities let us decompose this event:

E[ card Cj i ∩ P | d i ≥ j] = T :card T <k E card Cj i ∩ P | W j-1 i ∩ P = T P W j-1 i ∩ P = T | card W j-1 i ∩ P < k ≥ E card Cj i ∩ P -k T :card T <k P W j-1 i ∩ P = T | card W j-1 i ∩ P < k = E card Cj i ∩ P -k
Moving back to the complement yields Inequation (2.3). Now, since P has n points in total, conditioning on the value of d i we obtain

E [card (C i ∩ P )] = ln 2 n j=1 E card C j i ∩ P • 1 d i =j + E [n • 1 d i =∞ ] ≤ ln 2 n j=1 E card C j i ∩ P • 1 d i ≥j + E [n • 1 d i =∞ ] = ln 2 n j=1 E card C j i ∩ P | d i ≥ j P [d i ≥ j] +n • P [d i = ∞] = ln 2 n j=1 O je -Ω(j) + O ne -Ω(ln 2 n)
so each collector C i contains on average a constant number of elements of P . Lemma 2.2.2 and Equation (2.2) imply that E card

H (k) = O(m).
We now wrap-up the proof of our witness-collector theorem.

Proof of Theorem 10. Since E card W j i ∩ P = Ω(j), there exists some constant c > 0 such that E card W j i ∩ P ≥ cj. For j ≥ k+1 c , the Chernoff bound of Lemma 2.2.1 (b) thus ensures that P card W j i ∩ P < k is at most e -Ω(j) . Bounding that probability from above by 1 in the cases j < k+1 c we get that P card W j i ∩ P < k is O e -Ω(j) . Statement (i) then follows readily from Lemma 2.2.3. Now consider Statement (ii). We can charge each element of H (1) to an element of H (k) that contains it. Since each element of H (k) is charged at most k times, we have card H (k) ≥ 1 k card H (1) . The assumptions ensure that each W 1 i contains on average Ω(1) elements of H (1) and that these elements are distinct. It follows that E card H (1) and E card H (k) are Ω(m).

The Special Case of Convex Hulls

Unless indicated otherwise, in the remainder of this chapter the range space (X , R) considered is that of half-spaces in R d , where d is a constant. Every element of H (1) belongs to some element of H (k) , so the first condition of Theorem 10 (ii) holds for this range space.

In this setting, the elements of H (k) are also called the k-sets of the point set P . The bounds that we establish are expressed with O(), Ω() and Θ() in which the multiplicative constants depend on k; they are therefore valid for any fixed k.

For k ≤ d, any (k -1)-dimensional face of CH(P ) is a k-set, so the upper bound of Theorem 10 (i) applies to the size of the convex hull. The reverse is not true (cf. the figure on the right) but we remark that H (1) is exactly the set of vertices of CH(P ) and that every element of H (1) belongs to an actual (k-1)-dimensional face of CH(P ); the proof of Statement (ii) of Theorem 10 therefore provides, mutatis mutandis, a lower bound on the number of (k -1)-dimensional faces of CH(P ). In the rest of the chapter, we will navigate without further justification between the convex hull of a random point set P and the associated random geometric hypergraph.

Proofs of Lemmas 2.2.1 and 2.2.2

Proof of Lemma 2.2.1. Let V i be the indicator function of the event that the i th point from P belongs to W . We write

V = V 1 + . . . + V n and let t = E [V ].
Chernoff's bound for lower tails yields that for any δ ∈ (0, 1)

P [V < (1 -δ)t] ≤ e -δ (1 -δ) 1-δ t = e -t(1-(1-δ)(1-ln(1-δ))) .
(2.4)

In particular,

P [V = 0] ≤ lim δ→1 P [V < (1 -δ)t] = lim δ→1 e -t(1-(1-δ)(1-ln(1-δ))) = e -t
which proves Statement (a). Moreover, for

1 -δ = k t , Equation (2.4) specializes into P [V < k] < e -t(1-k t (1-ln k t )) Since x → x(1 -ln x) is increasing on (0, 1), for t ≥ k + 1 we have 1 - k t 1 -ln k t ≥ 1 - k k + 1 1 -ln k k + 1 > 0
and Statement (b) follows.

Proof of Lemma 2.2.2. The statement is a special case of a classical inequality for sums of random variables [40, Th 2.12]; we give a simple, elementary, proof.

Expanding V k = ( n i=1 V i ) k we obtain E V k = 1≤i 1 ,i 2 ...i k ≤n E [V i 1 • V i 2 . . . V i k ] = k ℓ=1 1≤i 1 ,i 2 ...i k ≤n |{i 1 ,i 2 ...i k }|=ℓ E [V i 1 • V i 2 . . . V i k ] .
Since the V i 's have values in {0, 1}, for any positive integers a 1 , a 2 , . . . a t and i

1 , i 2 , . . . i t E V a 1 i 1 • V a 2 i 2 . . . V at it = E [V i 1 • V i 2 . . . V it ] .
Letting p(ℓ, k) denote the number of partition of {1, 2, . . . , k} in ℓ subsets, we can thus write

E V k = k ℓ=1 1≤i 1 ,i 2 ...i ℓ ≤n ia =i b if a =b p(ℓ, k) E [V i 1 • V i 2 . . . V i ℓ ] .
Since V i and V j are independent if i = j the previous identity rewrites as

E V k = k ℓ=1     p(ℓ, k) 1≤i 1 ,i 2 ...i ℓ ≤n ia =i b if a =b E [V i 1 ] • E [V i 2 ] . . . E [V i ℓ ]     .
Thus,

E V k ≤ k ℓ=1 p(ℓ, k) 1≤i 1 ,i 2 ...i ℓ ≤n E [V i 1 ] • E [V i 2 ] . . . E [V i ℓ ]
and since

1≤j 1 ,j 2 ,...,j ℓ ≤n E [V j 1 ] • E [V j 2 ] . . . E [V j ℓ ] = n i=1 E [V i ] ℓ = E [V ] ℓ
we finally obtain that

E V k ≤ k ℓ=1 p(ℓ, k) E [V ] ℓ ≤ k ℓ=1 p(ℓ, k) E [V ] k
the last inequality following from the fact that E [V ] ≥ 1.

Euclidean Perturbation

We first consider the complexity of convex hulls of points perturbed under Euclidean perturbations.

f (λt, δ) = ν d-1 λt 0 2xδ -x 2 d-1 2 dx = ν d-1 t 0 λ d-1 2 2xδ -λx 2 d-1 2 λdx ≤ ν d-1 t 0 λ d+1 2 2xδ -x 2 d-1 2 dx = λ d+1 2 f (t, δ)
which proves the claim. The case λt > 2δ then follows easily:

f (λt, δ) = vol d (δB) = f 2δ t t, δ ≤ 2δ t d+1 2 f (t, δ) ≤ λ d+1 2 f (t, δ). Claim 2.3.2. For t ∈ [0, δ], f (t, δ) = Θ t d+1 2 δ d-1 2 . ν t cone cylinder δB W Proof.
Let W be a half-space that intersects δB with depth t and let ν = (∂W ) ∩ δB. The region W ∩ δB is sandwiched between a cone and a right cylinder with heights t and bases ν, with respective volumes t vol d-1 (ν)/d and t vol d-1 (ν). Since ν is a ball of radius r, with

r 2 = δ 2 -(δ -t) 2 = 2tδ -t 2 , it has (d -1)- dimensional volume Θ (tδ) d-1 2
and the claim follows.

Witness-Collector Construction

Our systems of witnesses and collectors for Euclidean perturbations are based on the construction summarized in the following figure.

h 1 h 4 h 2 ∂ρB W 2 1 H 2 ρB C j i H i W j i H 3 ranges in R i normals to H 1 W 1 1 W 4 1 W 3 1
Definition. Our construction is parameterized by a radius ρ, usually chosen so that the perturbed point set remains inside ρB, and a sequence of positive reals h 1 < h 2 < . . . < h ℓ . We let H 1 , H 2 , . . . H m be an inclusion-minimal cover of ∂(ρB) by half-spaces of intersection depth h 1 with ρB.

Claim 2.3.3. m = Θ (ρ/h 1 ) d-1 2 . Proof. If h 1 ≥ ρ then m ≤ 2 so assume h 1 < ρ. The intersection H i ∩ ∂(ρB) is a spherical cap with radius r = Θ √ h 1 ρ . Since the H i form a minimal cover of ∂(ρB), m = Θ vol d-1 (∂(ρB)) vol d-1 (∂(ρB) ∩ H i )
The statement then follows from the fact that vol d-1 (∂(ρB)) and vol d-1 (∂(ρB) ∩ W 1 i ) are, respectively, proportional to ρ d-1 and r d-1 . We then define the range R i as the set of half-spaces whose inner normal is parallel to a vector from the origin to a point of H i ∩∂(ρB). We define W j i as the intersection of ρB with the half-space parallel to H i and with intersection depth h j with ρB. We define C j i as the union of the half-spaces of R i that do not contain

W j i . Lemma 2.3.4. R 1 ∪ R 2 ∪ . . . ∪ R m covers the set of half-spaces in R d and {(W j i , C j i )}1≤i≤m
1≤j≤ℓ is a system of witnesses and collectors for that covering. Moreover, a constant fraction of the W 1 i are pairwise disjoint. Proof. The definition readily ensures that the union of the R i is the set of all half-spaces and that Condition (a) holds. The monotonicity of the h i implies that Condition (b) is also satisfied. Let x ∈ W j i .If x ∈ ∂H i , then let H denote the half-space parallel to H i with x on its boundary. If x ∈ ∂H i , we have to tilt the plane slightly: let H be a half space in R i with x on its boundary but not parallel to H. In both cases H is in R i and does not contain W j i and thus x ∈ H ⊂ W j i and Condition (c) holds. As the cover of ∂ρB by {H i } i=1,2,...,m is inclusion-minimal, we can extract a family I ⊆ {1, 2, . . . , m} of size Ω(m) such that the {W 1 i } i∈I are pairwise disjoint.

In our analysis we will need some control over the intersection of C j i with ρB:

Claim 2.3.5. C j i ∩ ρB is contained in a half-space parallel to H i with intersection depth at most 9h j with ρB.

Proof. For any half-space H, the region H ∩ ρB is the convex hull of H ∩ ∂ρB. It follows that H ∈ R i does not contain W j i if and only if H ∩ ∂ρB does not contain W j i ∩∂ρB. This implies that for any H ∈ R i the spherical cap H ∩∂ρB is contained in a cap with same center as W j i ∩ ∂ρB and three times its radius. A half-space cutting out a cap of radius r x in ∂ρB intersects ρB with depth h x = Θ r 2 x ρ .

Tripling the radius of a cap thus multiplies the depth of intersection by 9, and the statement follows.

Claim 2.3.6. If E [card (W 1 i ∩ P )] = Ω(1) then E card W 1 i ∩ H (1) = Ω(1) Proof. If W 1
i ∩P is non-empty then W 1 i contains the point of P extreme in direction u i and W 1 i ∩ H (1) is therefore non-empty. We thus have

E card W 1 i ∩ H (1) ≥ P W j i ∩ H (1) = ∅ ≥ P W 1 i ∩ P = ∅ ≥ 1 -e -E[card(W 1 i ∩P )] = Ω(1),
the last inequality following from the Chernoff bound of Lemma 2.2.1 (a).

Warm-up: Average-Case Analysis Made Easy

As a first example, let us use a system of witnesses and collectors to give a short 1 proof of a classical result of Raynaud.

Theorem 11 (Raynaud [41]). Let d ≥ 2 be a constant and P = {p 1 , p 2 , . . . , p n } be a set of random points uniformly and independently distributed in a ball of R d . For any fixed k, the expected number of k-dimensional faces of the convex hull of

P is Θ n d-1 d+1 .
Proof. The problem is invariant under scaling, so we can choose the ball to be B. We use our construction of Section 2.3.2 with ρ = 1. Using Claim 2.3.2, we find that setting h j = (j/n)

2 d+1 yields E card W j i ∩ P = n f (h j , 1) vol (B) = Θ(j). Claim 2.3.3 gives m = Θ (ρ/h 1 ) d-1 2 = Θ n d-1
d+1 . With Claims 2.3.1 and 2.3.5 this implies

E card C j i ∩ P ≤ n O f (h j , 1) vol (B) = O(j) so E [card CH(P )] = O n d-1 d+1
by Theorem 10 (i). Moreover, a constant fraction of the W 1 i are pairwise disjoint, and Claim 2.3.6 ensures that E card W 1 i ∩ H (1) = Ω(1); Theorem 10 (ii) thus implies that E [card CH(P )] = Ω n d-1 d+1 .

Upper Bounds on the Smoothed Complexity

We now bound from above S (n, U δB ), using various arguments whose effectiveness vary with the value of δ.

Charging Argument. Our first smoothed complexity bound relies on a charging argument between the witness and the collector that form a pair. Let P * be some point set of diameter at most 1 in R d . Without loss of generality we assume that P * is contained in B, and use a system of witnesses and collectors similar to the one presented in Section 2.3.2 with ρ = 1 + δ.

We make an important change, though: the depth of intersection of each witness W j i depends on i, and is adapted to P * . We start with an inclusion-minimal covering H 1 , H 2 , . . . , H m of ∂(ρB) by half-spaces whose intersection depth with ρB is Θ r 1+δ 2 . Each cuts out a spherical caps of radius r = δn -2 d+1 on ∂(ρB), 1 Raynaud's original argument was more than 7 pages long, still leaving substantial computations to the reader.

and m = O n 2-4 d+1 1 + 1 δ d-1
by Claim 2.3.3. For i = 1, 2, . . . , m and j = 1, 2, . . . , ⌈ln 2 n⌉ we define:

• R i as the set of half-spaces whose inner normal is parallel to a vector from the origin to a point of H i ∩ ∂(ρB), • W j i as the intersection of ρB with a half-space parallel to H i positioned so that E W j i ∩ P = j, • C j i as the union of the half-spaces of R i that do not contain W j i .

The

P p ∈ C j i = O 1 n + P p ∈ W j i .
Proof. Let p * ∈ P * and p its perturbed copy. We fix some indices 1 ≤ i ≤ m and 1 ≤ j ≤ ⌈ln 2 n⌉ and write w = P p ∈ W j i and c = P p ∈ C j i .

p

* u i h W j i u i u i+1 r u i u i+1 r ≤ 2+2δ ≤ 2r h 1+δ Cj i (1 + δ)B h w S ci
Refer to the figure above and let Cj i be the halfspace with normal u i containing C j i ∩ (1 + δ)B and with minimal intersection depth with (1 + δ)B. Let h denote the difference of the intersection depth of the half space cutting out W j i and Cj i with (1 + δ)B and h w denote the intersection depth at which W j i intersects B(p * , δ). Observe that Cj i intersects B(p * , δ) with depth at most h w + h. Since the diameter of Cj i ∩ P is at most 2 + 2δ, considerations on similar triangles show that h ≤ 2r.

If h w ≤ 2r then we obtain the first part of the announced bound on c:

c ≤ f (2r + h, δ) f (2δ, δ) ≤ f (4δn -2 d+1 , δ) f (2δ, δ) = f (4n -2 d+1 , 1) f (2, 1) = 1 f (2, 1) 4n -2 d+1 0 2x -x 2 d-1 2 dx ≤ 1 f (2, 1) 4n -2 d+1 0 (2x) d-1 2 dx = O 1 n .
If h w > 2r then we can assume that c > 2w, as otherwise the claim holds trivially.

In particular h w ≤ δ. Since h ≤ 2r = 2n -2 d+1 , the hypothesis n ≥ 2 d+1 2 ensures h < δ and the depths of intersection of both W j i and Cj i are in the interval [0, 2δ]. We then have

c ≤ f (h w + h, δ) f (2δ, δ) = f 1 + h hw h w , δ f (2δ, δ) ≤ 1 + h h w d+1 2 w ≤ 2 d+1 2 w,
the last inequality coming from h w > 2r ≥ h.

Claim 2.3.7 implies that, for n bigger than the constant 2

d+1 2 , E card C j i ∩ P = O 1 + E card W j i ∩ P = O(j)
and Theorem 10 (i) provides the following bound: 1) .

Proposition 12. S (n, U δB ) = O n 2 d-1 d+1 + n 2 d-1 d+1 δ -(d-
Large Perturbations. As δ → ∞ the bound of Proposition 12 does not tend to Θ n d-1 d+1 , the average-case complexity bound. We thus complement it by a variation on the same system of witnesses and collectors better suited for the analysis of large perturbations. Proof. We again assume, without loss of generality, that P * is contained in B and use the construction of Section 2.3.2 with ρ = 1 + δ and

h j = (1 + δ) j n 2 d+1 . By Claim 2.3.3 we have m = Θ ((1 + δ)/h 1 ) d-1 2 = Θ n d-1 d+1
.

For any point p * in B, we have

f (h j -2, δ) vol (δB) ≤ P p ∈ W j i ≤ f (h j , δ) vol (δB) r δ h j h j -2r Since h j ≥ 3,
E card H (k) = Θ(m) = Θ n d-1 d+1
.

Smoothed Number of Faces. Combining Proposition 12 and Lemma 2.3.8 we obtain the following upper bound on the smoothed number of faces of any dimension: Theorem 13. Let d ≥ 2 be a constant. Then, we have:

Range of δ 0, n 2 d+1 -1 d-1 ⌊ d 2 ⌋ n 2 d+1 -1 d-1 ⌊ d 2 ⌋ , 1 1, 3n 2 d+1 3n 2 d+1 , +∞ S(n, U δB ) O n ⌊ d 2 ⌋ O n 2 d-1 d+1 δ -(d-1) O n 2 d-1 d+1 Θ n d-1 d+1
In dimension 2, a Euclidean noise of amplitude above n -1/3 suffices to guarantee an expected sub-linear complexity. In dimension 3, the second bound is uninteresting as it exceeds the worst-case bound. In dimension d, a Euclidean noise of amplitude above n -4/(d 2 -1) suffices to guarantee an expected sub-quadratic complexity.

Smoothed Number of Vertices. The bounds of Theorem 13 may be improved by a rescaling argument like the one used by Damerow and Sohler [START_REF] Damerow | Extreme points under random noise[END_REF]: splitting the input into small cells and accounting separately for the contribution of each cell using a scaled version of Lemma 2.3.8. This only applies to the number of vertices, as a face of dimension 1 or more may involve perturbation of points coming from more than one cell.

Corollary 14. For any constant d ≥ 2, E card H (1) = O n d-1 d+1 + δ -2d d+1 n 1+2 d-1 (d+1) 2
, and for d = 2 we have:

Range of δ [0, 1 √ n ] [ 1 √ n , 1] [1, n 5/12 ] [n 5/12 , n 2/3 ] [n 2/3 , +∞] S(n, U δB ) O(n) O δ -2 3 n 2 3 O n 2/3 O δ -4 3 n 11 9
O n 1/3

Proof. We continue to assume that P * ⊂ B and we cover B with m ′ = Θ(1 + r -d ) disjoint cells of size r =

m ′ O n m ′ d-1 d+1 = O δn -2 d+1 -d 2 d+1 n d-1 d+1 = O δ -2d d+1 n 4d (d+1) 2 + d-1 d+1 = O δ -2d d+1 n 1+2 d-1 (d+1) 2
.

This proves the first statement. For the second statement, in two dimensions, we proceed differently in each regime:

δ ≤ 1 √ n .
In this case, the worst-case bound is used.

1 ≤ δ ≤ n 5/12
. This case is solved using Proposition 12.

n 2/3 ≤ δ.
Here, Lemma 2.3.8 yields the result.

n 5/12 ≤ δ ≤ n 2/3
. This case is handled through the first statement of the present corollary.

1

√ n ≤ δ ≤ 1.
For the remaining case, we apply the same partitioning idea, but using Proposition 12 instead of Lemma 2.3.8 as an upper bound for one cell. Namely, considering a partitioning induced by covering cells of size δ, we get sets P * i whose convex hull has size n

2 3
i . Summing on the 1 δ 2 cells and using the concavity of x → x 2 3 , we have

O(δ -2 ) i=1 n 2 3 i = O δ -2 (δ 2 n) 2 3 = O ( n δ ) 2 3

Lower Bound: Points in Convex Position

We finally analyze the expected complexity of Euclidean perturbations of some particular point configuration: points in convex position that are "nicely spread out"; more precisely, we take P * to be an (ε, κ)-sample of a sphere with fixed radius, ie. a sample such that any ball of radius ε centered on the sphere contains between 1 and κ points of the sample.

Our motivation for studying this class of configurations is that they are natural candidates to realize the smoothed complexity of convex hulls in 2 and 3 dimensions and therefore provide an interesting lower bound. In light of Theorem 10 (ii), setting up the witnesses W 1 i is enough to obtain a lower bound on the expected size of the convex hull; we give a complete analysis since at this stage it comes easily and makes it clear that the lower bound obtained by our choice of W 1 i is sharp for these configurations.

k, E card H (k) is Range of δ [0, n 2 1-d ] [n 2 1-d , 1] [1, n 2 d+1 ] [n 2 d+1 , +∞) E card H (k) Θ(n) Θ n d-1 2d δ 1-d 2 4d Θ n d-1 2d δ (1-d) 2 4d Θ n d-1 d+1
The last bound corresponds to the average-case behavior which applies for δ sufficiently large, as follows from Lemma 2.3.8. We thus only have to analyze the range δ ≤ n 2 d+1 . Note that the first bound merely reflects that a point remains extreme when the noise is small compared to the distance to the nearest hyperplane spanned by points in its vicinity, and that the bounds reveal that as the amplitude of the perturbation increases, the expected size of the convex hull does not vary monotonically (see Figures 2.2a and 2.2c): the lowest expected complexity is achieved by applying a noise of amplitude roughly the diameter of the initial configuration.

The following claim will be useful to position the witnesses and control the collectors.

Claim 2.3.9. Under the assumptions of Theorem 15, let j ≤ ln 2 n, let H be a halfspace such that E [card (H ∩ P )] = Θ(j) and let h denote its depth of intersection with (1 + δ)B.

(i) If δ = O j n 2 d-1 then h = Θ j n 2 d-1 and if Ω j n 2 d-1 ≤ δ ≤ O n 2 d+1 then h = Θ j n 1 d δ d+1 2d . (ii) If H ′ is a half-space that intersects (1 + δ)B with depth 9h then E [card (H ′ ∩ P )] = O(E [card (H ∩ P )]).
Proof. The region S ⊆ ∂B in which we can center a ball of radius δ that intersects H is the intersection of ∂B with a half-space parallel to H and that intersects it with depth h; S is thus a spherical cap of B of radius

√ 2h -h 2 = Θ √ h and
(d -1)-dimensional area Θ h d-1 2
. By the sampling condition in the definition of P * , each ball of radius n

(H ∩ (p * + δB)) vol (δB) ≤ f (h, δ) f (2δ, δ) = O h d+1 2 δ d-1 2 δ d = O h δ d+1 2
.

Shrinking h by a factor two, we obtain that a constant fraction (depending only on d) of the relevant points contribute for at least f (h/2,δ)

f (2δ,δ) = Ω h δ d+1 2 to E [card (H ∩ P )], hence Θ(j) = E [card (H ∩ P )] = Θ nh d-1 2 h δ d+1 2 = Θ nδ -d+1 2 h d and h = Θ j n 1 d δ d+1 2d
. The condition h ≤ δ thus amounts to δ = Ω j n 2 d-1 , giving the second regime.

If h > δ then a constant fraction of the relevant points p * are such that H intersects p * + δB with depth at least δ/2, thus containing a constant fraction of each of these balls (and the rest of the relevant points contribute less). It follows that Θ(j) = Θ nh Observe that in either case, the number of points in H ∩P depends polynomially on h. Thus, multiplying the depth by 9 multiplies the expected number of points by a constant (depending only on d) and statement (ii) follows.

Proof of Theorem 15. We use our construction of Section 2.3.2 with ρ = 1 + δ. We fix h j such that each W j i contains Θ(j) points of P ; the values of h j are given by Claim 2.3.9(i). By Claim 2.3.5, C j i is contained in a half-space that intersects (1 + δ)B with depth at most 9h j . Claim 2.3.9(ii) thus ensures that

E card C j i ∩ P = O E card W j i ∩ P = O(j)
and we can apply Theorem 10 (i and we have three regimes.

If δ = O 1 n 2 d-1 then Claim 2.3.9(i) yields h 1 = Θ 1 n 2 d-1 and m = Θ 1 + δ h 1 d-1 2 = Θ      1 1 n 2 d-1   d-1 2    = Θ (n) . If Ω j n 2 d-1 ≤ δ ≤ O n 2 d+1
then Claim 2.3.9(i) yields

h 1 = Θ 1 n 1 d δ d+1 2d . If δ ≤ 1 then m = Θ 1 + δ h 1 d-1 2 = Θ      1 1 n 1 d δ d+1 2d   d-1 2    = Θ n d-1 2d δ 1-d 2 4d
and if δ ≥ 1 then

m = Θ 1 + δ h 1 d-1 2 = Θ      δ 1 n 1 d δ d+1 2d   d-1 2    = Θ n d-1 2d δ (1-d) 2 4d
Up to multiplicative constants, the boundaries between the regimes can be set as in the statement of the Theorem.

Gaussian Perturbation

The Gaussian model raises two difficulties compared to the Euclidean model: the computations are more technical and the fact that the perturbations have noncompact support requires to adapt the witness-collector construction. We expect some of the results to extend to arbitrary dimension mutatis mutandis, but for the sake of the presentation only spell out the analysis in the two-dimensional case.

Preliminaries

Recall that if X ∼ N (µ, σ 2 ) then for any t ≥ 0 we have P

[X ≥ µ + tσ] = Q(t),
where Q is the tail probability of the standard Gaussian distribution:

Q(x) x 0 1 2 1 ∀x ∈ R, Q(x) = 1 √ 2π ∞ x e -t 2 2 dt.
The solution to the functional equation

f (x)e f (x) = x
This essentially follows from [15, Equations (4.6) and (4.9)]; note that the constant 1.01 is arbitrary and any constant strictly larger than 1 would do (the constants in the Θ() would change but we do not care). The following inequalities will be useful:

Lemma 2.4.1.

(i) For x > 0, e -x 2 2 x + 1 x < √ 2πQ(x) < e -x 2 2 x . (ii) For x > 1/4, Q x + 1 x = Θ (Q(x)). (iii) (a) n i=0 e -i 2 x = O 1 + 1 √ x (b) For any constant γ > 0, for x > γ n 2 , n i=0 e -i 2 x = Ω 1 √ x (c) For any constant γ > 0, for x < γ n 2 , n i=0 e -i 2 x = Ω (n)
Proof. The upper bound of statement (i) comes from

Q(x) = ∞ x 1 √ 2π e -t 2 2 dt < ∞ x t √ 2πx e -t 2 2 dt = ∞ x 2 2 e -t x √ 2π dt = 1 √ 2πx e -x 2 2
and the lower bound comes from the fact that

1 + 1 x 2 Q(x) = ∞ x 1 + 1 x 2 1 √ 2π e -t 2 2 dt > ∞ x 1 + 1 t 2 1 √ 2π e -t 2 2 dt = e -x 2 2 x √ 2π .
Now, for statement (ii), we have Q(x) ≥ Q(x + 1 x ) since Q is a decreasing function. Moreover, from statement (i) we have

√ 2πQ(x + 1 x ) > x + 1 x 1 + x + 1 x 2 e -( x+ 1
x )

2 2 = x 4 + x 2 x 4 + 3x 2 + 1 e -1-1 2x 2 e -x 2 2 x > x 4 + x 2 x 4 + 3x 2 + 1 e -1-1 2x 2 √ 2πQ(x)
Statement (ii) then follows from noting that the image of [1/4, +∞) under the function x → x 4 +x 2 x 4 +3x 2 +1 e -1-1 2x 2 is contained in some closed interval of (0, +∞).

The proof of Statements (iii-a) and (iii-b) follows from a standard comparison between series and integrals:

if x > γ n 2 , n i=0 e -i 2 x ≥ n+1 0 e -t 2 x dt ≥ n √ x 0 e -u 2 du √ x ≥ √ γ 0 e -u 2 du √ x ≥ Ω 1 √ x
and for any x > 0,

e -t 2 10 0 1 1 2 3 4 5 6 n i=0 e -i 2 x ≤ 1 + n 0 e -t 2 x dt ≤ 1 + n √ x 0 e -u 2 du √ x ≤ 1 + ∞ 0 e -u 2 du √ x = O 1 + 1 √ x . Statement (iii-c) is trivial since, when x < γ n 2 , n i=0 e -i 2 x ≥ n • e -γ = Ω (n).

Witness-Collector Construction

One Witness-Collector Pair. The pairs witness-collectors that we use to analyze Gaussian perturbations are based on the following basic construction. Let w, h and α be positive reals and u some vector in the plane.

-We define R( u, α) as the set of halfplanes whose inner normal makes an angle at most α 2 with u. -We define W (w, h, u) as the semiinfinite half strip with axis of symmetry O + R u, with width w and distance h to the origin. To save breath we define the height of a semi-infinite half strip as its distance to the origin -so W (w, h, u) has height h.

-We define C(w, h, u, α) as the union of the half-planes in R( u, α) that do not contain W (w, h, u).

C(w, h, u, α) α u h W (w, h, u) w H + H -

O

The following more explicit description of C(w, h, u, α) will be convenient:

Claim 2.4.2. C(w, h, u, α) = H -∪ H + where H -and H + are the half-planes whose inner normals make an angle of ± α 2 with u, that contain W (w, h, u) and have one of the corners of W (w, h, u) on their boundary.

Proof. This follows from observing that any halfplane through ∂H + ∩ ∂H -and contained in C(w, h, u, α) also contains W (w, h, u). This construction has the following properties: (a') Any halfplane whose inner normal makes an angle at most α 2 with u contains W (w, h, u) or is contained in C(w, h, u, α). (b') If h j > h j+1 and w j < w j+1 then W (w j , h j , u) ⊆ W (w j+1 , h j+1 , u). (c') W (w, h, u) ⊆ C(w, h, u, α). Families of pairs (W (w, h, u), C(w, h, u, α)) therefore combine easily into systems of witnesses and collectors. We will control the expected number of points in a witness by setting w and h adequately and tune α accordingly thanks to the next fact. We say that a point p * is in the slab of W (w, h, u) if the ray p * + R + u intersects W (w, h, u).

Claim 2.4.3. Let u be arbitrary and let v denote a unit vector orthogonal to u. If p * ∈ R 2 is in the slab of W (w, h, u) and outside the interior of C(w, h, u, α) then

d(p * , C(w, h, u, α)) = d(p * , W (w, h, u)) cos α 2 - w 2 + | --→ Op * • v| sin α 2 .
Proof. Let H denote the half-plane contained in C(w, h, u, α) and whose distance to p * is minimal. Let q * and r * denote respectively the orthogonal projections of p * on W (w, h, u) and C(w, h, u, α). Let s * denote the intersection of p * q * with the boundary of H. System of Witnesses and Collectors. Our construction is parameterized by some positive real α and two sequences of positive reals

h 1 > h 2 > • • • > h ℓ and w 1 ≤ w 2 ≤ • • • ≤ w ℓ .
We choose an inclusion-minimal cover of ∂B by halfplanes H 1 , H 2 , . . . , H m each intersecting ∂B in a circular arc of angle α; we let u i denote the center of H i ∩ ∂B and note that m = Θ 1 α . We define R i as the set of half-planes whose inner normal is parallel to a vector from the origin to a point of H i ∩ ∂B and let W j i = W (w j , h j , u i ) and C j i = C(w j , h j , u i , α).

Lemma 2.4.4. R 1 ∪R 2 ∪. . .∪R m covers the set of half-planes and {(W j i , C j i )}1≤i≤m 1≤j≤ℓ is a system of witnesses and collectors for that covering. Moreover, some Ω h 1 w 1 of the W 1 i are pairwise disjoint.

Proof. The definition readily ensures that the union of the R i is the set of all half-planes and that Condition (a) holds. The monotonicity of the h i and the w i implies that Condition (b) is also satisfied. Claim 2.4.2 implies that each W j i is contained in the corresponding C j i , so Condition (c) holds. Each W 1 i is contained in a wedge with apex the origin and opening angle Θ w 1 h 1 . Some Ω h 1 w 1 of these wedges are disjoint (except in the origin), so the corresponding W 1 i 's are pairwise disjoint.

Warm-up: Gaussian Polygons Made Easy

To illustrate our construction, we revisit the classical problem of computing the expected number of faces of the convex hull from a Gaussian distribution: Theorem 16 (Rényi and Sulanke [START_REF] Rényi | Über die konvexe Hülle von n zufällig gewählten Punkten I[END_REF]). Let P = {p 1 , p 2 , . . . , p n } be a set of random points chosen independently from N (0, I 2 ). The expected number of vertices of the convex hull of P is Θ √ ln n .

Proof. We use the construction of Section 2.4.2 with ℓ = ln 2 n and the values of α, w j and h j set as specified on the right. Lemma 2.4.4 ensures that we obtain a system of witnesses and collectors, so it only remains to analyze the expected number of points in W j i and C j i . We complete each vector u i into a direct, orthonormal frame (O, v i , u i ); in that frame, the coordinates of any point p ∈ P write (x i , y i ) where x i , y i are independent random variables chosen from N (0, 1).

α = 1 h 1 = Θ 1 √ ln n w j = 2 h j = W 0 n 2 j 2
The probability for p to be in W j i therefore writes

P p ∈ W j i = P [y i > h j ] P [|x i | < 1] = Θ (Q(h j )) . Lemma 2.4.1 (i) yields Q(x) = Θ 1 x e -x 2 2 for x > 1 so, since j ≤ ln 2 n, Q(h j ) = Θ     e -1 2 W 0 n 2 j 2 W 0 n 2 j 2     = Θ     1 W 0 n 2 j 2 e W 0 n 2 j 2     = Θ j n (2.6) and E card W j i ∩ P = nΘ (Q(h j )) = Θ(j). Since for n ≥ 3, α < 1 √ W 0 (3 2 ) < π 4 ,
tan α 2 < 0.5 and

2h j w j ≥ 2h ℓ w j = W 0 n 2 ln 4 n ≥ 1.
This means that tan α 2 < 2h j w j , so the origin is not in C j i . By Claims 2.4.2 and 2.4.3, C j i is contained in the union of two half-planes with height hj = h j cos α 2sin α 2 = h j -O (α). Thus,

E card C j i ∩ P ≤ 2nQ hj = 2 (nQ (h j ))   Q hj Q (h j )  
We already observed that nQ (h j ) = Θ(j). By Lemma 2.4.1 (i) we have

Q hj Q (h j ) = e -1 2 hj 2 -h 2 j h j hj = h j hj e O(h j α+α 2 )
and with Equation (2.5) we finally obtain

E card C j i ∩ P = O je O(h j α) = O je O √ 1-ln j ln n = O(j),
and Property (b') holds. Theorem 10 (i) then yields that

E card H (1) = O(m) = O( √ ln n).
Let H i denote the halfplane with same height and inner normal as W 1 i and p u i be the point of P extremal in direction u i . By construction p u i belongs to H (1) , thus

E card W 1 i ∩ H (1) ≥ P p u i ∈ W 1 i = P [p u i ∈ H i ] P p u i ∈ W 1 i | p u i ∈ H i We have P [p u i ∈ H i ] = P [P ∩ H i = ∅] ≥ P P ∩ W 1 i = ∅ ≥ 1 -1 e > 1 2
by Lemma 2.2.1 (a). Gaussian noise perturbs points independently in directions x and y of frame (O, v i , u i ). The choice of p u i in P depends only on the y pertur-bation, thus knowing that p u i ∈ H i , deciding if it is in W 1 i or in H i \ W 1 i depends only on the coordinate along direction v i , thus

P p u i ∈ W 1 i | p u i ∈ H i = p∈H i ∩P P p ∈ W 1 i | p u i = p P [p u i = p | p u i ∈ H i ] = p∈H i ∩P P [|x p | ≤ 1] P [p u i = p | p u i ∈ H i ] = P [|x p 1 | ≤ 1] p∈H i ∩P P [p u i = p | p u i ∈ H i ] = P [|x p 1 | ≤ 1] = 1 -2Q(1) > 1 2 (2.7)
Together we get that Lemma 2.4.4 ensures that we can also apply Theorem 10 (ii) and get that E card H (1) = Ω( √ ln n) as well.

Upper Bound on the Smoothed Complexity

As in the Euclidean case, for large Gaussian perturbation the smooth complexity is identical to the i.i. Proof. We can suppose that P * is included in rB. We set up the Gaussian witnesscollector construction of Section 2.4.2, with ℓ = ln 2 n and the values of α, w j and h j set as specified on the right. Every point p ∈ P writes p

= x i v i + y i u i with x i , y i ∼ N (0, σ 2 ) and u i , v i ∈ S 1 , v i ⊥ u i .
Thus, the probability for p to be in W j i is upperbounded by P [y i > h j ] and is lower-bounded by

P [y i > h j ] P |x i | ≤ w-r 2 . α = σ h 1 -r = Θ 1 √ ln n w j = w = 7 2 σ h j = r + σ W 0 n 2 j 2
It's easy to see that

P |x i | ≤ w-r 2 is lower-bounded from below by P |x i | ≤ 5w 14 (since r ≤ σ = 2w 7 )
, which is a constant.

Now, P [y

i > h j ] ∈ Q h j +r σ , Q h j -r σ so P [y i > h j ] < Q W 0 n 2 j 2 = Θ j n .
As

σ ≥ 3r √ ln n ≥ 2r ln(n 2 ) ≥ 2r W 0 (n 2 ) ≥ 2r W 0 n 2 j 2 , we get 2r σ ≤ 1 W 0 n 2 j 2 = σ h j -r and Q h j + r σ = Q h j -r σ + 2r σ ≥ Q h j -r σ + σ h j -r .
Now, using Lemma 2.4.1 (ii) , as long as

h j -r σ > 1 4 (which is true for n ≥ 3 and j ≤ ln 2 n) we get that Q h j -r σ + σ h j -r = Ω Q h j -r σ = Ω j n
using Equation (2.6).

We obtain that for any p * ∈ P * , P p ∈ W j i = Θ j n , and so

E card P ∩ W j i = Θ (j) .
Condition (a') therefore holds. Since n ≥ 3, α <

1 √ W 0 (3 2 ) < π 4 , tan α 2 < 0.5 and
2h j w ≥ 2 h ℓ -r w = 4 7 W 0 n 2 ln 4 n ≥ 0.5.
Thus, tan α 2 < 2h j w , so the origin is not in C j i . Using Claim 2.4.3 with p * at the origin, the collector C j i is included in the union of two half-spaces with height hj = h j cos α 2 -w 2 sin α 2 ≥ h j cos α 2 -7 8 ασ, since sin(x) < x for x > 0. Now,

h j cos α 2 = h j + (cos α 2 -1)h j ≥ h j - 1 2 α 2 2 h j = h j - 1 8 ασ h j h 1 -r ≥ h j - 1 8 ασ h j h j -r ≥ h j - 1 8 ασ since cos x -1 ≥ -1 2 x 2 . Thus, we obtain hj ≥ h j -ασ. Note that Q h j -r σ ≥ Q hj -r σ + α = Q hj -r σ + σ h 1 -r . Since hj ≤ h 1 , σ h 1 -r ≤ σ hj -r and Q h j -r σ > Q hj -r σ + σ h 1 -r > Q hj -r σ + σ hj -r = Ω Q
hjr σ using Lemma 2.4.1 (ii) (we have hj -r σ > 1 4 for n ≥ 3 and j ≤ ln 2 n), we get

Q hj -r σ = O j
n by Equation (2.6). Thus, E card P ∩ C j i = O(j), Theorem 10 (i) can be applied and we obtain

E card H (1) = E [card CH(P )] = O 1 α = O √ ln n . Corollary 17. S n, N (0, σ 2 ) = O ln(n) σ 2 ln (nσ 2 ) + √ ln n .
Proof. Let P * be some point of diameter at most 1. Without loss of generality, we assume that P * ⊂ B. We cover B with

m ′′ = Θ 1 + 1 r 2 disjoint cells of size r = σ 3 √ ln n We break down P * into P * 1 ∪ P * 2 ∪ • • • ∪ P * m ′′
by taking its intersection with each covering cells; we let P i denote the perturbation of P * i and n i = card P i . Every vertex of CH(P ) is a vertex of some CH(P i ), and we can apply Lemma 2.4.5 to bound the number of vertices of CH(P i ) from above by

√ ln n i . If m ′′ > 1,
the sum is maximized with ∀i, n i = n m ′′ , which bounds from above the number of vertices of CH(P ) by

m ′′ O ln n m ′′ = O 1 r 2 ln (nr 2 ) = O ln(n) σ 2 ln (nσ 2 )
using Equality (2.5).

A Better Smoothed Upper Bound for Gaussian Perturbation

Theorem 18. S(n, N (0,

σ 2 I 2 )) = O √ ln n σ + √ ln n .
Let P * be some point set of diameter at most 1 in the plane and, without loss of generality, assume that P * is contained in B. We use a system of witnesses and collectors similar to the one presented in Section 2.4.2 with ℓ = ln 2 n. As in the Euclidean case, a key difference is that the depth of intersection of each witness W j i depends on i, and is adapted to P * . Specifically, we set w and α to the values on the right, choose the u i regularly spaced on S 1 with u i u i+1 = Θ(α). We then define R i = R( u i , α), W j i = W (h j i , w, u i ) and C j i = C(h j i , w, u i , α) where h j i depends on P * and is tuned so that the expected number of points in the witnesses are what they should be.

w = 2(1 + σ) α = (2+σ) 2 + 2 √ 2σ √ ln n +2 √ 2σ 2 -(2+σ) (1+σ √ ln n) h j i s. t. E card P ∩ W (h j i , w, u i ) = j
We first relate the distances from a point p * of P * to a witness W j i and a collector C j i :

Claim 2.4.6. If p * ∈ R 2 is in the slab of W j i and outside the interior of C j i , then

d(p * , W j i ) -d(p * , C j i ) ≤ σ √ 2 ln n .
Proof. Let h(p * ) and h(p * ) denote, respectively, d(p * , W j i ) and d(p * , C j i ). By Claim 2.4.3,

h(p * ) = h(p * ) cos α 2 - w 2 + | --→ Op * • v i | sin α 2
and with 1 -

cos x ≤ x 2 2 , sin |x| < |x|, w 2 = 1+σ, and | --→ Op * • v i | ≤ 1, this becomes h(p * ) -h(p * ) ≤ h(p * ) -h(p * ) cos α 2 + (2 + σ) sin α 2 ≤ h(p * ) α 2 8 + (2 + σ) α 2 α 2 C j i W j i h(p * ) h(p * ) u i w j 2 p * B O
The distance from p * to W j i = W (h j i , w, u i ) is maximized when p * is located at the point of ∂B with outer normalu i and all other points of P * are at the symmetric position, at the point of ∂B with normal u i . The same argument as in Equation (2.6) and the observation that ln(x) > W 0 (x) for x ≥ 3 yield the upper bound

h(p * ) ≤ 2 + σ W 0 (n 2 ) ≤ 2 1 + σ √ ln n .
Injecting this in the above inequality we get

h(p * ) -h(p * ) ≤ 1 + σ √ ln n α 2 4 + (2 + σ) α 2 The polynomial P (α) = 1 + σ √ ln n α 2 4 + (2 + σ) α 2 - σ √
2 ln n can be checked to be negative for

0 ≤ α ≤ (2 + σ) 2 + 2 √ 2σ √ ln n + 2 √ 2σ 2 -(2 + σ) (1 + σ √ ln n) ,
and that concludes the proof.

The distance from a point p * to W j i and C j i determines the probability that the perturbation of p * belongs to either of these sets.

Claim 2.4.7. P p ∈ W j i = Θ Q d(p * ,W j i ) σ and P p ∈ C j i = O Q d(p * ,C j i ) σ .
Proof. A perturbed point p is in W j i if it satisfies two conditions: (α) its displacement from p * along u i should be greater than d(p * , W j i ), and (β) its displacement in the orthogonal direction is in the slab of width w j . The conditions are independent, (α) is true with probability Q

d(p * ,W j i ) σ
and (β) is true with constant probability since w = 2 + 2σ ensures that the allowed orthogonal displacement for p * is larger than σ. The statement for W j i follows. As for the collectors, the probability that a perturbed point p is in C j i is bounded from above by the sum of the probabilities to be in H + and to be in H -, which are both Q

d(p * ,C j i ) σ .
Combining the two previous claims we now get that witness and collector get, on average, essentially the same number of points.

P p ∈ C j i = O Q h(p * ) σ = O Q h(p * ) σ - 1 √ 2 ln n = O Q √ 2 ln n + 1 √ 2 ln n - 1 √ 2 ln n = O Q √ 2 ln n = O 1 n
and the statement follows. If h(p * ) ≤ σ √ 2 ln n + σ √ 2 ln n then we have

P p ∈ C j i = O Q h(p * ) σ = O Q h(p * ) σ - 1 √ 2 ln n If h(p * ) ≤ σ 4 + σ √ 2 ln n ≤ σ 1 4 + 1 √ 2 ln 3
then h(p * ) is bounded from above by 2σ and

P p ∈ W j i = Ω (Q (2)) = Ω(1). Then, P p ∈ C j i ≤ 1 = O P p ∈ W j i
and the statement also holds. Thus, we can suppose that h(p * ) ≥ σ 4 + σ √ 2 ln n and use Lemma 2.4.1 (ii) to get:

P p ∈ C j i = O Q h(p * ) σ - 1 √ 2 ln n + 1 h(p * ) σ -1 √ 2 ln n . Since 1 h(p * ) σ -1 √ 2 ln n ≥ 1 √ 2 ln n + 1 √ 2 ln n -1 √ 2 ln n = 1 √ 2 ln n we get P p ∈ C j i = O Q h(p * ) σ = O P p ∈ W j i
and the statement also holds. Finally assume that p * ∈ C j i . In such a case Claims 2.4.3 and 2.4.6 do not apply directly, but we have 1 2 ≤ P p ∈ C j i ≤ 1 so we have to argue that P p ∈ W j i = Ω(1). Let us move from p * in the directionu i until we reach some point p * on the boundary of C j i ; observe that P p * + η ∈ C j i ≥ 1 2 where η ∼ N (0, σ 2 I 2 ). Now p * satisfies the hypotheses of Claim 2.4.6 and the above analysis implies that P p * + η ∈ W j i = Ω P p * + η ∈ C j i = Ω(1). Moving from p * to p * only increased the distance to W j i , so we also have

P p ∈ W j i ≥ P p * + η ∈ W j i = Ω(1).
We now have all the ingredients to prove our upper bound on the smoothed complexity under Gaussian noise.

Proof of Theorem 18. We set up our witnesses and collectors as described above. Since the parameter w is fixed and each sequence {h j i } j is decreasing, Lemma 2.4.4 yields that {(W j i , C j i )}1≤i≤m 1≤j≤ℓ is a system of witnesses and collectors for the covering

R 1 ∪ R 2 ∪ . . . ∪ R m of the set of half-planes. Each parameter h j i is set so that E card W j i ∩ P = j and Claim 2.4.8 implies that E card C j i ∩ P = O(j). Theorem 10 (i) thus implies that S(n, N (0, σ 2 I 2 )) = O 1 α = O      1 + σ √ ln n (2 + σ) 1 + 2 √ 2 (2+σ) 2 σ 2 + σ √ ln n -1      . (2.8) If σ ≤ 1 √ ln n then Equation (2.8) simplifies into S(n, N (0, σ 2 I 2 )) = O     1 1 + 1 (1+σ) 2 σ 2 + σ √ ln n -1     .
Notice that in this case,

1 (1+σ) 2 σ 2 + σ √ ln n
is bounded by some constant C and since for 0

< x < C, √ 1 + x -1 = Θ(x), S(n, N (0, σ 2 I 2 )) = O   1 1 (1+σ) 2 σ 2 + σ √ ln n   = O √ ln n σ . If 1 √ ln n ≤ σ ≤ 1 then Equation (2.8) simplifies into S(n, N (0, σ 2 I 2 )) = O σ √ ln n 1 + Θ(σ 2 ) -1 = O σ √ ln n σ 2 = O √ ln n σ If 1 ≤ σ then Equation (2.8) simplifies into S(n, N (0, σ 2 I 2 )) = O σ √ ln n σΘ(1) = O( √ ln n).
In each case we therefore have S(n, N (0,

σ 2 I 2 )) = O √ ln n σ + √ ln n .

Lower Bound on Smoothed Complexity: Points in Convex Position

We finally investigate lower bounds on the smoothed complexity by analyzing the size of the convex hull of a Gaussian perturbation of points in convex position, as in Section 2.3.5.

Theorem 19. Let P * = {p * i , 1 ≤ i ≤ n} be the set of vertices of a regular n-gon of radius 1 in R 2 . Let P = {p i = p * i + η i } where η 1 , η 2 , . . . , η n are random vectors in R 2 chosen independently from N (0, σ 2 I 2 ). The expected number of vertices of the convex hull of P is Range of σ 0, 1

n 2 1 n 2 , 1 √ ln n 1 √ ln n , +∞ E card H (1) Ω(n) Ω 4 √ ln(n √ σ) √ σ Ω √ ln n
We use the witness-collector construction presented in Section 2.4.2. We only care about the lower-bound, so, shortening W 1 i into W i , we need only define one level of witnesses {W i } 1≤i≤m to apply Theorem 10 (ii).

Parameters Setting. We set h 1 and w 1 depending on σ and n as summarized below. We let u 1 , u 2 , . . . , u m denote a family of vectors in S 1 such that u i is aligned with p * 2πi m , so these vectors are more or less equally spaced on S 1 . The witnesses are defined as W i = W (w 1 , h 1 , u i ). We choose m maximal so that the {W i } are pairwise disjoint; Lemma 2.4.4 ensures that we can set m = Ω min n, h 1

w 1 . 0 ≤ σ < 2 n 2 2 n 2 ≤ σ < 1 4 W 0 n 2 4 1 4 W 0 n 2 4 ≤ σ w 1 2σ 2σ + 2 √ σ 3 2 W 0 2 3 (n √ σ) 4 3 -1/4 2σ + 2 h 1 1 1 + σ 3 2 W 0 2 3 (n √ σ) 4 3 1 + σ W 0 n 2 4
Preparation. Let i ∈ {1, 2 . . . , m}. As in Section 2.4.3, we let (O, v i , u i ) denote some orthonormal frame and let H i be the halfplane supporting W i with inner normal u i . We renumber the points of P * with indices in {-n-1 2 , . . . , n-1 2 } so that p * 0 is the point in direction u i . For the sake of the presentation we assume that n is odd (the case of even n follows with trivial modifications). We write (x i , y i ) for the coordinates of p i in (O, v i , u i ) and denote by p u i ∈ H (1) the point of P extremal in direction u i . Our goal is to prove that E card W i ∩ H (1) is Ω(1) in order to apply Theorem 10 (ii); in the light of

E card W i ∩ H (1) ≥ P [p u i ∈ W i ]
we set out to bound from below the probability that p u i lies in W i . We write z t for the distance from p * t to H i and note that

z 0 = h 1 -1 and z t = h 1 -1 + 1 -cos 2πt n For x ∈ [-1 2 , 1 2 ] we have 8x 2 ≤ 1 -cos(2πx) ≤ 20x 2 , hence h 1 -1 + 8 t 2 n 2 ≤ z t ≤ h 1 -1 + 20 t 2 n 2 8t 2 n 2 ≤ z t -z 0 ≤ 20t 2 n 2 .
(2.9)

Analysis for Small σ. We start with the case σ < 2 n 2 , where the analysis is simpler but already uses the main ingredients of the general case. Since h 1 = 1, we have z 0 = 0 and therefore p * 0 lies on the boundary of H i . We condition on the event {p 0 ∈ H i and p u i = p 0 } and obtain:

P [p u i ∈ W i ] ≥ P [p 0 ∈ W i | p 0 ∈ H i and p u i = p 0 ] P [p 0 ∈ H i and p u i = p 0 ] (2.10)
We bound each of these terms in turn.

Claim 2.4.9. When σ < 2 n 2 , P [p 0 ∈ H i and p u i = p 0 ] = Ω(1).

Proof. Using the independence of the random variables {y t } t we write

P [p 0 ∈ H i and p u i = p 0 ] ≥ P [y 0 ≥ h 1 and ∀t = 0, y t ≤ h 1 ] = P [y 0 ≥ h 1 ] t =0 P [y t ≤ h 1 ]
As p * 0 ∈ H i , the point p 0 has probability at least 1 2 of remaining in the half-plane H i after a Gaussian perturbation, so P [y 0 ≥ h 1 ] ≥ 1 2 . Moreover, y t ∼ N (h 1z t , σ 2 ) so Lemma 2.4.1 (i) and the bounds on z t and σ lead to:

P [y t ≥ h 1 ] = P [y t -E [y t ] ≥ z t ] = Q zt σ ≤ Q 8t 2 n 2 σ ≤ Q 4t 2 ≤ e -2t 2 ,
and

P [y t ≤ h 1 ] ≥ 1 -e -2t 2 .
Taking the logarithm we obtain

ln P [p 0 ∈ H i and p u i = p 0 ] = ln P [y 0 ≥ h 1 ] + 2 n-1 2 t=1 ln P [y t ≤ h 1 ] ≥ ln 1 2 + 2 n-1 2 t=1 ln 1 -e -2t 2
Then, using that for x ∈ (0, 1 2 ] we have ln(1x) > -2x and Lemma 2.4.1 (iii-a) we get 1) = Ω(1).

-ln P [p 0 ∈ H i and p u i = p 0 ] ≤ ln 2 -2 n-1 2 t=1 -2e -2t 2 ≤ ln 2 + 4 n-1 2 t=0 e -2t 2 = O(1), and
P [p u i = p 0 ] = e -O(
Equation (2.10) finally implies that P [p u i ∈ W i ] is Ω(1), so E card W i ∩ H (1) is indeed Ω(1) for this range of σ.

Relevant Points. The contribution of the tth point to

E [card (H i ∩ P )] is Q zt σ .
The gist of our analysis for larger σ is to split the points into two parts, the relevant points where

Q zt σ = Θ Q z 0 σ
and the irrelevant ones. The expected number of points in H i is (up to a constant multiplicative factor) at least the number of relevant points times Q z 0 σ ; fine tuning z 0 so that this product is Ω(1) then amounts to solving some functional equation. Specifically, we call a point p t . We denote by P r the relevant points.

relevant if |t| ≤ t m = min nσ √ z 0 , n-1
The same conditioning as in Equation (2.10) yields

P [p u i ∈ W i ] ≥ P [p u i ∈ W i | p u i ∈ H i ∩ P r ] P [p u i ∈ H i ∩ P r ] .
(2.11)

One of the terms can be bounded as easily as for small σ.

Claim 2.4.10.

When σ ≥ 2 n 2 , P [p u i ∈ W i | p u i ∈ H i ∩ P r ] ≥ 1 2 .
Proof. First, note that the parameter w 1 is set so that in the orthogonal projection on the v i -axis, the image of the witness contains the image of the ball B(p t , σ) whenever p t is relevant. This ensures that

P [p u i ∈ W i | p u i ∈ H i and p u i is relevant] ≥ 1 -2Q(1) ≥ 1 2 .
Counting Relevant Points in H i . Bounding the remaining probability requires different quantitative analysis depending on the range of σ but are based on the same principle: counting the expected number of relevant points in H i . Since H i has inner normal u i , we have

P [p u i ∈ H i | p u i ∈ P r ] = P [H i ∩ P r = ∅] .
Thus, by the Chernoff bound of Lemma 2.2.1 (a), to show that the right-hand term is Ω(1) it suffices to show that H i contains on average Ω(1) relevant points. Notice that

P [p t ∈ H i ] = P [y t -E [y t ] > z t ] = Ω Q z t σ ,
so the expected number of relevant points in H i writes

Ω tm t=-tm Q z t σ = Ω Q z 0 σ tm t=0 1 zt σ + σ zt z 0 σ e -1 2σ 2 (z 2 t -z 2 0 ) . (2.12)
Recall that z t = z 0 + Θ t 2 n 2 . How we evaluate Equation (2.12) depends on the range of σ.

Large σ. When σ ≥ 1 4 W 0 n 2 4 , every point is relevant, ie. t m = n-1 2 , since z 0 = σ W 0 n 2 4 implies nσ √ z 0 = n σ W 0 n 2 4 ≥ n 2 . Claim 2.4.11. When σ ≥ 1 4 W 0 n 2 4 , P [p u i ∈ H i ∩ P r ] = Ω(1).
Proof. Since every point is relevant, this probability equals the probability that H i ∩ P is non-empty. Computations similar to that of Equation (2.6) yield that

Q z 0 σ = Θ 1 n . Moreover, z t ≥ σ 2 so 1 z t σ + σ z t = Θ σ zt . Also, z t = Θ(z 0 ) and z 2 t -z 2 0 = Θ t 2 z 0 n 2 .
Injecting these three relations in Equation (2.12) we obtain that the expected number of (relevant) points in H i writes

E [card (H i ∩ P )] = Ω   1 n n-1 2 t=0 z 0 z t e -t 2 Θ( z 0 n 2 σ 2 )   = Ω   1 n n-1 2 t=0 e -j 2 Θ( z 0 n 2 σ 2 )   Since z 0 n 2 σ 2 < 4 n 2 , Lemma 2.4.1 (iii-c) implies that n-1 2 t=0 e -t 2 Θ( z 0 n 2 σ 2 ) = Ω(n),
so we finally get that H i contains Ω(1) (relevant) points on average. The Chernoff bound of Lemma 2.2.1 (a) yields that P [H i ∩ P = ∅] is Ω(1), and so is

P [p u i ∈ H i ∩ P r ] = Ω(1). Intermediate σ. When 2 n 2 ≤ σ < 1 4 W 0 n 2 4
we have

z 0 = σ 3 2 W 0 2 3 (n √ σ) 4 3 . The function x → x 3 2 W 0 2 3 (n √ x) 4 3
is increasing. Let us define σ 0 as the solution of

σ 0 = 1 4 3 2 W 0 2 3 (n √ σ 0 ) 4 3
Using that W 0 is the solution to f (x)e f (x) = x, we obtain that

σ 0 = 1 4 W 0 n 2 4 .
Then, for σ <

1 4 W 0 n 2 4
we have

nσ √ z 0 ≤ n σ 3 2 W 0 2 3 (n √ σ) 4 3 < n σ 0 3 2 W 0 2 3 n √ σ 0 4 3 = n 2
and t m = nσ √ z 0 . Notice that

P [p u i ∈ H i ∩ P r ] ≥ P [H i ∩ P r = ∅] P [H i ∩ (P \ P r ) = ∅] .
The two quantities on the right-hand side are independent.

Claim 2.4.12.

When 2 n 2 ≤ σ < 1 4 W 0 n 2 4 , P [P r ∩ H i = ∅] = Ω(1).
Proof. Note that z 0 is set so that

Q z 0 σ = Θ 1 tm = Θ √ z 0
nσ . Indeed, using Lemma 2.4.1 (i) and the fact that

z 0 = Ω(σ), Q z 0 σ = Θ e -z 2 0 2σ 2 z 0 σ
. The choice for z 0 comes from the resolution of the equation 1x e -x 2 2 = √ x n √ σ using the definition of the function W 0 .

Moreover, for |t| ≤ t m we have z t = Θ(z 0 ) and

z 2 t -z 2 0 = Θ t 2 z 0 n 2 . Indeed, σ ≥ 2 n 2 implies that z 0 = Ω(σ) and z t < z 0 + O t 2 m n 2 = O z 2 0 +σ 2 z 0 = O(z 0 ) and z t = z 0 + Θ t 2 n 2
= Ω(z 0 ). Also, z t = Ω(σ) so

1 z t σ + σ z t
= Ω σ zt . Injecting these relations into Equation (2.12) we obtain that the expected number of relevant points in H i is

Ω 1 t m tm t=-tm 1 zt σ + σ zt z 0 σ e -1 2σ 2 (z 2 t -z 2 0 ) = Ω 1 t m tm t=0 e -t 2 Θ( z 0 n 2 σ 2 ) . Again, Lemma 2.4.1 (iii-b) ensures that tm t=0 e -t 2 Θ( z 0 n 2 σ 2 ) = Ω nσ √ z 0
and the expected number of relevant points in H i is Ω(1). The Chernoff bound of Lemma 2.2.1 (a) yields that P [H i ∩ P = ∅] is Ω(1).

It remains to bound the third quantity:

Claim 2.4.13. When 2 n 2 ≤ σ < 1 4 W 0 n 2 4 , P [H i ∩ (P \ P r ) = ∅] = Ω(1).
Proof. Every irrelevant point p t belongs to H i with probability Q zt σ . The probability that H i contains no irrelevant point is therefore at least

  n-1 2 t=tm+1 1 -Q z t σ   2
Lemma 2.4.1 (i) and the fact that

z t = z 0 + Θ t 2 n 2 ensure that 1 -Q z t σ ≥ 1 -Q z 0 σ e -1 2σ 2 (z 2 t -z 2 0 ) = 1 -Q z 0 σ e -t 2 Θ( z 0 n 2 σ 2 )
so the probability that H i contains no irrelevant point is at least

γ =   n-1 2 t=tm+1 1 - 1 t m e -t 2 Θ 1 t 2 m   2 .
Taking the logarithm, and using ln(1x) ≥ -2x for x ∈ [0, 1], we get

-ln γ = -2 n-1 2 t=tm+1 ln 1 - 1 t m e -t 2 Θ 1 t 2 m ≤ 4 t m n-1 2 t=tm+1 e -t 2 Θ 1 t 2 m ≤ 4 t m n-1 2 t=0 e -t 2 Θ 1 t 2 m
and Lemma 2.4.1 (iii-a) yields 0 ≤ln γ ≤ O(1). It follows that the probability that H i contains no irrelevant point is at least e -O(1) = Ω(1).

Wrapping Up. We can now obtain our lower bound.

Proof of Theorem 19. Lemma 2.4.4 and the preceding analysis ensure that the assumptions of Theorem 10 (ii) are satisfied, and we thus have E [card CH(P )] = Ω (min (n, h 1 /w 1 )). We treat separately the three regimes.

If σ < 2 n 2 then E [card CH(P )] = Ω min n, 1 O 1 n 2 = Ω(n)
which is the first regime announced in Theorem 19. (Note that the boundaries between the regimes can be set up to a multiplicative constant.)

If 2 n 2 ≤ σ < 1 4 W 0 n 2 4 then E [card CH(P )] = Ω      1 + σ ln (n √ σ) √ σ √ σ + 1 4 ln (n √ σ)     
We simplify this expression by comparing σ and

1 ln (n √ σ) . Specifically, if σ ≤ 1 √ ln n then σ = O 1 ln (n √ σ) and E [card CH(P )] = Ω 4 ln (n √ σ) √ σ
which is the second regime announced in Theorem 19.

If 1 √ ln n ≤ σ < 1 4 W 0 n 2 4 = O √ ln n then 1 ln (n √ σ) = O(σ)
and

E [card CH(P )] = Ω σ ln (n √ σ) σ = Ω ln n √ σ = Ω √ ln n If σ ≥ 1 4 W 0 n 2 4 = Ω √ ln n then E [card CH(P )] = Ω   1 + σ W 0 n 2 4 σ + 1   = Ω √ ln n
The lower bound is the same as in the case 1

√ ln n ≤ σ < 1 4 W 0 n 2 4 .
Merging the two conditions we obtain that

σ ≥ 1 √ ln n ⇒ E [card CH(P )] = Ω √ ln n
which is the third regime announced in Theorem 19.

Gaussian Perturbation of a Regular Polygon: An Upper Bound

In Section 2.4.3, we proved a lower bound on the smoothed complexity of convex hull with Gaussian perturbations, see Theorem 19. In this section, we prove that this lower bound is almost tight for this specific configuration of points (a regular polygon). By almost, we mean that the lower bound is tight up to some small intervals of σ. We believe that theses gaps are just a technical issue due to our technique.

Theorem 20. Let P * = {p * i , 1 ≤ i ≤ n} be the set of vertices of a regular n-gon of radius 1 in R 2 . Let P = {p i = p * i + η i } where η 1 , η 2 , . . . , η n are random vectors in R 2 chosen independently from N (0, σ 2 I 2 ). The expected number of vertices of the convex hull of P is

Range of σ 0, 2 ln 4 n n 2 2 ln 4 n n 2 , 1 √ ln n 1 √ ln n , +∞ E card H (1) O(n) O 4 √ ln(n √ σ) √ σ O √ ln n
Using Theorem 19 and Theorem 20 we get the following estimation:

Range of σ 0, 1 n 2 1 n 2 , 2 ln 4 n n 2 2 ln 4 n n 2 , 1 √ ln n 1 √ ln n , +∞ E card H (1) Θ(n) O(n), Ω 4 √ ln(n √ σ) √ σ Θ 4 √ ln(n √ σ) √ σ Θ √ ln n
Note that we can suppose σ > 2 ln 4 n n 2

since otherwise the upper bound is trivial. The chosen parameters are similar to Section 2.4.3 (and so are some arguments in the proof), but in this case we need to define ℓ = ln 2 n levels of witnesses and collectors.

Parameter Setting. We set h j and w j depending on σ and n as summurized below. We let u 1 , u 2 , . . . , u m denote a family of vectors in S 1 such that u i is aligned with p * ⌊ 2πi m ⌋ , so these vectors are more or less equally spaced on S 1 . The witnesses are defined as W j i = W (w i , h i , u i ) and the collectors are defined as

C j i = C(w j , h j , u i , α). 2 ln 4 n n 2 ≤ σ < 1 4 W 0 n 2 4j 2 1 4 W 0 n 2 4j 2 ≤ σ w j 2σ + 2 √ σ 3 2 W 0 2 3 n j √ σ 4 3 -1/4 2σ + 2 h j 1 + σ 3 2 W 0 2 3 n j √ σ 4 3 1 + σ W 0 n 2 4j 2 α Θ σ h 0 -1+ √ h 0 -1 Θ σ h 0 -1+ √ h 0 -1
Preparation. Let i ∈ {1, . . . , m}. As in Section 2.4.3, we let (O, v i , u i ) denote some orthonormal frame and let H j i the halfplane supporting W j i , with inner normal u i . We renumber the points of P * with indices in {-n-1 2 , . . . , n-1 2 } so that p * 0 is the point in direction u i . For the sake of presentation, we assume that n is odd (the case of even n follows from trivial modification). Our goal is to show that E card W j i ∩ P = Θ(j) and that E card C j i ∩ P = O(j). Let j ∈ {1, . . . , ℓ}. We write z t for the distance from p * t to H j i and note that

z 0 = h j -1 and z t = h j -1 + 1 -cos 2πt n
Same argument as Equation 2.9 gives z tz 0 = Θ t 2 n 2 .

Relevants Points. The contribution of the t-th point to E card H j i ∩ P is Q zt σ . The gist of our analysis for larger σ is to split the points into two parts, the relevant points where Q zt σ = Θ Q z 0 σ and the irrelevant ones. The expected number of points in H j i is (up to a constant multiplicative factor) at least the number of relevant points times Q z 0 σ ; fine tuning z 0 so that this product is Ω(1) then amounts to solving some functional equation. Also, we need to show that the contribution of the irrelevant points are negligeable. Specifically, we call a point p t

relevant if |t| ≤ t m = min nσ √ z 0 , n-1 2
. A relevant point in H j i is in W j i with constant probability, since the width of the witness is chosen to enclose B(p * , σ) in v i direction, when p is relevant. Thus, E card

W j i ∩ P = Ω E card W j i ∩ P . Since W j i ⊂ H j i , we get E card W j i ∩ P = Θ E card H j i ∩ P .
Counting points in H j i . A first step to compute the expected number of points in W j i is to compute the expected number of points in H j i . The expected number of points in H j i writes

E card H j i ∩ P = n-1 2 t=-n-1 2 Q z t σ = Θ   n-1 2 t=0 1 zt σ + σ zt z 0 σ e -1 2σ 2 (z 2 t -z 2 0 )   (2.13) Intermediate σ When 2 ln 4 n n 2 ≤ σ < 1 4 W 0 n 2 4j 2
we have

z 0 = σ 3 2 W 0 2 3 n j √ σ 4 3
.

The function x → x 3 2 W 0 2 3 ( n j √ x) 4 3
is increasing. Let us define σ 0 as the solution of

σ 0 = 1 4 3 2 W 0 2 3 n j √ σ 0 4 3
Using that W 0 is the solution to f (x)e f (x) = x, we obtain that

σ 0 = 1 4 W 0 n 2 4j 2 .
Then, for σ <

1 4 W 0 n 2 4j 2 we have nσ √ z 0 ≤ n σ 3 2 W 0 2 3 n j √ σ 4 3 < n σ 0 3 2 W 0 2 3 n j √ σ 0 4 3 = n 2
and t m = nσ √ z 0 .

Claim 2.4.14.

When 2 ln 4 n n 2 < σ < 1 4 W 0 n 2 4j 2 , E card H j i ∩ P = Θ(j).
Proof. Note that z 0 is set so that

Q z 0 σ = Θ j tm = Θ j √ z 0 nσ
. Indeed, using Lemma 2.4.1 (i) and the fact that z 0 = Ω(σ),

Q z 0 σ = Θ e -z 2 0 2σ 2 z 0 σ
. The choice for z 0 comes from the resolution of the equation 1x e -x 2 2 = √ x n √ σ using the definition of the function W 0 .

Moreover, for |t| ≤ t m we have z t = Θ(z 0 ) and

z 2 t -z 2 0 = Θ t 2 z 0 n 2 . Indeed, σ ≥ 2 ln 4 n n 2 ≥ 2j 2 n 2 implies that z 0 = Ω(σ) and z t < z 0 +O t 2 m n 2 = O z 2 0 +σ 2 z 0 = O(z 0 )
and

z t = z 0 + Θ t 2 n 2
= Ω(z 0 ). Also, z t = Ω(σ) so

1 z t σ + σ z t = Θ σ zt .
Injecting these relations into Equation (2.13) we obtain that the expected number of relevant points in H j i is

Ω j t m tm t=0 1 zt σ + σ zt z 0 σ e -1 2σ 2 (z 2 t -z 2 0 ) = Ω j t m tm t=0 e -t 2 Θ( z 0 n 2 σ 2 ) . Again, Lemma 2.4.1 (iii-b) ensures that tm t=0 e -t 2 Θ( z 0 n 2 σ 2 ) = Ω nσ √ z 0
and the expected number of relevant points in H j i is Ω(j). Same arguments yields the upper bound

E card H j i ∩ P = O j t m n t=0 e -t 2 Θ( z 0 n 2 σ 2 ) = O j t m 1 + nσ √ z 0 = O(j)
using Lemma 2.4.1 (iii-a), since z 0 = Ω(σ 2 ).

Large σ When σ ≥ 1 4 W 0 n 2 4j 2 , every point is relevant, ie. t m = n-1 2 , since z 0 = σ W 0 n 2 4j 2 implies nσ √ z 0 = n σ W 0 n 2 4j 2 ≥ n 2 . Claim 2.4.15. When σ ≥ 1 4 W 0 n 2 4j 2 , E card H j i ∩ P = Θ(j).
Proof. Computations similar to that of Equation (2.6) yield that

Q z 0 σ = Θ j n . Moreover, z t ≥ σ 2 so 1 z j σ + σ z j
= Θ σ z j . Also, z t = Θ(z 0 ) and z 2 tz 2 0 = Θ t 2 z 0 n 2 . Injecting these three relations in Equation (2.12) we obtain that the expected number of (relevant) points in H i writes

E card H j i ∩ P = Θ   j n n-1 2 t=0 z 0 z t e -t 2 Θ( z 0 n 2 σ 2 )   = Θ   j n n-1 2 t=0 e -t 2 Θ( z 0 n 2 σ 2 )   Since z 0 n 2 σ 2 < 4 n 2 , Lemma 2.4.1 (iii-c) implies that n-1 2 j=0 e -j 2 Θ( z 0 n 2 σ 2 ) = Ω(n),
so we finally get that H i contains Ω(j) (relevant) points on average. The upper bound comes trivially since e -j 2 Θ( z 0 n 2 σ 2 ) = O(1).

We then conclude that for σ > 2 ln 4 n n 2 , E card W j i ∩ P = Θ(j). It remains to control the expected number of points in the collector.

Couting points in C j i .

Claim 2.4.16. Let σ > 2 ln 4 n n 2 . Then, E card C j i ∩ P = O(j). Proof. The collector C j i is the union of two halfplanes of height hj . The contribution of a halfplane depends only on its height and to compute the contribution to the collector, we compute the contribution to a halfplane Hj i parallel to H j i of height hj . This contribution will be computed separately for relevant and irrelevant points.

As above z t denote the distance of p * t to H j i and we denote zt its distance to H. Let's first consider the contribution of the relevant points. We suppose without loss of generality that Hj i corresponds to the half-plane on the left of u i , and we consider only the relevant points on the left side {p 0 , . . . , p tm }. The contribution of the relevants points on the right side will be trivially bounded by the contribution of the left-sided relevant points. Using Claim 2.4.3, we get that for 0 ≤ t ≤ t m ,

zt = z t cos α 2 -sin α 2 w j +Θ( t n ) 2 .
In the large σ settings, w j > 1 so tm nw j < 1. For the intermediate σ settings,

tm n = σ √ z 0 and tm nw j = σ 2σ √ z 0 1+ 1 √ z 0 ≤ 1 1+ √ z 0 < 1, since w j = 2σ 1 + 1 √ z 0 .
Thus,

z t ≤ zt + z t 1 -cos α 2 + α(w j + C 1 tm n ) 4 ≤ zt + αw j 4 1 + (C 1 tm n ) w j + z t α 2w j ≤ zt + αw j 4 (C 1 + 2) if we choose α ≤ σ C(h 0 -1))(1+ 1 √ h 0 -1
) with C > zt m z 0 (remember that z tm = Θ(z 0 )) and C 1 > 0 some constants.

In particular, since w j < 4σ 1 + 1 √ z 0 we have

z t σ ≤ zt σ + α(C 1 + 2) 1 + 1 √ z 0 . We choose α = σ C 2 (h 0 -1)(1+ 1 √ h 0 -1 ) with C 2 = C(C 1 + 2). Since zt ≤ ztm < z tm < Cz 0 ≤ C(h 0 -1), Q z t σ ≥ Q zt σ + (C 1 + 2)α 1 + 1 √ z 0 ≥ Q zt σ + σ C(h 0 -1)(1 + 1 √ h 0 -1 ) 1 + 1 √ z 0 ≥ Q   zt σ + σ Cz 0 1 + 1 √ z 0 1 + 1 √ z 0   = Q zt σ + σ Cz 0
and since zt ≥ 1 4 σ we conclude by

Q zt σ + σ Cz 0 ≥ Q zt σ + σ zt = Ω Q zt σ using Lemma 2.4.1 (ii). Thus, Q zt σ = O Q z t
σ and the contribution of relevant points to the collector is bounded, up to a constant, by the contribution of relevant points to the witness.

Taking the above formula with t = t m gives that

Q ztm σ = O Q zt m σ . Since we chose t m so that Q zt m σ = Θ Q z 0 σ , we obtain Q ztm σ = O Q z 0 σ
. Basic circle geometry gives that zim+jzim > z jz 0 and thus the contribution of irrelevant points to Hj i is bounded by the contribution of all points to H j i which is O(j).

Wrapping up. With the chosen parameter, Theorem 10 (i) applies and E H (1) =

E [card CH(P )] = O 1 α . Notice that for 1 √ ln n < σ < 1 4 W 0 n 2 4j 2 , 1 α = O h 0 σ = O √
ln n , which is the same behavior as the case where σ >

1 4 W 0 n 2 4j 2 . Thus, for σ > 1 √ ln n , we get 1 α = O 1 √ ln n . For 2 ln 4 n n 2 < σ < 1 √ ln n , 1 α = O √ h 0 σ = O 4 ln(n √ σ) σ
. This finishes the proof of Theorem 20.

Theorem 10 is established for a set of n independent elements. Except for some technicalities in the presentation, nothing prevents making n a random variable to prove eg. analogs of Theorems 11 and 16 for Poisson distributions. (As this was not required for our application to smoothed complexity analysis, we opted for a simpler presentation where n is fixed.)

Silhouette of Polytopes

Glisse, Lazard, Michel and Pouget [START_REF] Glisse | Silhouette of a random polytope[END_REF] used the witness and collector approach to study the expected size of the silhouette of a 3D random convex polytope defined as the convex hull of a Poisson point process of intensity n on the unit sphere.

The silhouette of the polytope from a given viewpoint is the two dimensional convex hull of the projection of the points, thus the problem reduces to the size of the convex hull of i.i.d. points in a disk for the distribution corresponding to the projection of a Poisson point process. Glisse et al. analyzed the size of that convex hull using a system of witnesses and collectors adapted to that distribution and proved that the worst point of view yields a silhouette of expected size Θ ( √ n).

ℓ ∞ Perturbation and Snap-Rounding

Systems of witnesses and collectors can be designed for perturbations that are uniform in the ball for other metrics. In [START_REF] Attali | The Effect of Noise on the Number of Extreme Points[END_REF], denoting the unit square in 2D, we prove the following theorem:

Theorem 21. Let P * = {p * i : 1 ≤ i ≤ n} be an (Θ (n) , Θ(1))-sample of the unit circle in R 2 and let P = {p i = p * i + η i } where η 1 , η 2 , . . . , η n are random variables chosen independently from U δ . For any fixed k, and δ ∈ [n -2 , 1]

E card H (k) = Θ n 1 5 δ -2 5
As in the Euclidean case, the witnesses and collectors are parallel half planes, but the partition of ranges must be adapted to cope with the lack of rotational symmetry. The angle α i of the set of directions covered by R i is no longer constant and is much smaller when the ranges are almost horizontal or vertical than when they are oblique. The bound of Theorem 21 is confirmed experimentally (cf. the slopes of -2 5 in the plots of Figure 2.3a). Theorem 21 implies that for δ ∈

[n -2 , 1], S(n, U δ ) is Ω n 1 5 δ -2 5
. It is also known to be O n ln n δ 2 3 , for all ranges of δ, by the upper bound obtained by Damerow and Sohler for maximal points under ℓ ∞ noise [START_REF] Damerow | Extreme points under random noise[END_REF].

Snap Rounding. Given a grid whose pixel have size δ, rounding points with real coordinates at the center of their pixel have some similarity with ℓ ∞ noise. Actually, for a single point, and if the origin of the grid is random, the two processus are identical, but when several points are involved things are different: clearly rounding creates collisions while noising separates identical points. However for the regular n-gon, provided that δ < 1 n the two processes give convex hulls of similar size as confirmed by Figure 2.3b.

Delaunay Triangulation

Systems of witnesses and collectors can also be used to prove the following well known result of Dwyer [START_REF] Dwyer | The expected number of k-faces of a Voronoi diagram[END_REF]:

Theorem 22 (Dwyer [START_REF] Dwyer | The expected number of k-faces of a Voronoi diagram[END_REF]). The expected complexity of the Delaunay triangulation of n random points uniformly distributed in the unit ball B of dimension d is Θ(n).

In [START_REF] Devillers | Complexity analysis of random geometric structures made simpler[END_REF], Devillers et al. gave a proof, considerably simpler than Dwyer's, of this result up to logarithmic factors; these factors can be removed thanks to Theorem 10 using a system of witnesses and collectors that we now outline.

The faces of dimension k of the Delaunay triangulation are hyperedges of size k + 1 in the hypergraph where the ranges are balls in R d . More precisely, given a set P of n points in general position, k + 1 points define a face of the Delaunay triangulation DT (P ) iff there exists a ball with the k + 1 points on its boundary and no other points inside. Thus the hypergraph define using the balls as ranges may be a strict superset of the Delaunay faces. The proof splits the ranges in three subsets and builds a system of witnesses and collectors for each these subsets.

Balls Centered Deep Inside B. Let r j = O j n 1 d
denote the radius of a ball completely contained in B and expected to contain j points. We use a minimal covering of B with balls of radius r 1 and keep the balls centered inside (1-r 1 ln 2 n)B to define our first level witnesses W 1 i . We define W j i as the ball concentric with W 1 i with radius r j , and C j i as the ball concentric with W j i with radius r j + 2r 1 . We finally let R i be the set of balls centered in W 1 i . This system of witnesses and collectors verifies the hypotheses of Theorem 10 (i), and a constant fraction of the first layer {(W 1 i , C 1 i )} i verifies the hypotheses of Theorem 10 (ii). Altogether, they allow to conclude that the number of Delaunay balls centered in (1r 1 ln 2 n)B is Θ(n). Balls Centered Near ∂B. The Delaunay balls centered in an annulus of width 2r 1 ln 2 n around ∂B can be counted easily since their number is sublinear. To this aim we can cover the above annulus by collectors of diameter O(r 1 ln 2 n) and use associated empty witnesses.

Balls Centered outside B. Balls centered outside B are a bit more delicate, since they can have a large radius but, possibly, a small probability to be empty. A first remark is that ball of infinite radius are half-plane and are counted by Theorem 11.

Actually, the construction of Theorem 11 can be adapted to count all balls of radii between α and 2α by using balls of radius α to define the witnesses and balls of radii 2α for the collectors. Then it is possible to sum on various values of α to cover all the possible radii. As a side result we get the expected size of the α-shape of points uniformly distributed in B.

Introduction

Consider a sequence of points in a convex body in dimension d whose convex hull is dynamically maintained when the points are inserted one by one, the convex hull size may increase, decrease, or remain constant when a new point is added.

Studying the expected size of the convex hull when the points are evenly distributed in the convex is a classical problem of probabilistic geometry that yields some surprising facts. For example, although it seems quite natural to think that the expected size of the convex hull is increasing with n the number of points, this fact is only formally proved for n large enough [START_REF] Devillers | The monotonicity of f-vectors of random polytopes[END_REF]. The asymptotic behavior of the expected size is known to be polylogarithmic for a polytopal body and polynomial for a smooth one. If for a polytope or a smooth body, the asymptotic behavior is somehow "nice", for "most" convex bodies the behavior is unpredictable [7, corollary 3]. It is possible to construct strange convex objects that have no such nice behaviors and this note exhibits a convex body, such that the behavior of the expected size of a random polytope oscillates between the polytopal and smooth behaviors when n increases. More formally, let K be a convex body in R d and (x 1 , . . . , x n ) a sample of n points chosen uniformly and independently at random in K. Let K n be the convex hull of these points and f 0 (K n ) the number of vertices of K n .

It is well known [START_REF] Bárány | Random points and lattice points in convex bodies[END_REF][START_REF] Reitzner | Random polytopes[END_REF] that if P is a polytope, then

E [f 0 (P n )] = c d,P ln d-1 n + o(log d-1 n) (3.1)
and if K is a smooth convex body (i.e with C 2 boundary with a positive Gaussian curvature), then For general convex bodies, we cannot expect such a beautiful formula.

E [f 0 (K n )] = c d,K n d-1 d+1 + o(n d-1 d+1 ) ( 3
Theorem 23 (Bàràny-Larman [START_REF] Bárány | Intrinsic volumes and f -vectors of random polytopes[END_REF]). For any function G(n) → n→∞ ∞ and for most (in the Baire category sense) convex bodies

K in R d , G(n) ln d-1 n > E [f 0 (K n )]
for infinitely many n and

G(n) -1 n d-1 d+1 < E [f 0 (K n )]
for infinitely many n.

Note that this "most" does not contain convex polytopes and smooth convex bodies, which are the most used in practice.

In this chapter, we present an explicit example of a convex body which has this chaotic behavior.

Notations. Let's introduce some notations used in this chapter:

• K ⊕ L will denote the Minkowski sum of K and L, defined as

J ⊕ K = {x + y |x ∈ J, y ∈ K};
• d H (J, K) will denote the Hausdorff distance of the convex bodies K and L, defined as

d H (J, K) = min{r ∈ R + |J ⊂ K ⊕ B, K ⊂ J ⊕ rB}
where B is the Euclidean unit ball in R d .

Approximations of Convex Bodies

In this section, we present an intermediate lemma about random polytopes of close (in terms of Hausdorff distance) convex bodies. Let K be a convex body in R d and K n be a random polytope in K. We want to show that if L is an approximation of K with small Hausdorff distance, L n is approximating the asymptotic behavior of K n for some value of n.

Let's assume that the expected size of K n is in c d,K g(n, d) + o(g(n, d)), where c d,K is a constant and g some function.

Then, for every close-enough compact set L containing K, L n has an expected size as close as we want from c d,K g(n, d) for values of n as big as we want. The idea of this lemma is very simple: if L is very close to K, the volume in L \ K is small, and points chosen uniformly in L are very unlikely to be in L \ K. Then, even if asymptotically the expected size of L n is different from the size of K n , there exists some n where the expected size of L n is as close as we want to c d,K g(n, d).

K ⊕ αB L K α Lemma 3.2.1. Let K be a convex body in R d such that E [f 0 (K n )] = c d,K g(n, d) + o(g(n, d)). (3.3)
Let ε > 0 and N ∈ N.

Then, there exist p > N and α > 0 such that for any compact set

L containing K with d H (K, L) < α, E [f 0 (L p )] c d,K g(p, d) ∈ [1 -ε, 1 + ε]. Proof. First, for all n ∈ N * E [f 0 (L n )] = P [L n ⊂ K] E [f 0 (L n )|L n ⊂ K] + P [L n ⊂ K] E [f 0 (L N )|L n ⊂ K] .
As the points are uniformly distributed,

E [f 0 (L n )|L n ⊂ K] = E [f 0 (K n )]. Using (3.3), let's choose p such that E [f 0 (K p )] c d,K g(p, d) ∈ 1 - ε 2 , 1 + ε 2 , (3.4)
then

P [L p ⊂ K] E [f 0 (L p )| L p ⊂ K] c d,K g(p, d) ≤ 1 + ε 2 . As P [L p ⊂ K] = 1 -P [L p ⊂ K] = 1 - vol (K) vol (L) p we get P [L p ⊂ K] E [f 0 (L p )| L p ⊂ K] ≤ 1 - vol (K) vol (L) p p. Now, as 1 ≥ vol(K) vol(L) ≥ vol(K) vol(K⊕Bα) → α→0 1 we can choose α such that vol (K) vol (L) p ≥ max 1 -c d,K g(p, d) p ε 2 , 1 - ε 2 . (3.5)
Finally,

E [f 0 (L p )] ≤ c d,K g(p, d) 1 + ε 2 + c d,K g(p, d) ε 2 = c d,K g(p, d)(1 + ε). (3.6)
For the lower bound, using Inequalities (3.4) and (3.5) we get

E [f 0 (L p )] ≥ P [L p ⊂ K] E [f 0 (L n )| L n ⊂ K] ≥ c d,K g(p, d) vol (K) vol (L) p (1 - ε 2 ) ≥ c d,K g(p, d) vol (K) vol (L) p - ε 2 ≥ c d,K g(p, d) 1 - ε 2 - ε 2 = c d,K g(p, d)(1 -ε).
(3.7)

Inequalities (3.7) and (3.6) prove the lemma.

Construction of the Convex Body

Given an increasing function G, we want to construct a convex body in R d where the size of a convex hull of random points has a chaotic behavior between ln d-1 n and n d-1

d+1 on some values arbitrarily big. More formally, Theorem 24. Let G : N * → R * + an increasing function such that G(n) → n→∞ ∞. We can construct a convex body K such that: For all N ∈ N * , there exist M 1 , M 2 > N , where Proof. The main idea of the proof is, starting from a convex body K (0) , to iterate smooth and polytopal approximations. Lemma 3.2.1 will give us some number of points where the behavior of the random convex body will be very close to n d-1 d+1

E [f 0 (K M 1 )] < G(M 1 ) ln d-1 M 1 and E [f 0 (K M 2 )] > G(M 2 ) -1 M d-1 d+1 2 . K (0) K (0) ⊕ B β0 K (1) K (1) ⊕ B β1 K (2)
(which is the behavior for smooth convex bodies) or very close to ln d-1 n (which is the behavior for polytopes).

Iterations. We create an increasing sequence of convex bodies starting from the unit ball, made of polytopal and smooth approximations. Let's define K (0) as the unit ball. For all n ∈ N * , K (n) is an approximation of K (n-1) where d H (K (n-1) , K (n) ) < β n-1 , with (β i ) i∈N some decreasing sequence, as shown in Figure 3.1.

• If n is odd, K (n-1) is a smooth convex body, so K (n) is a convex polytope.

Let's choose q n > n, such that

E f 0 (K (n-1) qn ) q d-1 d+1 n > 2 G(q n ) .
We define

ε n = 1 - 2 c d,K (n-1) G(q n ) . (3.8)
Using Lemma 3.2.1,with ε = ε n , there exist α n-1 and p n > q n such that for every compact set L containing K

(n-1) with d H (K (n-1) , L) < α n-1 , E [f 0 (L pn )] > c d,K (n-1) p n d-1 d+1 (1 -ε n ). (3.9)
Therefore,

E [f 0 (L pn )] > c d,K (n-1) p n d-1 d+1 (1 -ε n ) > p n d-1 d+1 G(q n ) -1 > p n d-1 d+1 G(p n ) -1 . (3.10) Now let's define β n-1 = min( α n-1 2 , β n-2 2 ) if n > 1 and β 0 = α 0 2 . We define K (n) as a convex polytope with d H (K (n-1) , K (n) ) < β n-1 , so (3.10) works for L = K (n) . • If n is even, K (n-1) is a convex polytope, so K (n) is a smooth approximation. Let's choose q n such that E f 0 (K (n-1) qn ) ln d-1 q n < G(q n ) 2
and define

ε n = G(q n ) 2c d,K (n-1) -1.
Using Lemma 3.2.1 with ε = ε n , there exist α n-1 and p n > q n such that for every compact set with d H (K (n-1) , L) < α n-1 ,

E [f 0 (L pn )] < c d,K (n-1) ln d-1 (p n )(1 + ε n ).
Finally,

E [f 0 (L pn )] < G(q n ) ln d-1 (p n ) < G(p n ) ln d-1 (p n ). (3.11)
Again, we define β n-1 = min( α n-1 2 , β n-2 2 ). We define K (n) as a smooth approximation of K (n-1) such that d H (K (n-1) , K (n) ) < β n-1 , so (3.11) works for L = K (n) .

Note that for all m > n ∈ N,

d H (K (n) , K (m) ) ≤ m-1 k=n d H (K (k) , K (k+1) ) < m-1 k=n β k ≤ m-n-1 k=0 β n 2 k ≤ 2β n ≤ α n .
That means for all m > n, the property (3.10) or (3.11) (depending on the evenness of n) are also true for K (m) . Now, defining K = ∪ ∞ i=0 K (i) , the property (3.10) and (3.11) are true for arbitrary n ∈ N with L = K, by considering K (n) and K (n+1) . As we can choose q n as big as we want for any n (it will just decrease α n-1 ), we can choose this sequence to be increasing. As a result, E [f 0 (K n )] will have a chaotic behavior within n d-1 d+1 /G(n) and G(n) ln d-1 n, as shown in Figure 3

.2. n E [f 0 (K n )] n d-1 d+1 n d-1 d+1 G(n) G(n) ln d-1 n ln d-1 n p 4 E f 0 (K (3)
p 4 ) E f 0 (K (4)

Concluding remarks

We have constructed a convex body K such that the expected size of the convex hull of a random polytope in K has a chaotic behavior. This construction is the limit of a sequence of bodies (K (i) ) that alternate polytopes and smooth shapes so it is difficult to provide an explicit description of K, in this note we just show that constructing such a sequence is possible by a repeated application of Lemma 3.2.1 but there is no obstacle, except long and painful computations, to a more constructive version with explicit description of the sequence. Notice that in such a case the complexity of K (i) will be increasing quite rapidly. Actually, since K (i) is constrained in a slab of width β i around K (i-1) , the size of K (i) can be lower bounded for polytopes, see [START_REF] Böröczky | Polytopal approximation bounding the number of k-faces[END_REF]:

|K (i) | = Ω β -d-1 2 i
and since β i < α 0 2 i we get, at least, an exponential behavior for the size of K (i) . Even with a constructive description of the K (i) , the description of K as the limit of the K (i) will remain quite abstract, but will allow to develop a membership test, given a point p, p ∈ int(K) can be decided by computing the sequence K (i) up to an index where p ∈ K

(i) or p ∈ K (i) ⊕ β i B.

Introduction

Let D be a disk in R 2 with radius R centered at o, and X 1 , . . . , X n be a sample of n points uniformly and independently distributed in D. Let's define the polygon K n as the convex hull of X 1 , . . . , X n , and f 0 (K n ) its number of vertices. This kind of polygon has been well studied, and using [START_REF] Bárány | Random polytopes in smooth convex bodies[END_REF][START_REF] Reitzner | Random polytopes[END_REF] one can easily check that

E [f 0 (K n )] = c n 1 3 + o(n 1 3 ) (4.1)
where c = 2

4 3 3 -1 3 Γ( 5
3 )π 5 3 ≈ 3.383228964 and Γ denotes the usual Gamma function. To generate such a polygon, one can explicitly generate n points uniformly in D and compute the convex hull. For a very large number of points, it could be interesting to generate fewer points to get the same polygon, for example to evaluate the constant that are not explicitly known for the asymptotic distribution of the perimeter, or other parameters such as the higher moments of the extremal points.

In this chapter, we propose an algorithm that generates far fewer points at random in order to get K n , so that the time and the memory needed is reduced for n large.

Algorithm

We start with random polygon K i in D where i is very small, and we increase the number of points until we get K n . The idea is that given the convex hull of small number of points, the number of points generated in D that are deeply inside (and so will not change the convex hull) is a random variable that we can easily simulate, so that we need to generate only the small number of points that are close to the convex hull. The outline of the algorithm is the following:

• Generate a small number of points in D and compute its convex hull;

• Compute the radius of the largest disk centered at o inscribed in the convex hull;

• Choose a number of points to simulate at this step;

• Simulate the number of points that fall in this inscribed disk at this step;

• Generate the rest of the random points in the annulus defined by these two discs and update the convex hull.

• continue this process until the sum of the simulated and generated points is equal to n.

To simplify the notations, we assume D to have radius 1.

Notations.

• n is the total number of points simulated and m i is the total number of points from step 1 to step i;

• k i is the number of generated points at step i, and k = i k i is the total number of generated points;

• h i is size of the convex hull at step i, and h is the size of the final convex hull.

• p i is the probability to fall in the annulus at step i.

Initialization. First, we have to generate a random polytope K i with a small number of points in D such that o is inside the random polytope. This is not too much to ask, as (see [3])

P [o ∈ K i ] = 2 -(i-1) i (4.2)
We initialize the random polygon by generating 100 points in the disk. As the probability that o ∈ K 100 is lower than 1.6 × 10 -28 , it's very unlikely that this is not enough. Otherwise, we add another sample of 100 points, until 0 ∈ P 100.j for some j. At the beginning of each step i of the loop, we are given a polygon K m i , which is the convex hull of m i points. Let s i the number of new points simulated at step i. We choose s i = m i if m i < n ln -2 n, and s i = n ln -2 n otherwise. Let D i be the largest inscribed disk in K m i centered in o, and r i its radius.

Using a simulation of a binomial variable of parameter s i and 1r 2 i , we can evaluate the number of points that falls in D \ D i . As the points in D i will not change the convex hull, we do not need to generate them. Then, we generate the rest of the points uniformly in the annulus D \ D i , and we update the convex hull using a Graham scan.

Generation of Random Points. To generate random points in an annulus with radii r i and 1, one need to generate the polar angles uniformly in [-π, π) and the squared radii uniformly in [r 2 i , 1). As we want to perform a Graham scan in linear time, the points have to be sorted by their polar angles. This can be done in expected linear time and size, using a bucket sort, as the angles are uniformly chosen, see [START_REF] Cormen | Introduction to Algorithms[END_REF].

Complexity

Clearly the size complexity is max i (h i + k i ) and the time complexity is i (h i + k i ) since the Graham scan and the points generation are linear in the number of points [START_REF] Graham | An efficient algorith for determining the convex hull of a finite planar set[END_REF].

For the initialization, as the probability that 0 ∈ K n decreases exponentially, it is very unlikely that more than one loop is necessary. Let's call p the minimal number of points such that o ∈ K p . Using formula (4.2), the expectation of p is very small : For i large enough, we have [START_REF] Bárány | Intrinsic volumes and f -vectors of random polytopes[END_REF]:

E [p] =
E [d H (K m i , D)] = Θ ln m i m i 2 3 (4.4)
where d H , the Hausdorff distance, is the maximal distance between a point in K i and the boundary of D.

Recall that D i is the annulus with radii r i = 1d H (K m i , D) and 1 and let p i be the probability that a random point in D falls in D i . Using (4.4), there exist a constant c 0 > 0 such that, for i large ,

E [p i ] = 1 -r 2 i < 2(1 -r i ) < c 0 ln m i m i 2 3 .
Let' s call i τ the last step i where m i < n ln 2 n . At each step i ≤ i τ , k i is a binomial variable with parameter p i and m i < n ln 2 n . Thus, for i large enough, As we choose m i+1 = 2m i , i τ is bounded by log 2 (n).

E [k i ] = E [ E [k i | p i ]] = m i E [p i ] = O(m
For i > i τ , k i is a binomial variable with parameter p i and n ln 2 n , so using Equation (4.5) and the fact that m i > n ln 2 n , we get

E [k i ] = O(n 1
3 ).

As we simulate at each step i > i τ at least n ln 2 (n) , the number of step after i τ is bounded by ln 2 (n).

Now,

E [k] = iτ i=1 E [k i ] + i>iτ E [k i ]
≤ O ln + O(n

1 3 ln 2 n) = O(n 1 3 ln 2 n) (4.6)
At each step i, the expected size of the convex hull is O(m

1 3 i ) = O(n 1
3 ), and 3 ). Thus, using Chernoff bound, the expected size of the largest list, that is the expected size complexity, is O(n 1 3 ). As our points are sorted according to their polar angle, computing the convex hull with a Graham scan is done in linear time (O(n

E [k i ] = O(n 1

Experiments

This algorithm has been implemented in c++ and integrated into the cgal library.

As expected, the distribution of E [f 0 (K n )] is asymptotically the same as the theoretical one, see Equation (4.1), with the same constant, see Figure 4.2. This estimation has been done on 1000 experiments for each value of n.

Complexities. To evaluate the expected size complexity, we estimate the average size of the largest list of points used in the loop, see Figure 4.3. The time complexity can be evaluated by estimating the total number of points generated, see Figure 4.4.

As a first application, we can estimate the distribution of the smallest and the largest edge of a random polygon, see

Conclusion

We propose an algorithm that generates random polygons given by the convex hull of random points, without generating all the points. There is no theoretical obstacle to generalize to higher dimension. The theoretical results used for the evaluation of the complexity are known in arbitrary dimension [START_REF] Bárány | Intrinsic volumes and f -vectors of random polytopes[END_REF][START_REF] Reitzner | Random polytopes[END_REF], so the analysis can be done as well.

We can reduce the expected time complexity by a logarithmic factor if we allow to increase the expected size complexity by a logarithmic factor. Instead of bounding the simulated points at step i by n ln 2 n when m i becomes bigger than

Conclusion & Perspectives

We give new results on the complexity analysis of random convex hull. The Witness & Collector technique allows to capture the order of magnitude of the expected number of faces of a convex hull made of random points. These random points might be identically distributed: in this case we give an easier proof of classic results. They can also be a noisy version of an arbitrary set of points: this corresponds to the smoothed complexity.

We performed the smoothed analysis for two kind of perturbations. The first perturbation distribution is the uniform noise in a ball. This first analysis is new, and given in arbitrary dimension. The second one is the Gaussian perturbation: in this case we improve the results of the state of the art in dimension 2; we believe that this result can be generalized in higher dimensions.

For these two results, we provide an upper and a lower bound for the smoothed complexity. In the two cases, the lower bound does not match with the upper bound. The problem of having tight bounds is still open; however the case of large perturbations is tight, since it corresponds to the average-case magnitude.

The Witness & Collector technique can be applied for other structures based on hypergraphs; taking the ranges as balls of R d , the Delaunay triangulation average size can be estimated. An interesting question would be to bound the smoothed complexity under a given noise, for an arbitrary initial set of points. The technique works for a bad initial point set: if the points are on the moment curve t → (t, t 2 , t 3 ), it's possible to compute the noisy complexity under a uniform Euclidean noise. Is it possible to deal with an arbitrary initial set of points? If not, can we, at least, show that under large perturbations, the smoothed complexity corresponds to the average complexity?

Other geometric structures can be interesting to investigate. One example is the visibility complex of a set of n triangles in R 3 . The visibility complex encodes all the visibility informations of a 3D scene. In the worst case, its size is Θ(n 4 ), which makes the structure unusable. The worst-case seems, however, to be too pessimistic in practice; in particular for uniformly distributed unit balls the expected size is linear and for polygons or polyhedra of bounded aspect ratio [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF]. This would justify a smoothed analysis.

The asymptotic expected average number of vertices of a random polytope is known with high precision when the points are uniformly and independently chosen on a well shaped convex body. If the convex body is badly shaped, then it can be as unpredictable as we want. Actually, most of the convex bodies are badly shaped, however this notion of most does not include the convex bodies used and studied in practice. We give a construction of such a set, where the magnitude of the expected size oscillates between two regimes. This is an illustration of the fact that we cannot hope a good asymptotic formula for every arbitrary convex body.

We also propose an algorithm generating efficiently a random convex hull in a disk. We reduced the number of points to be generated, using the observation that, after generating a small number of points, a large region of the disk will not contain any of the extreme points. Generating efficiently random geometric objects can be interesting to study limit behaviors. It can also provide test case for algorithms, if the average-case analysis of the algorithm is not known. An open question, for example, would be to generate efficiently the convex hull of n points uniformly chosen, given the fact that the n points are in convex position. Since this event happens with a very small probability, a simple rejection algorithm is inneficient so generating such a structure when n is large is challenging.

These problems can be seen as special cases of the problem of sampling an object efficiently according to a given distribution µ. Several algorithms using Markov chains can solve (at least approximately) this kind of problem. However, computing the mixing time (that is, the number of steps before reaching the steady state distribution) can be difficult, and several interesting cases are still open.

Outline 1 . 1

 11 Stochastic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Sylvester's four-point problem . . . . . . . . . . . . . . . . . 6 1.1.2 Random polytopes . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Smoothed Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Smoothed Analysis of the Simplex Algorithm . . . . . . . . 11 1.2.3 Smoothed Analysis of the Gaussian Elimination . . . . . . . 12 1.2.4 Smoothed Analysis of the k-means Algorithm . . . . . . . . 14 1.3 Smoothed Analysis of Geometric Structures . . . . . . . . . . . . . 15 1.3.1 Smoothed Analysis of Visibility Map of Realistic Terrains . . 15 1.3.2 Smoothed Analysis of the Number of Extremal Points . . . . 16 1.1 Stochastic Geometry 1.1.1 Sylvester's four-point problem

  e) Expected complexity of a Gaussian perturbation P of a regular n-gon in R 2 (Theorem 19 and Theorem 20). The lower bound gives a lower bound on the smoothed complexity for Gaussian perturbation.

Figure 2 . 1 :

 21 Figure 2.1: Summary of our bounds.

  Our smoothed upper bound Our lower bound from sphere sample Lower bound from average-case 2 9

Damerow-

  Sohler smoothed upper bound Our smoothed upper bound Our lower bound on regular n-gon lim Lower bound from average-case (b) Comparison of the smoothed bounds for Gaussian perturbation in dimension 2 (Theorem 18 and

4 (

 4 c) Experimental results for the complexity of the convex hull of a perturbation of the regular n-gon inscribed in the unit circle. Left: Gaussian perturbation of variance σ 2 . Right: Euclidean perturbation of amplitude δ. Each data point corresponds to an average over 1000 experiments.

Figure 2 . 2 :

 22 Figure 2.2: Plots summarizing the main results.

  First assume that λt ≤ 2δ. Let ν d-1 denote the volume of a (d -1)dimensional ball of radius 1. By integrating along the direction of the inner normal to the half-space, we find

Lemma 2 . 3 . 8 .

 238 For δ ≥ 3n 2 d+1 we have S(n, U δB ) = Θ n d-1 d+1 .

Theorem 15 .

 15 Let d ≥ 2 be a constant andP * = {p * i : 1 ≤ i ≤ n} be an Θ n 1 1-d, Θ(1) -sample of the unit sphere in R d and let P = {p i = p * i + η i } where η 1 , η 2 , . . . , η n are random variables chosen independently from U δB . For any fixed

d-1 2 and h = Θ j n 2 d- 1 .O j n 2 d- 1 ,

 22121 The condition h > δ amounts to δ = giving the first regime.

  is called the Lambert function W 0 [15, Equation (3.1)]. For x ≥ 0 the definition of W 0 (x) is non-ambiguous and satisfies ∀x ≥ 1.01, W 0 (x) = Θ (ln x) .

O

  The assumptions ensure that|p * q * | = d(p * , W (w, h, u)) and |p * r * | = d(p * , C(w, h, u, α)). With v ∈ S 1 , v ⊥ u, we have |q * s * | = w 2 + | --→ Op * • v| tan α 2 and |p * r * | = |p * s * | cos α 2 = (|p * q * |-|q * s * |) cos α2and the statement follows.

2

 2

7 ( 7 (

 77 a) Experimental results for the complexity of the convex hull of a ℓ ∞ perturbation of amplitude δ of the regular n-gon inscribed in the unit circle. Each data point corresponds to an average over 1000 experiments. b) Experimental results for the complexity of the convex hull of a rounding of the regular n-gon inscribed in the unit circle on a grid of pixel size δ.

Figure 2 . 3 :

 23 Figure 2.3: Experimental results for the ℓ ∞ perturbation and rounding.

. 2 )

 2 where c d,P and c d,K are constants depending only on d and on the convex body. These are the two extreme behaviors : every random polytope of a convex body in R d has a behavior between (3.1) and (3.2) for n large enough[7, corollary 3].

Figure 3 . 1 :

 31 Figure 3.1: Iterations are made of polygonal and smooth approximations

p 5 ) p 5 Figure 3 . 2 :

 532 Figure 3.2: The expected size of the random polytope of K.

Chapter 4 A

 4 Generator of Random Convex Polygons in a Disk Outline 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Figure 4 . 1 :

 41 Figure 4.1: At step i, we simulate the number of points that falls in D i and we generate points uniformly in the yellow annulus

1 :

 1 integer n Result: Convex hull of n uniformly chosen points in the disk D Simulated_Points ← 0 ; do Generate min(100,n -Simulated_Points) points in the disk of radius 1; Simulated_Points ← Simulated_Points+min(100,n -Simulated_Points); while o is not in the convex hull and Simulated_Points < n; while Simulated_Points< n do Compute inscribed_radius; p ← inscribed_radius 2 ; if Simulated_Points < n ln -2 n then k ← Simulated_Points; else k ← min(⌊n ln -2 n⌋,n -Simulated_points); end X ← Simulation of Binomial variable with parameters k, 1p; Generate X points uniformly and sorted in the annulus of radii inscribed_radius, 1; Simulated_Points ← Simulated_Points + k ; Merge the list of the convex hull and the new points; Update the convex hull with a Graham scan on the list; end return Convex hull Algorithm Algorithm of the Generator of Random Polygon in a disk

  expected size and time complexity of the initialization is O(1).

1 3 1 3 1 3

 111 ln 2 n)), the generation of the k points and the computation of the largest annulus as well (O(n )). Thus, the expected time complexity is O(n log 2 n).

Figure 4 . 5 and

 45 Figure 4.6. The average have been done on 100 experiments for each value of n. The expected minimal edge seems to be O(n -1 3 ), and the maximal O ln 2

Figure 4 . 2 :

 42 Figure 4.2: Average size of K n divided by n 1 3

n ln 2 n 2 3

 22 , we can choose to always simulate m i points. In this case,E [k i ] = O(m n).On the other hand, the expected time complexity is reduced to O(n

Figure 4 . 3 :

 43 Figure 4.3: Average maximal size of the list divided by n 1 3

Figure 4 . 4 :n 1 3 ln 2 n 2

 4412 Figure 4.4: Average number of generated points divided by n 1 3 ln 2 n

Figure 4 . 5 :Figure 4 . 6 :

 4546 Figure 4.5: Average length of the minimal edge

  : Static Witnesses and Collectors . . . . . . . . . . 28 2.2.2 Proof of Theorem 10: Adaptative Witnesses and Collectors . 29 2.2.3 The Special Case of Convex Hulls . . . . . . . . . . . . . . . 31 2.2.4 Proofs of Lemmas 2.2.1 and 2.2.2 . . . . . . . . . . . . . . . 32 2.2.1 Principle: Static Witnesses and Collectors

  4.) The bound in Equation (2.1) is expressed in terms of the E card (C i ∩ P ) k but can be controlled by E [card (C i ∩ P )] since the elements of P are chosen independently: Lemma 2.2.2. If V = n i=1 V i , where the V i are independently distributed random variables with value in {0, 1} and E

  2.3.1 Preliminaries: Ball/Half-space Intersection . . . . . . . . . . 34 2.3.2 Witness-Collector Construction . . . . . . . . . . . . . . . . 35 2.3.3 Warm-up: Average-Case Analysis Made Easy . . . . . . . . 37 2.3.4 Upper Bounds on the Smoothed Complexity . . . . . . . . . 37 2.3.5 Lower Bound: Points in Convex Position . . . . . . . . . . . 41 Terminology and Notations. Let d ≥ 2 be a constant. We denote by ρB the ball of radius ρ centered at the origin of R d . Given X ⊂ R d we denote by vol

k (X) its k-dimensional volume and by ∂X its boundary. We say that two half-spaces are parallel if they have the same inner normal. The intersection depth of a half-space W and a ball p + δB is δ -d(p, W ), where d(p, W ) is the signed distance of p to ∂W (positive if and only if p / ∈ W ).

2.3.1 Preliminaries: Ball/Half-space Intersection

We denote by f (t, δ) the volume of the intersection of p+δB with a half-space that intersects it with depth t. Note that t → f (t, δ) is increasing on [0, 2δ] for any fixed δ.

Claim 2.3.1. For any λ ≥ 1 and any t ≥ 0, f (λt, δ) ≤ λ d+1 2 f (t, δ).

  for the covering of the set of half-spaces inR d by R 1 ∪ R 2 ∪ . . . ∪ R m .To apply Theorem 10 (i) it remains to control the expected number of points of P in the collectors.

	i , C j i )}1≤i≤m 1≤j≤ℓ proof of Lemma 2.3.4 readily implies that {(W j witnesses and collectors	is a system of

Claim 2.3.7. For any perturbed point p ∈ P , with card P ≥ 2 d+1 2 ,

  Claims 2.3.1 and 2.3.2 imply that P p ∈ W j i = Θ( j n ). By Claims 2.3.1 and 2.3.5 we get P p ∈ C j i = Θ( j n ) as well, so Theorem 10 (i) applies. A constant fraction of the W 1 i are pairwise disjoint, by Lemma 2.3.4, and E [card (W 1 i ∩ P )] = Ω(1). Using Claim 2.3.6, it follows that Theorem 10 (ii) also applies, and

  1 3 δn -2 d+1 . We partition P * into P * 1 ∪P * 2 ∪. . .∪P * m ′ by taking its intersection with each of the covering cells; we let P i denote the perturbation of P * i and n i = card P i . Every vertex of CH(P ) is a vertex of some CH(P i ), and we can apply Lemma 2.3.8 to bound the number of vertices of CH(P i ) from above by n i If m ′ > 1, the sum is maximized with ∀i, n i = n m ′ which bounds from above the number of vertices of CH(P ) by

	d-1 d+1 .

  For the rest of this proof call these points relevant. How much a relevant point contributes to E [card H ∩ P ] depends on how h compares to δ. If h ≤ δ then H intersects any ball p * +δB with depth at most δ, and Claim 2.3.2 bounds the contribution of any relevant point p * to E [card H ∩ P ] by vol

			1 1-d centered on ∂B contains Θ(1) points of P * . In total
	there are thus Θ nh	d-1 2	points p

* ∈ P * such that (p * + δB) ∩ H = ∅.

  2.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4.2 Witness-Collector Construction . . . . . . . . . . . . . . . . 47 2.4.3 Warm-up: Gaussian Polygons Made Easy . . . . . . . . . . . 49 2.4.4 Upper Bound on the Smoothed Complexity . . . . . . . . . 51 2.4.5 Lower Bound on Smoothed Complexity: Points in Convex Position . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4.6 Gaussian Perturbation of a Regular Polygon: An Upper Bound 65

  Claim 2.4.8. For any p * ∈ P * , we have P p ∈ C j i = O 1 n + P p ∈ W j Let h(p * ) and h(p * ) denote, respectively, d(p * , W j i ) and d(p * , C j i ). Since w ≥ 2 any point in P * is in the slab of W j i . First assume that p * is not in C j i . Claim 2.4.6 then ensures that h(p * ) ≥ h(p * ) -σ

	√ and the fact that Q is decreasing, we have 2 ln n . If h(p * ) > σ √ 2 ln n + σ √ 2 ln n then by Claim 2.4.7, Lemma 2.4.1 (i),

i .

Proof.

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.2 Approximations of Convex Bodies . . . . . . . . . . . . . . . . . . . 78 3.3 Construction of the Convex Body . . . . . . . . . . . . . . . . . . . 80 3.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

	Chapter 3
	A Chaotic Random Convex Hull
	Outline
	3.1

For instance, while Delaunay triangulations in R 3 have quadratic worst-case complexity, they appear to have near-linear size for the point sets arising in practice in the context of reconstruction[START_REF] Cazals | Delaunay triangulation based surface reconstruction[END_REF]; one should thus not consider Delaunay-based reconstruction methods inefficient on the sole ground of worst-case analysis. The worstcase analysis can sometimes be refined by introducing additional parameters such as fatness[START_REF] Berg | Improved bounds on the union complexity of fat objects[END_REF] or spread[START_REF] Erickson | Nice point sets can have nasty Delaunay triangulations[END_REF], but realistic input models remain elusive in many contexts (eg. computer graphics scenes).

A blueprint keeps also informations about the cluster centers.

Remerciements