A Note on Stabbing Convex Bodies with Points, Lines, and Flats
Consider the problem of constructing weak $\eps$-nets where the stabbing elements are lines or -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 . Specifically, a $(k,\eps)$-net is a set of -flats, such that any convex body in of volume larger than $\eps$ is stabbed by one of these -flats. We show that for , 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 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} )$.