Title: Halving by a Thousand Cuts Or Punctures

Speaker: Da Wei Zheng, University of Illinois Urbana-Champaign

Date and time: 2pm (New York time), Tuesday, February 14, 2023

Place: On Zoom (details provided on the seminar mailing list)

For point sets $P_1,...,P_k$, a set of lines $L$ is halving if any face of the arrangement $A(L)$ contains at most $\lvert P_i \rvert/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 $\tilde O(\mathrm{OPT}^{3/2})$, where $\mathrm{OPT}$ is the size of the optimal solution. 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 setting, 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.

This is joint work with Sariel Har-Peled.