TY - JOUR

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

AU - Har-Peled, Sariel

AU - Jones, Mitchell

N1 - Funding Information:
We thank an anonymous reviewer for sketching an improved construction of -net s for , which led to Theorem 7. Our previous construction had an additional log term. We also thank the anonymous reviewers for detailed comments that improved the paper.
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023

Y1 - 2023

N2 - Consider the problem of constructing weak ε-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, ε) -net is a set of k-flats, such that any convex body in [0 , 1] d of volume larger than ε is stabbed by one of these k-flats. We show that for k≥ 1 , one can construct (k, ε) -nets of size O(1 / ε1-k/d). We also prove that any such net must have size at least Ω (1 / ε1-k/d). As a concrete example, in three dimensions all ε-heavy bodies in [0 , 1] 3 can be stabbed by Θ (1 / ε2 / 3) lines. Note that these bounds are sublinear in 1 / ε, and are thus somewhat surprising. The new construction also works for points providing a weak ε-net of size O((1 / ε) log d-1(1 / ε)).

AB - Consider the problem of constructing weak ε-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, ε) -net is a set of k-flats, such that any convex body in [0 , 1] d of volume larger than ε is stabbed by one of these k-flats. We show that for k≥ 1 , one can construct (k, ε) -nets of size O(1 / ε1-k/d). We also prove that any such net must have size at least Ω (1 / ε1-k/d). As a concrete example, in three dimensions all ε-heavy bodies in [0 , 1] 3 can be stabbed by Θ (1 / ε2 / 3) lines. Note that these bounds are sublinear in 1 / ε, and are thus somewhat surprising. The new construction also works for points providing a weak ε-net of size O((1 / ε) log d-1(1 / ε)).

KW - Approximation

KW - Sublinear bounds

KW - Weak ε-net

UR - http://www.scopus.com/inward/record.url?scp=85153109110&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85153109110&partnerID=8YFLogxK

U2 - 10.1007/s00454-023-00496-y

DO - 10.1007/s00454-023-00496-y

M3 - Article

AN - SCOPUS:85153109110

SN - 0179-5376

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

ER -