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.9020866751670836
0 references
0.8982917666435242
0 references
0.8974841833114624
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