Shakhar Smorodinsky

The problem of determining tight asymptotic bounds on the maximum number of k-sets is one of the most challenging open problems in combinatorial geometry. It is a widely studied problem due to its importance in analyzing geometric algorithms. The maximum number of k-sets in a set of n points in three dimensions is proven O(nk^3/2). This improves substantially the best known upper bound of O(nk^5/3).