Home Bookmarks Papers Blog

# Halving by a Thousand Cuts or Punctures

Sariel Har-Peled and Da Wei Zheng.
For point sets $\P_1, \ldots, \P_\numS$, a set of lines $\L$ is halving if any face of the arrangement $\ArrX{\L}$ contains at most $|\P_i|/2$ points of $\P_i$, for all $i$. We study the problem of computing a halving set of lines of minimal size. Surprisingly, we show a polynomial time algorithm that outputs a halving set of size $O(\opt^{3/2})$, where $\opt$ is the size of the optimal solution. Our solution relies on solving a new variant of the weak $\eps$-net problem for corridors, which we believe to be of independent interest.

We also study other variants of this problem, including an alternative settings, where one needs to introduce a set of guards (i.e., points), such that no convex set avoiding the guards contains more than half the points of each point set.

PDF.