An improved bound for k -sets in three dimensions
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos · 2000
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk3/2).This improves substantially the previous best known upper bound of O(nk 5/3) (see [7] and [1]). IntroductionLet S be a set of n points in ]R d, A k-set of S is a subset S' c S such that S' = S N H for some halfspace H and IS'] --k.The problem of determining tight asymptotic bounds on the maximum number of k-sets is one of the most intriguing open problems in combinatorial geometry.Due to its importance in analyzing geometric algorithms [5,9], the problem has caught the attention of computational geometers as well [3,7,8,14,16].A close to optimal solution for the problem remains elusive even in the plane.The best asymptotic upper and lower bounds in the plane are O(nkU3) (see [6]) and n. 2 n(v/iS--~) (see [15]), respectively.In this