On the convex hull of random points in a polytope (Q3825830)

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 4100276
Language Label Description Also known as
default for all languages
No label defined
    English
    On the convex hull of random points in a polytope
    scientific article; zbMATH DE number 4100276

      Statements

      On the convex hull of random points in a polytope (English)
      0 references
      1988
      0 references
      convex hull of a finite
      0 references
      asymptotic behaviour
      0 references
      extreme points
      0 references
      0 references
      Let \({\mathcal L}_ n=\{X_ 1,...,X_ n\}\) be a set of n points in \(R^ d\) where elements of \({\mathcal L}_ n\) are i.i.d. random variables. The convex hull of \({\mathcal L}_ n\) is the intersection of all closed halfspaces containing \({\mathcal L}_ n\). The convex hull of a finite set is a polytope. The vertices of the polytope are called the extreme points of \({\mathcal L}_ n\). Let E \(V_ n\) (E \(F_ n)\) be the expected number of vertices (facets) of the polytope. The author studies the asymptotic behaviour of E \(V_ n\) and E \(F_ n\) for sets of points, chosen a uniform distribution on the interior of a d- dimensional polytope. He proves that E \(V_ n=O(\log^{d-1}n)\) and E \(F_ n=O(\log^{(d-1)/[d/2]}n)\), for points drawn from any d-polytope. In the next two sections it is shown that the bound on E \(V_ n\) is tight for a large class of polytopes including the simple polytopes and E \(F_ n=O(\log^{d-1}n)\) for any simple polytope. In the conclusion of the paper, these bounds are applied to the analysis of new algorithms for identifying extreme points and constructing the convex hull.
      0 references

      Identifiers