On the Smoothed Complexity of Convex Hulls

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



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.224.pdf
  • Filesize: 1.05 MB
  • 16 pages

Document Identifiers

Author Details

Olivier Devillers
Marc Glisse
Xavier Goaoc
Rémy Thomasse

Cite AsGet BibTex

Olivier Devillers, Marc Glisse, Xavier Goaoc, and Rémy Thomasse. On the Smoothed Complexity of Convex Hulls. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 224-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.224

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.
Keywords
  • Probabilistic analysis
  • Worst-case analysis
  • Gaussian noise

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Robert M. Corless, Gaston H. Gonnet, D.E.G. Hare, David J. Jeffrey, and Donald E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5(1):329-359, 1996. http://dx.doi.org/10.1007/BF02124750. Google Scholar
  2. Valentina Damerow and Christian Sohler. Extreme points under random noise. In Proc. 12th European Sympos. Algorithms, pages 264-274, 2004. http://dx.doi.org/10.1007/978-3-540-30140-0_25. Google Scholar
  3. Mark de Berg, Herman Haverkort, and Constantinos P. Tsirogiannis. Visibility maps of realistic terrains have linear smoothed complexity. Journal of Computational Geometry, 1:57-71, 2010. http://jocg.org/index.php/jocg/article/view/12. Google Scholar
  4. Olivier Devillers, Marc Glisse, and Xavier Goaoc. Complexity analysis of random geometric structures made simpler. In Symposium on Computational Geometry, pages 167-176, 2013. http://dx.doi.org/10.1145/2462356.2462362. Google Scholar
  5. Marc Glisse, Sylvain Lazard, Julien Michel, and Marc Pouget. Silhouette of a random polytope. Research Report 8327, INRIA, 2013. http://hal.inria.fr/hal-00841374/. Google Scholar
  6. Matthias Reitzner. Random polytopes. In New perspectives in stochastic geometry, pages 45-76. Oxford Univ. Press, Oxford, 2010. Google Scholar
  7. Alfréd Rényi and Rolf Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten I. Z. Wahrsch. Verw. Gebiete, 2:75-84, 1963. http://dx.doi.org/10.1007/BF00535300. Google Scholar
  8. Alfréd Rényi and Rolf Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten II. Z. Wahrsch. Verw. Gebiete, 3:138-147, 1964. http://dx.doi.org/10.1007/BF00535973. Google Scholar
  9. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51:385-463, 2004. http://dx.doi.org/10.1145/990308.990310. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail