Random points and lattice points in convex bodies

Assume K ⊂ R d K ⊂ R^d is a convex body and X X is a (large) finite subset of K K ? How many convex polytopes are there whose vertices belong to X X ? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of X X ) approximate K K ? We are interested in these questions mainly in two cases. The first is when X X is a random sample of n n uniform, independent points from K K . In this case motivation comes from Sylvester’s famous four-point problem and from the theory of random polytopes. The second case is when X = K ∩ Z d X=K ∩ Z^d where Z d Z^d is the lattice of integer points in R d R^d and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar.