Stabbing Convex Bodies with Lines and Flats

Authors Sariel Har-Peled, Mitchell Jones



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.42.pdf
  • Filesize: 0.89 MB
  • 12 pages

Document Identifiers

Author Details

Sariel Har-Peled
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Il, USA
Mitchell Jones
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA

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

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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York, 2001. URL: http://www.cs.princeton.edu/~chazelle/book.html.
  4. 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.
  5. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Natan Rubin. Stronger bounds for weak epsilon-nets in higher dimensions. In Proc. 53rd ACM Sympos. Theory Comput. (STOC), 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail