On the smoothed complexity of convex hulls

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.