On the convex hull of random points in a polytope

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’-¹n) for any polytope, the expected number of vertices is ¦[(log^d’-¹n) for any simple polytope, and the expected number of facets is O(log^d’-¹n) for any simple polytope. An algorithm is presented for constructing the convex hull of such sets of points in linear average time.