Skip to Main content Skip to Navigation
Conference papers

On the smoothed complexity of convex hulls

Olivier Devillers 1 Marc Glisse 2 Xavier Goaoc 3 Rémy Thomasse 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download
Contributor : Marc Glisse <>
Submitted on : Sunday, October 23, 2016 - 10:32:30 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM


Files produced by the author(s)



Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse. On the smoothed complexity of convex hulls. Proceedings of the 31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. pp.224-238, ⟨10.4230/LIPIcs.SOCG.2015.224⟩. ⟨hal-01144473v2⟩



Record views


Files downloads