Convex bodies, economic cap coverings, random polytopes (Q3828623)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4103863
Language Label Description Also known as
default for all languages
No label defined
    English
    Convex bodies, economic cap coverings, random polytopes
    scientific article; zbMATH DE number 4103863

      Statements

      Convex bodies, economic cap coverings, random polytopes (English)
      0 references
      0 references
      1988
      0 references
      random polytope
      0 references
      volume
      0 references
      cap
      0 references
      convex body
      0 references
      0 references
      0 references
      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)}. \]
      0 references

      Identifiers