Home Bookmarks Papers Blog

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

$\newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ Sariel Har-Peled, and Mitchell Jones.
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 $\Omega(1/\eps^{1-k/d})$. As a concrete example, in three dimensions all $\eps$-heavy bodies in $[0,1]^3$ can be stabbed by $\Theta(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} )$.
PDF. : arXiv : DBLP (SoCG) .