Stars of empty simplices

Abstract

Let (Formula Presented) be a point set in general position. For a subset of X, let the degree be the number of d-dimensional simplices formed by this subset and further points of X which are empty—that is, which contain no other points of X. The k-degree of the set X is defined as the largest degree of all k-element subsets of X. We show that if X is a random point set consisting of n independently and uniformly chosen points from a convex set, then the d-degree is of order n, improving previously obtained results and giving the correct order of magnitude with a significantly simpler proof. We also prove that the 1-degree is of order nd-1 for d ≥ 3.