Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2015
DOI: 10.4230/lipics.socg.2015.224
We establish an upper bound on the smoothed complexity of convex hulls in $ℝ^d$ under uniform Euclidean ($\ell^2$) noise. Specifically, let $\{p_1^*, p_2^*, …, p_n^*\}$ be an arbitrary set of $n$ points in the unit ball in $ℝ^d$ and let $p_i=p_i^*+x_i$, where $x_1, x_2, …, x_n$ are chosen independently from the unit ball of radius $δ$. We show that the expected complexity, measured as the number of faces of all dimensions, of the convex hull of $\{p_1,p_2, …, p_n\}$ is $O\left(n^{2-\frac{4}{d+1}}\left(1+1/δ\right)^{d-1}\right)$; the magnitude $δ$ of the noise may vary with $n$. For $d=2$ this bound improves to $O\left(n^{\frac{2}{3}}(1+δ^{-\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.