A. V. Aho, Complexity theory The Hardware, Software and Heart of It, Computer Science, pp.241-267

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Machine Learning, pp.245-248, 2009.
DOI : 10.1007/s10994-009-5103-0

N. Alon and J. H. Spencer, The probabilistic method Wiley-Interscience Series in Discrete Mathematics and Optimization, 2008.

D. Arthur, B. Manthey, and H. Röglin, Smoothed analysis of the kmeans method, J. ACM, vol.5819, issue.5, pp.1-19, 2011.

D. Attali, O. Devillers, and X. Goaoc, The Effect of Noise on the Number of Extreme Points
URL : https://hal.archives-ouvertes.fr/inria-00438409

I. Bárány, Intrinsic volumes andf-vectors of random polytopes, Mathematische Annalen, vol.52, issue.4, pp.671-699, 1989.
DOI : 10.1007/BF01452053

I. Bárány, Random points and lattice points in convex bodies, Bulletin of the American Mathematical Society, vol.45, issue.3, pp.339-365, 2008.
DOI : 10.1090/S0273-0979-08-01210-X

I. Bárány and D. Larman, Convex bodies, economic cap coverings, random polytopes, pp.274-291, 1988.

I. Bárány and V. Vu, Central limit theorems for gaussian polytopes. The Annals of Probability, pp.1593-1621, 2007.

W. Blaschke, Vorlesungen über Differenzialgeometrie II. Affine Differenzialgeometrie, 1923.

K. Böröczky-jr, Polytopal Approximation Bounding the Number of k-Faces, Journal of Approximation Theory, vol.102, issue.2, pp.263-285, 2000.
DOI : 10.1006/jath.1999.3413

I. Bárány, Random polytopes in smooth convex bodies, Mathematika, vol.151, issue.01, pp.81-92, 1992.
DOI : 10.1007/BF00535300

F. Cazals and J. Giesen, Delaunay Triangulation Based Surface Reconstruction, Effective Computational Geometry for Curves and Surfaces, pp.231-276, 2006.
DOI : 10.1007/978-3-540-33259-6_6
URL : https://hal.archives-ouvertes.fr/inria-00070609

R. M. Corless, G. H. Gonnet, D. Hare, D. J. Jeffrey, and D. E. Knuth, On the LambertW function, Advances in Computational Mathematics, vol.1, issue.6, pp.329-35910, 1996.
DOI : 10.1007/BF02124750

T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms, 2001.

V. Damerow and C. Sohler, Extreme Points Under Random Noise, Proc. 12th European Sympos. Algorithms, pp.264-274, 2004.
DOI : 10.1007/978-3-540-30140-0_25

G. Dantzig, Maximization of linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation, pp.339-347, 1951.

M. Berg, Improved Bounds on the Union Complexity of Fat Objects, Discrete & Computational Geometry, vol.9, issue.1, pp.127-14010, 2008.
DOI : 10.1007/s00454-007-9029-7

M. De-berg, H. Haverkort, and C. P. Tsirogiannis, Visibility maps of realistic terrains have linear smoothed complexity, Proceedings of the 25th annual symposium on Computational geometry, SCG '09, pp.163-168, 2009.
DOI : 10.1145/1542362.1542397

O. Devillers, V. Dujmovic, H. Everett, X. Goaoc, S. Lazard et al., The Expected Number of 3D Visibility Events Is Linear, SIAM Journal on Computing, vol.32, issue.6, pp.1586-1620, 2003.
DOI : 10.1137/S0097539702419662
URL : https://hal.archives-ouvertes.fr/inria-00071914

O. Devillers, M. Glisse, and X. Goaoc, Complexity analysis of random geometric structures made simpler, Proceedings of the 29th annual symposium on Symposuim on computational geometry, SoCG '13
DOI : 10.1145/2462356.2462362
URL : https://hal.archives-ouvertes.fr/hal-00761171

O. Devillers, M. Glisse, and X. Goaoc, Complexity analysis of random geometric structures made simpler, Proceedings of the 29th annual symposium on Symposuim on computational geometry, SoCG '13, pp.167-176, 2013.
DOI : 10.1145/2462356.2462362
URL : https://hal.archives-ouvertes.fr/hal-00761171

O. Devillers, M. Glisse, X. Goaoc, G. Moroz, and M. Reitzner, The monotonicity of $f$-vectors of random polytopes, Electronic Communications in Probability, vol.18, issue.0, pp.1-8, 2013.
DOI : 10.1214/ECP.v18-2469
URL : https://hal.archives-ouvertes.fr/hal-00758686

O. Devillers, P. Duchon, and R. Thomasse, A generator of random convex polygons in a disc AofA 2014-25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms URL https, 2014.

O. Devillers, M. Glisse, and R. Thomasse, A chaotic random convex hull AofA 2014-25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms URL https, 2014.

