Halving by a Thousand Cuts or Punctures

For point sets P₁, ..., P_k, a set of lines L is halving if any face of the arrangement A(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(o^3/2), where o is the size of the optimal solution - this is of interest when o = o(log² n). Our solution relies on solving a new variant of the weak ε-net problem for corridors, which we believe to be of independent interest. We also study other variants of this problem, including an alternative “dual” 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.