An upper bound on the number of planar k-sets

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X^c. It is proved that O(n√k/log_*k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p.139-49) by a factor of log _*k. The method can be extended to give the bound O(n√k/(log k)^ε). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work