| On the bichromatic k-set problem (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract 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 n 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 o / n in two dimensions: O(nk | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||