## Abstract

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 / ε)).

Original language | English (US) |
---|---|

Pages (from-to) | 1241-1254 |

Number of pages | 14 |

Journal | Discrete and Computational Geometry |

Volume | 69 |

Issue number | 4 |

DOIs | |

State | Published - Jun 2023 |

## Keywords

- Approximation
- Sublinear bounds
- Weak ε-net

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics