×

On the shape of the convex hull of random points. (English) Zbl 0639.60015

Let Prob(d,n) denote the probability that a uniform and independent choice of n points from the unit ball in Euclidean d-space gives a convex hull with exactly n vertices. This paper studies the behaviour of Prob(d,n(d)), as \(d\to \infty\), for certain functions n(d).
C. Buchta [Monatsh. Math. 102, 91-102 (1986; Zbl 0594.52006)] proved that for \(n=(3/2-\epsilon)d\), \(\epsilon >0\), the probability tends to one. Here the authors show that \[ for\quad n=c 2^{d/2},\quad \lim_{d\to \infty}\Pr ob(d,n)>1-c^ 2, \]
\[ and\quad for\quad n=c d^{3/4} 2^{d/2},\quad \lim_{d\to \infty}\Pr ob(d,n)<2e^{-c/2}. \] They also investigate the question whether the convex hull is a neighborly polytope.
Reviewer: W.J.Firey

MSC:

60D05 Geometric probability and stochastic geometry

Citations:

Zbl 0594.52006
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bárány, I., Füredi, Z.: Approximation of the sphere by polytopes having few vertices. To appear in Proc. Am. Math. Soc. · Zbl 0669.52003
[2] Blaschke, W.: Vorlesungen über Differentialgeometrie II. Affine Differentialgeometrie. Berlin: Springer 1923 · JFM 49.0499.01
[3] Buchta, C.: On a conjecture of R.E. Miles about the convex hull of random points. Monatsh. Math. 102, 91–102 (1986) · Zbl 0594.52006 · doi:10.1007/BF01490202
[4] Buchta, C., Müller, J.: Random polytopes in a ball. J. Appl. Probab. 21, 753–762 (1984) · Zbl 0552.60006 · doi:10.2307/3213693
[5] Chernoff, H.: A measure of asymptotic efficiency for tests of an hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493–507 (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[6] Elekes, G.: A geometric inequality and the complexity of computing volume. Discrete. Comput. Geom. 1, 289–292 (1986) · Zbl 0611.52010 · doi:10.1007/BF02187701
[7] Erdös, P., Spencer, J.: Probabilistic methods in combinatorics. Budapest: Akadémiai Kiadó 1974
[8] Füredi, Z.: Random polytopes in the d-dimensional cube. Discrete Comput. Geom. 1, 315–319 (1986) · Zbl 0607.52004 · doi:10.1007/BF02187704
[9] Gruber, P.M.: Approximation of convex bodies by polytopes. In: Gruber, P.M., Wills, J.M. (eds.). Convexity and its applications, pp. 131–162. Basel: Birkhauser 1983
[10] Hostinsky, B.: Sur les probabilités géométriques. Publ. Fac. Sci. Univ. Masaryk. Brno. 1925 · JFM 51.0305.02
[11] Kingman, J.F.C.: Random secants of a convex body. J. Appl. Probab. 6, 660–672 (1969) · Zbl 0186.51603 · doi:10.2307/3212110
[12] Lovász, L.: An algorithmic theory of numbers, graphs and convexity. Preprint, Report No. 85368-OR, University of Bonn 1985
[13] Miles, R.E.: Isotropic random simplices. Adv. Appl. Probab. 3, 353–382 (1971) · Zbl 0237.60006 · doi:10.2307/1426176
[14] Rényi, A.: Probability theory. Amsterdam: North-Holland 1970 · Zbl 0233.60001
[15] Rényi, A., Sulanke, R.: Über die convexe Hülle von n zufällig gewählten Punkten I–II. Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 75–84 (1963); 3, 138–147 (1964) · Zbl 0118.13701 · doi:10.1007/BF00535300
[16] Spencer, F.: Sequences with small discrepancy relative to n events. Compositio Math. 47, 365–392 (1982) · Zbl 0502.10030
[17] Wendel, J.G.: A problem in geometric probability. Math. Scand. 11, 109–111 (1962) · Zbl 0108.31603
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.