David Zheng "Halving by a Thousand Cuts Or Punctures"
- Event Type
- Seminar/Symposium
- Sponsor
- Illinois Computer Science
- Location
- 3401 SC
- Virtual
- Join online
- Date
- Feb 13, 2023 11:00 am
- Speaker
- David Zheng, UIUC
- Contact
- Candice Steidinger
- steidin2@illinois.edu
- Views
- 104
We look forward to seeing you in person in 3401 SC or online on February 13 for the Theory Seminar.
Abstract:
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 |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 ε-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.
Joint work with Sariel Har-Peled. SODA23. https://arxiv.org/abs/2208.11275 .