Beschreibung:
The convex hull of n points drawn independently from a uniform distribution on the interior of a d-dimensional polytope is investigated. It is shown that the expected number of vertices is O(log d–1 n) for any polytope, the expected number of vertices is Ω(log d–1 n) for any simple polytope, and the expected number of facets is O(log d–1 n) for any simple polytope. An algorithm is presented for constructing the convex hull of such sets of points in linear average time.