TY - GEN

T1 - Stabbing convex bodies with lines and flats

AU - Har-Peled, Sariel

AU - Jones, Mitchell

N1 - Funding Information:
Supported in part by NSF AF award CCF-1907400.
Publisher Copyright:
© Sariel Har-Peled and Mitchell Jones; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

PY - 2021/6/1

Y1 - 2021/6/1

N2 - We study 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.

AB - We study 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.

KW - Combinatorics

KW - Discrete geometry

KW - K-flats

KW - Weak ε-nets

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

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

U2 - 10.4230/LIPIcs.SoCG.2021.42

DO - 10.4230/LIPIcs.SoCG.2021.42

M3 - Conference contribution

AN - SCOPUS:85108191767

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Computational Geometry, SoCG 2021

A2 - Buchin, Kevin

A2 - de Verdiere, Eric Colin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 37th International Symposium on Computational Geometry, SoCG 2021

Y2 - 7 June 2021 through 11 June 2021

ER -