Stabbing convex bodies with lines and flats

Sariel Har-Peled, Mitchell Jones

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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]3 can be stabbed by Θ(1/ε2/3) lines. Note, that these bounds are sublinear in 1/ε, and are thus somewhat surprising.

Original languageEnglish (US)
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771849
DOIs
StatePublished - Jun 1 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: Jun 7 2021Jun 11 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume189
ISSN (Print)1868-8969

Conference

Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo
Period6/7/216/11/21

Keywords

  • Combinatorics
  • Discrete geometry
  • K-flats
  • Weak ε-nets

ASJC Scopus subject areas

  • Software

Cite this