O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse, On the Smoothed Complexity of Convex Hulls Schloss Dagstuhl?Leibniz-Zentrum fuer Informatik, 31st International Symposium on Computational Geometry of Leibniz International Proceedings in Informatics (LIPIcs), pp.224-238, 2015.

O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse, On the smoothed complexity of convex hulls, Symposium on Computational Geometry, pp.224-239, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01144473

O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse, Smoothed complexity of convex hulls by witnesses and collectors URL https, Research Report, vol.8787, 2015.

R. Dwyer, The expected number of k-faces of a Voronoi diagram. Internat, J. Comput. Math, vol.26, issue.593, pp.13-2110, 1993.

B. Efron, The convex hull of a random set of points, Biometrika, vol.52, issue.3-4, pp.331-343, 1965.
DOI : 10.1093/biomet/52.3-4.331

J. Erickson, Nice point sets can have nasty Delaunay triangulations. Discrete and Computational Geometry, pp.109-13210, 2003.

M. Glisse, S. Lazard, J. Michel, and M. Pouget, Silhouette of a random polytope, Research Report, vol.8327
URL : https://hal.archives-ouvertes.fr/hal-00841374

R. L. Graham, An efficient algorith for determining the convex hull of a finite planar set, Information Processing Letters, vol.1, issue.4, pp.132-133, 1972.
DOI : 10.1016/0020-0190(72)90045-2

M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization

M. Inaba, N. Katoh, and H. Imai, -clustering, Proceedings of the tenth annual symposium on Computational geometry , SCG '94, pp.332-339, 1994.
DOI : 10.1145/177424.178042
URL : https://hal.archives-ouvertes.fr/in2p3-01333933

V. Klee and G. J. Minty, How Good is the Simplex Algorithm?, Inequalities III, pp.159-175, 1972.

M. Mahajan, P. Nimbhorkar, and K. Varadarajan, The Planar k-Means Problem is NP-Hard, WALCOM: Algorithms and Computation, pp.274-285, 2009.
DOI : 10.1109/TC.1981.6312176

J. Marckert, Probability that n random points in a disk are in convex position, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01433151

V. Petrov, Limit Theorems of Probability Theory Sequence of Independent Random Variables Number 4 in Oxford studies in probability, 1995.

H. Raynaud, Sur l'enveloppe convexe des nuages de points aleatoires dans R n, J. Appl. Probab, vol.7, pp.35-48, 1970.

M. Reitzner, The combinatorial structure of random polytopes, Advances in Mathematics, vol.191, issue.1, pp.178-208, 2005.
DOI : 10.1016/j.aim.2004.03.006

M. Reitzner, Random Polytopes, New perspectives in stochastic geometry, pp.45-76, 2010.
DOI : 10.1093/acprof:oso/9780199232574.003.0002
URL : https://hal.archives-ouvertes.fr/hal-00758686

A. Rényi and R. Sulanke, ???ber die konvexe H???lle von n zuf???llig gew???hlten Punkten, Zeitschrift f???r Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol.2, issue.1, pp.75-84, 1963.
DOI : 10.1007/BF00535300

A. Rényi and R. Sulanke, ???ber die konvexe H???lle von n zuf???llig gew???hlten Punkten. II, Zeitschrift f???r Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol.2, issue.2, pp.138-14710, 1964.
DOI : 10.1007/BF00535973

A. Sankar, D. A. Spielman, and S. Teng, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, SIAM Journal on Matrix Analysis and Applications, vol.28, issue.2, pp.446-476, 2006.
DOI : 10.1137/S0895479803436202

C. Schütt and E. Werner, The convex floating body., MATHEMATICA SCANDINAVICA, vol.66, issue.2, pp.275-290, 1990.
DOI : 10.7146/math.scand.a-12311

D. A. Spielman and S. Teng, Smoothed analysis of algorithms, Journal of the ACM, vol.51, issue.3, pp.385-463, 2004.
DOI : 10.1145/990308.990310

J. J. Sylvester, On a special class of questions on the theory of probabilities, Birmingham British Association Report, pp.8-9

L. N. Trefethen, D. Bau, and I. , Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), 1997.
DOI : 10.1137/1.9780898719574

P. Valtr, The probability thatn random points in a triangle are in convex position, Combinatorica, vol.13, issue.4, pp.567-573, 1996.
DOI : 10.1007/BF01271274

A. Vattani, k-means Requires Exponentially Many Iterations Even in the Plane, Discrete & Computational Geometry, vol.51, issue.3, pp.596-616, 2011.
DOI : 10.1007/s00454-011-9340-1

]. J. Wilkinson, Error Analysis of Direct Methods of Matrix Inversion, Journal of the ACM, vol.8, issue.3
DOI : 10.1145/321075.321076