### Abstract

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.

Original language | English (US) |
---|---|

Article number | 62 |

Journal | ACM Transactions on Algorithms |

Volume | 6 |

Issue number | 4 |

DOIs | |

State | Published - Aug 1 2010 |

Externally published | Yes |

### Keywords

- Arrangements
- Combinatorial geometry
- κ-levels
- κ-sets

### ASJC Scopus subject areas

- Mathematics (miscellaneous)