论文标题
用点，线和平底鞋刺凸面的注释
A Note on Stabbing Convex Bodies with Points, Lines, and Flats
论文作者
论文摘要
$ \ newCommand {\ eps} {\ varepsilon} \ newCommand {\ tldo} {\ wideTilde {o}} $考虑构建弱$ \ eps $ -Nets的问题，其中刺伤元素是线条或$ k $ -flats而不是点而不是点。我们在最简单的环境中研究了这个问题，即它仍然很有趣 - 即，在HyperCube $ [0,1]^d \ bigr。$上的均匀量度量度。具体而言，$（k，\ eps）$ - 网是一组$ k $ - flats，因此，大于$ \ eps $的$ [0,1]^d $中的任何凸件被这些$ k $ flats之一刺穿。我们表明，对于$ k \ geq 1 $，一个人可以构造$（k，\ eps）$ - 尺寸$ o（1/\ eps^{1-k/d}）$的网。我们还证明，任何此类净值都必须具有至少$ω（1/\ eps^{1-k/d}）$。作为一个具体的示例，在三个维度中，所有$ \ eps $ -Heavy them in $ [0,1]^3 $可以用$θ（1/\ EPS^{2/3}）$ line刺入。请注意，这些界限是\ emph {sublinear} $ 1/\ eps $，因此有些令人惊讶。新结构还适用于提供较弱的$ \ eps $ -NET的尺寸$ o（\ tfrac {1} {\ eps} \ log^{d-1} \ tfrac {1} {\ eps}）$。
$\newcommand{\eps}{\varepsilon}\newcommand{\tldO}{\widetilde{O}}$Consider the problem of constructing weak $\eps$-nets where the stabbing elements are lines or $k$-flats instead of points. We study this problem in the simplest setting where it is still interesting -- namely, the uniform measure of volume over the hypercube $[0,1]^d\bigr.$. Specifically, a $(k,\eps)$-net is a set of $k$-flats, such that any convex body in $[0,1]^d$ of volume larger than $\eps$ is stabbed by one of these $k$-flats. We show that for $k \geq 1$, one can construct $(k,\eps)$-nets of size $O(1/\eps^{1-k/d})$. We also prove that any such net must have size at least $Ω(1/\eps^{1-k/d})$. As a concrete example, in three dimensions all $\eps$-heavy bodies in $[0,1]^3$ can be stabbed by $Θ(1/\eps^{2/3})$ lines. Note, that these bounds are \emph{sublinear} in $1/\eps$, and are thus somewhat surprising. The new construction also works for points providing a weak $\eps$-net of size $O(\tfrac{1}{\eps}\log^{d-1} \tfrac{1}{\eps} )$.
