The ε-T-net problem

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky

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

Abstract

We study a natural generalization of the classical ε-net problem (Haussler-Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ nt, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least εn contains a set in S. When t = 1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log ε t)d log 1 ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1 ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t = 1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

Original languageEnglish (US)
Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771436
DOIs
StatePublished - Jun 1 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: Jun 23 2020Jun 26 2020

Publication series

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

Conference

Conference36th International Symposium on Computational Geometry, SoCG 2020
CountrySwitzerland
CityZurich
Period6/23/206/26/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Epsilon-nets
  • Geometric hypergraphs
  • Linear union complexity
  • VC-dimension

Cite this

Alon, N., Jartoux, B., Keller, C., Smorodinsky, S., & Yuditsky, Y. (2020). The ε-T-net problem. In S. Cabello, & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry, SoCG 2020 [LIPIcs-SoCG-2020-5] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2020.5