论文标题
减少一千个削减或穿刺
Halving by a Thousand Cuts or Punctures
论文作者
论文摘要
$ \ newCommand {\ arr} {\ Mathcal {a}} \ newCommand {\ nums} {k} {k} \ newCommand {\ arrx} [1] {\ arr（＃1） \ newCommand {\ opt} {\ mathsf {o}} $ for点集$ p_1，\ ldots，p_ \ nums $，一组$ l $如果facement $ \ arrx {l} $的任何面$ \ arrx {l} $最多，最多包含$ | p_i | p_i |/2 $ p_i $ p_i $ $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ y $我们研究了计算一组最小尺寸的线路集的问题。令人惊讶的是，我们显示了一种多项式时间算法，该算法输出了一组尺寸$ o（\ opt^{3/2}）$的一组，其中$ \ opt $是最佳解决方案的大小。我们的解决方案依赖于解决走廊的弱$ \ eps $ -NET问题的新变体，我们认为这是独立的。 我们还研究了此问题的其他变体，包括替代设置，其中人们需要引入一组警卫（即点），因此没有凸组避免避免后卫包含每个点集的一半以上。
$\newcommand{\Arr}{\mathcal{A}} \newcommand{\numS}{k} \newcommand{\ArrX}[1]{\Arr(#1)} \newcommand{\eps}{\varepsilon} \newcommand{\opt}{\mathsf{o}}$ 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 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.
