# On the smoothed complexity of convex hulls

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We establish an upper bound on the smoothed complexity of convex hulls in $\mathbb{R}^d$ under uniform Euclidean ($\ell^2$) noise. Specifically, let $\{p_1^*, p_2^*, \ldots, p_n^*\}$ be an arbitrary set of $n$ points in the unit ball in $\mathbb{R}^d$ and let $p_i=p_i^*+x_i$, where $x_1, x_2, \ldots, x_n$ are chosen independently from the unit ball of radius $\delta$. We show that the expected complexity, measured as the number of faces of all dimensions, of the convex hull of $\{p_1,p_2, \ldots, p_n\}$ is $O\left(n^{2-\frac{4}{d+1}}\left(1+1/\delta\right)^{d-1}\right)$; the magnitude $\delta$ of the noise may vary with $n$. For $d=2$ this bound improves to $O\left(n^{\frac{2}{3}}(1+\delta^{-\frac{2}{3}}\right)$. We also analyze the expected complexity of the convex hull of $\ell^2$ and Gaussian perturbations of a nice sample of a sphere, giving a lower-bound for the smoothed complexity. We identify the different regimes in terms of the scale, as a function of $n$, and show that as the magnitude of the noise increases, that complexity varies monotonically for Gaussian noise but non-monotonically for $\ell^2$ noise.
Type de document :
Communication dans un congrès
31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. Lipics, 2015, <http://www.win.tue.nl/SoCG2015/>. <10.4230/LIPIcs.SOCG.2015.224>
Liste complète des métadonnées

https://hal.inria.fr/hal-01144473
Contributeur : Marc Glisse <>
Soumis le : dimanche 23 octobre 2016 - 22:32:30
Dernière modification le : samedi 18 février 2017 - 01:14:35

### Fichiers

socg-final.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse. On the smoothed complexity of convex hulls. 31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. Lipics, 2015, <http://www.win.tue.nl/SoCG2015/>. <10.4230/LIPIcs.SOCG.2015.224>. <hal-01144473v2>

Consultations de
la notice

## 173

Téléchargements du document