Home Bookmarks Papers Blog

Halving by a Thousand Cuts or Punctures

$ \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\Arr}{\Mh{\mathcal{A}}}% \newcommand{\ArrX}[1]{\Arr\pth{#1}}% \newcommand{\ptq}{q} \newcommand{\numS}{\Mh{k}} \newcommand{\opt}{\Mh{\mathsf{o}}} \renewcommand{\L}{\Mh{L}}% \renewcommand{\P}{\Mh{P}}% \newcommand{\pts}{s}$
Sariel Har-Peled and Da Wei Zheng.
For point sets $\P_1, \ldots, \P_\numS$, a set of lines $\L$ is halving if any face of the arrangement $\ArrX{\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 $\eps$-net problem for corridors, which we believe to be of independent interest.

We also study other variants of this problem, including an alternative 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.


PDF.
Last modified: Wed 2022-08-24 02:47:30 UTC 2022 by Sariel Har-Peled