2022/08/24 by Sariel Har-Peled, Har-Peled, Sariel, Da Wei Zheng +1
Computer Science · Engineering · Environmental Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.2208.11275
openalex publication_date 2022/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\newcommand\ArrA \newcommand\numSk \newcommand\ArrX[1]\Arr(#1) \newcommand\epsε \newcommand\opto For point sets P1, …, P_\numS, a set of lines L is halving if any face of the arrangement \ArrXL 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(\opt3/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 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.