The monotonicity of f-vectors of random polytopes

Abstract

Let K be a compact convex body in R-d, let K-n be the convex hull of n points chosen uniformly and independently in K, and let f(i) (K-n) denote the number of i -dimensional faces of K-n. We show that for planar convex sets, E[f(0) (K-n)] is increasing in n. In dimension d >= 3 we prove that if lim(n ->infinity) E[f(d-1) (K-n)]/An(c) = 1 for some constants A and c > 0 then the function n -> E[f(d-1) (K-n)] is increasing for n large enough. In particular, the number of facets of the convex hull of n random points distributed uniformly and independently in a smooth compact convex body is asymptotically increasing. Our proof relies on a random sampling argument.