2026-08-08T06:39:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12163 2024-03-06T10:49:35Z ddc:004 open_access

The ε-t-Net Problem Alon, Noga Jartoux, Bruno Keller, Chaya Smorodinsky, Shakhar Yuditsky, Yelena epsilon-nets geometric hypergraphs VC-dimension linear union complexity 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 ε ≥ t/n, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Alon and Bruno Jartoux and Chaya Keller and Shakhar Smorodinsky and Yelena Yuditsky 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.5 urn:nbn:de:0030-drops-121639 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5 eng https://creativecommons.org/licenses/by/3.0/legalcode