The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.224
URN: urn:nbn:de:0030-drops-51451
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5145/
Go to the corresponding LIPIcs Volume Portal

Devillers, Olivier ; Glisse, Marc ; Goaoc, Xavier ; Thomasse, Rémy

On the Smoothed Complexity of Convex Hulls

pdf-format:
62.pdf (1 MB)

Abstract

We establish an upper bound on the smoothed complexity of convex hulls in R^d under uniform Euclidean (L^2) noise. Specifically, let {p_1^*, p_2^*, ..., p_n^*} be an arbitrary set of n points in the unit ball in R^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 r. 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(n^{2-4/(d+1)} (1+1/r)^{d-1}); the magnitude r of the noise may vary with n. For d=2 this bound improves to O(n^{2/3} (1+r^{-2/3})).

We also analyze the expected complexity of the convex hull of L^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 L^2 noise.

BibTeX - Entry

@InProceedings{devillers_et_al:LIPIcs:2015:5145,
  author =	{Olivier Devillers and Marc Glisse and Xavier Goaoc and R{\'e}my Thomasse},
  title =	{{On the Smoothed Complexity of Convex Hulls}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{224--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5145},
  URN =		{urn:nbn:de:0030-drops-51451},
  doi =		{10.4230/LIPIcs.SOCG.2015.224},
  annote =	{Keywords: Probabilistic analysis, Worst-case analysis, Gaussian noise}
}

Keywords: Probabilistic analysis, Worst-case analysis, Gaussian noise
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI