On the dichromatic κ-set problem

We study a bichromatic version of the well-known κ-set problem: given two sets R and B of points of total size n andaninteger κ, how many subsets of the form (R ∩ h) ∪ (B \ h) can have size exactly κ over all halfspaces h? In the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the κ-level in an arrangement of n halfspaces. Disproving an earlier conjecture by Linhart [1993], we present the first nontrivial upper bound foi all κ < n in two dimensions: O(nk1/3 + n5/6εκ2/3+2ε + κ2)for anyfixed ε 0. In three dimensions, we obtain the bound O(nκ3/2 + n0.5034κ2'4932 + κ3). Incidentally, this also implies a new upper bound for the original κ-set problem in four dimensions: O(n27kappa;3/2 + nL5034 7kappa;2'4932 + nκ3), which improves the best previous result for all κ < n0923. Extensions to other cases, such as arrangements of disks. are also discussed.