×

Convex bodies, economic cap coverings, random polytopes. (English) Zbl 0674.52003

Let K be a convex compact body with nonempty interior in the d- dimensional Euclidean space \({\mathbb{R}}^ d\) and let \(x_ 1,x_ 2,...,x_ n\) be random points in K, independently and uniformly distributed. Define \(K_ n=conv\{x_ 1,...,x_ n\}\). The main purpose of the reviewed paper is to study the behaviour of the deviation of the vol \(K_ n\) from vol K as a function on n, more precisely, the expectation of the random variable \(vol(K\setminus K_ n)\). This expectation is denoted by E(K,n).
Let us define a map v: \(K\to {\mathbb{R}}\) as \(v(x)=\min \{vol(K\cap H):\) \(x\in H\), H a halfspace\(\}\). Next, for \(\epsilon >0\) define \(K(\epsilon)=\{x\in K:\) v(x)\(\leq \epsilon \}.\)
The main result of the paper: Theorem 1. Assume K is a convex compact body in \({\mathbb{R}}^ d\) with vol K\(=1\). Then for \(n\geq n_ 0(d)\) we have \[ const\cdot vol K(1/n)\leq E(K,n)\leq const(d)\cdot vol K(1/n). \] Different estimates for K(\(\epsilon)\) are also obtained.
The main tools in proving Theorem 1 is the following theorem concerning so-called “economic cap coverings”. (Let us remind that a cap of K is the set \(K\cap H\) where H is halfspace whenever this set is nonempty.)
Theorem 6. Assume a convex body \(K\subset {\mathbb{R}}^ d\) is given with vol K\(>0\). Take \(\epsilon\) with \(0<\epsilon <\epsilon_ 0(d)=(2d)^{-2d}\). Then there are caps \(K_ 1,...,K_ m\) of K and pairwise disjoint subsets \(K_ 1',...,K_ m'\), \(K_ i'\subset K_ i\) \((i=1,...,m)\) such that (i) \(\cup^{m}_{1}K_ i'\subset K(\epsilon)\subset \cup^{m}_{1}K_ i\), \((ii)\quad vol K_ i\leq 6^ d\epsilon\) \((i=1,...,m)\), (iii) vol \(K_ i'\geq (6d)^{-d}\epsilon\) \((i=1,...,m).\)
Let us also mention the following consequence of Theorem 6.
Theorem 8. Assume \(P\subset {\mathbb{R}}^ d\) is a convex polytope with n vertices and vol P\(>0\). Then P has \((d+1)\) vertices \(x_ 0,x_ 1,...,x_ d\) such that \[ vol(conv\{x_ 0,...,x_ d\})/vol P\leq const(d)n^{-(d+1)/(d-1)}. \]
Reviewer: M.Ostrovskij

MSC:

52A22 Random convex sets and integral geometry (aspects of convex geometry)
60D05 Geometric probability and stochastic geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02311318 · Zbl 0658.52003 · doi:10.1007/BF02311318
[2] Wendel, Math. Scand. 11 pp 109– (1962) · Zbl 0108.31603 · doi:10.7146/math.scand.a-10655
[3] DOI: 10.1112/plms/s3-25.3.543 · Zbl 0253.52001 · doi:10.1112/plms/s3-25.3.543
[4] Ewald, Mathematika 17 pp 1– (1970)
[5] Danzer, Proc. Symp. Pure Math. (1963)
[6] Buchta, Zufallige Polieder, eine Obersicht, Lecture Notes in Mathematics pp 1– (1985)
[7] DOI: 10.1007/BF00535006 · Zbl 0536.60020 · doi:10.1007/BF00535006
[8] Blaschke, Vorlesungen uber Differentialgeometrie II. Affine Differentialgeometrie (1923)
[9] DOI: 10.1007/BF00334039 · Zbl 0639.60015 · doi:10.1007/BF00334039
[10] Arnold, Functional Analysis and its Appl. 14 pp 1– (1980) · Zbl 0452.22014 · doi:10.1007/BF01078407
[11] DOI: 10.1007/BF00535973 · Zbl 0126.34103 · doi:10.1007/BF00535973
[12] DOI: 10.1007/BF00535300 · Zbl 0118.13701 · doi:10.1007/BF00535300
[13] DOI: 10.2307/1969800 · Zbl 0047.04903 · doi:10.2307/1969800
[14] DOI: 10.1007/BF01076357 · Zbl 0551.47012 · doi:10.1007/BF01076357
[15] DOI: 10.1112/jlms/s2-25.1.13 · Zbl 0483.52008 · doi:10.1112/jlms/s2-25.1.13
[16] Gruber, Rendiconti Sem. Mat. Torino 41 pp 19– (1983)
[17] Gruber, Convexity and its applications (1983) · Zbl 0512.00020 · doi:10.1007/978-3-0348-5858-8
[18] DOI: 10.1007/BF01238645 · Zbl 0287.52009 · doi:10.1007/BF01238645
[19] DOI: 10.1007/BF02187704 · Zbl 0607.52004 · doi:10.1007/BF02187704
[20] Schneider, Proc. Geom. Symp., Siegen, 1978 pp 13– (1979)
[21] Leichtweiss, Studia Math. Hung. 21 pp 453– (1986)
[22] DOI: 10.2307/1993769 · Zbl 0118.28301 · doi:10.2307/1993769
[23] Wieacker, Einige Probleme der polyedrischen Approximation (1987)
[24] DOI: 10.1007/BF00534188 · Zbl 0407.60009 · doi:10.1007/BF00534188
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.