On the expected number of holes in random point sets

For a positive integer d, let S be a finite set of points in R^d with no d+1 points on a common hyperplane. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S.

We study the expected number of holes in sets of n points drawn uniformly and independently at random from a convex body of unit volume. We provide several new bounds and show that they are tight. In many cases, we are even able to determine the leading constants precisely, improving several previous results.

This is based on two joint works with Pavel Valtr and Manfred Schecher.