K-set (geometry) - Combinatorial Bounds

Combinatorial Bounds

It is of importance in the analysis of geometric algorithms to bound the number of k-sets of a planar point set, or equivalently the number of k-levels of a planar line arrangement, a problem first studied by Lovász (1971) and Erdős et al. (1973). The best known upper bound for this problem is O(nk1/3), as was shown by Tamal Dey (1998) using the crossing number inequality of Ajtai, Chvátal, Newborn, and Szemerédi. However, the best known lower bound is far from Dey's upper bound: it is Ω(n exp(c (logk)1/2)) for some constant c, as shown by Toth (2001).

In three dimensions, the best upper bound known is O(nk3/2), and the best lower bound known is Ω(nk exp(c (logk)1/2)). For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of k-sets is Θ((n-k)k), which follows from arguments used for bounding the complexity of k-th order Voronoi diagrams.

For the case when k = n/2 (halving lines), the maximum number of combinatorially distinct lines through two points of S that bisect the remaining points when k = 1, 2, ... is

1,3,6,9,13,18,22... (sequence A076523 in OEIS).

Bounds have also been proven on the number of ≤k-sets, where a ≤k-set is a j-set for some j ≤ k. In two dimensions, the maximum number of ≤k-sets is exactly nk, while in d dimensions the bound is .