Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T13:44:19.502Z Has data issue: false hasContentIssue false
  • English
  • Français

The convex hull of random balls

Part of: General convexity Geometric probability and stochastic geometry

Published online by Cambridge University Press:  01 July 2016

Fernando Affentranger  and
Rex A. Dwyer
Fernando Affentranger*
Affiliation:
Albert-Ludwigs-Universität, Freiburg i. Br.
Rex A. Dwyer*
Affiliation:
North Carolina State University
*
∗Postal address: Mathematisches Institut, Albert-Ludwigs-Universität, Hebelstraße 29, D-7800 Freiburg i. Br., Germany.
∗∗Postal address: Department of Computer Science, North Carolina State University, Raleigh, NC 27695-8206, USA., E-mail: [email protected]. Supported by the National Science Foundation under Grant CCR-8908782.
Get access Rights & Permissions [Opens in a new window]

Abstract

While the convex hull of n d-dimensional balls is not a polytope, it does have an underlying combinatorial structure similar to that of a polytope. In the worst case, its combinatorial complexity can be of order Ω(n[d/2]). The thrust of this work is to show that its complexity is typically much smaller, and that it can therefore be constructed more quickly on average than in the worst case. To this end, four models of the random d-ball are developed, and the expected combinatorial complexity of the convex hull of n independent random d-balls is investigated for each. As n grows without bound, these expectations are O(1), O(n(d–1)/(d+4)), O(1) (for d = 2 only), and O(n(d–1)/(d+3)).

Keywords

GEOMETRIC PROBABILITYINTEGRAL GEOMETRYCOMPUTATIONAL GEOMETRYPOLYTOPESALGORITHM ANALYSIS

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 52A22: Random convex sets and integral geometry 68U05: Computer graphics; computational geometry
Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 2 , June 1993 , pp. 373 - 394
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Affentranger, F. (1990) Random spheres in a convex body. Arch. Math. 55, 74–81.Google Scholar
[2] Buchta, C., Müller, F. and Tichy, R. F. (1985) Stochastical approximation of convex bodies. Math. Ann. 271, 225–235.Google Scholar
[3] Dwyer, R. A. (1991) Convex hulls of samples from spherically symmetric distributions. Disc. Appl. Math. 31, 113–132.Google Scholar
[4] Dwyer, R. A. (1990) Kinder, gentler average-case analysis for convex hulls. SIGACT News 21, 64–71.CrossRefGoogle Scholar
[5] Miles, R. E. (1971) Isotropic random simplices. Adv. Appl. Prob. 3, 353–382.Google Scholar
[6] Miles, R. E. (1974) A synopsis of ‘Poisson flats in Euclidean spaces’. In Stochastic Geometry , ed. Harding, E. F. and Kendall, D.G., pp. 202–227, Wiley, New York.Google Scholar
[7] Preparata, F. P. and Shamos, M. I. (1985) Computational Geometry: An Introduction . Springer-Verlag, New York.Google Scholar
[8] Rappaport, D. (1992) A convex hull algorithm for discs, and applications. Computational Geometry: Theory and Applications 1, 171–187.Google Scholar
[9] Rényi, A. and Sulanke, R. (1963/64) Über die konvexe Hülle von n zufällig gewählten Punkten. Z. Wahrscheinlichkeitsth. 2, 75–84; 3, 138–147.Google Scholar
[10] Santaló, L. A. (1976) Integral Geometry and Geometric Probability. Volume 1 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, Reading, MA.Google Scholar
[11] Schneider, R. (1988) Random approximation of convex sets. J. Microscopy 151, 211–227.Google Scholar