LIPIcs.SoCG.2021.42.pdf
- Filesize: 0.89 MB
- 12 pages
Document
Stabbing Convex Bodies with Lines and Flats
Authors
Mitchell Jones 
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Acknowledgements
We thank an anonymous reviewer for sketching an improved construction of (k, ε)-nets for k ≥ 1, which led to Theorem 6. Our previous construction had an additional log term.
Cite AsGet BibTex
Sariel Har-Peled and Mitchell Jones. Stabbing Convex Bodies with Lines and Flats. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.42
https://doi.org/10.4230/LIPIcs.SoCG.2021.42
Abstract
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]³ can be stabbed by Θ(1/ε^{2/3}) lines. Note, that these bounds are sublinear in 1/ε, and are thus somewhat surprising.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Discrete geometry
- combinatorics
- weak ε-nets
- k-flats
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Imre Bárány, Zoltán Füredi, and László Lovász. On the number of halving planes. Combinatorica, 10:175-183, 1990. URL: https://doi.org/10.1007/BF02123008.
- Boris Bukh, Jiří Matoušek, and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity. In Proc. 25th Annu. Sympos. Comput. Geom. (SoCG), pages 1-10. ACM, 2009. URL: https://doi.org/10.1145/1542362.1542365.
- Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York, 2001. URL: http://www.cs.princeton.edu/~chazelle/book.html.
- Sariel Har-Peled. Geometric Approximation Algorithms, volume 173 of Math. Surveys & Monographs. Amer. Math. Soc., Boston, MA, USA, 2011. URL: https://doi.org/10.1090/surv/173.
- David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
- Jiří Matoušek. Geometric discrepancy: An illustrated guide, volume 18 of Algorithms and Combinatorics. Springer, 1999. URL: https://doi.org/10.1007/978-3-642-03942-3.
- Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Grad. Text in Math. Springer, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7.
- Jiří Matoušek and Uli Wagner. New constructions of weak ε-nets. Discrete Comput. Geom., 32(2):195-206, 2004. URL: https://doi.org/10.1007/s00454-004-1116-4.
- János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. J. Amer. Math. Soc., 26:645-658, 2013. URL: https://doi.org/10.1090/S0894-0347-2012-00759-0.
- Natan Rubin. An improved bound for weak epsilon-nets in the plane. In Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 224-235, 2018. URL: https://doi.org/10.1109/FOCS.2018.00030.
-
Natan Rubin. Stronger bounds for weak epsilon-nets in higher dimensions. In Proc. 53rd ACM Sympos. Theory Comput. (STOC), 2021.
