A Note on Stabbing Convex Bodies with Points, Lines, and Flats

Abstract

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$. 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\ge 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} )$.

arXiv comment13 pages, 6 figures; updated with improved constructions of $(k,\epsilon )$-nets for $k\ge 1$