TY - GEN

T1 - Halving by a Thousand Cuts or Punctures

AU - Har-Peled, Sariel

AU - Zheng, Da Wei

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - For point sets P1, ..., Pk, a set of lines L is halving if any face of the arrangement A(L) contains at most |Pi|/2 points of Pi, 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(o3/2), where o is the size of the optimal solution - this is of interest when o = o(log2 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.

AB - For point sets P1, ..., Pk, a set of lines L is halving if any face of the arrangement A(L) contains at most |Pi|/2 points of Pi, 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(o3/2), where o is the size of the optimal solution - this is of interest when o = o(log2 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.

UR - http://www.scopus.com/inward/record.url?scp=85170033768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85170033768&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85170033768

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1385

EP - 1397

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -