Published in

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2015

DOI: 10.4230/lipics.socg.2015.224

Links

Tools

Export citation

Search in Google Scholar

On the Smoothed Complexity of Convex Hulls

Journal article published in 2015 by Olivier Devillers ORCID, Marc Glisse, Xavier Goaoc, Rémy Thomasse
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

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.