On the bichromatic k-set problem

We study a bichromatic version of the well-known k-set problem: given two sets R and B of points of total size n and an integer k, how many subsets of the form (R ∩ h) ∪ (B \ h) can have size exactly k over all halfspaces h? In the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the k-level in an arrangement of n halfspaces. Disproving an earlier conjecture by Linhart (1993), we present the first nontrivial upper bound for all k « n in two dimensions: 0(nk ^1/3 + n^5/6-εk^2/3+2ε + k²) for any fixed ε > 0. In three dimensions, we obtain the bound 0(nk ^3/2 +n^0.5034k^2.4932 + k³). Incidentally, this also implies a new upper bound for the original k-set problem in four dimensions: 0(n²k^3/2+n^1.5034k ^2.4932+nk³), which improves the best previous result for all k « n^0.923. Extensions to other cases, such as arrangements of disks, are also discussed.