TY - JOUR

T1 - The ε -t-Net Problem

AU - Alon, Noga

AU - Jartoux, Bruno

AU - Keller, Chaya

AU - Smorodinsky, Shakhar

AU - Yuditsky, Yelena

N1 - Funding Information:
An abridged version of this paper appeared in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020). Noga Alon: Research supported in part by NSF Grant DMS-1855464, ISF Grant 281/17, GIF Grant G-1347-304.6/2016, and the Simons Foundation. Bruno Jartoux: Research supported by the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 678765) and by Grants 635/16 and 1065/20 from the Israel Science Foundation. Chaya Keller: Part of the research was done when the author was at the Technion, Israel. Supported by Grants 409/16 and 1065/20 from the Israel Science Foundation. Shakhar Smorodinsky: Research partially supported by Grants 635/16 and 1065/20 from the Israel Science Foundation. Yelena Yuditsky: Research supported by the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 678765) and by Grants 635/16 and 1065/20 from the Israel Science Foundation.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - We study a natural generalization of the classical ε-net problem (Haussler and Welzl in Discrete Comput. Geom. 2(2), 127–151 (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((d(1 + log t) / ε) 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. Finally, we use our techniques to generalize the notion of ε-approximation and to prove the existence of small-sized ε–t-approximations for sufficiently large hypergraphs with a bounded VC-dimension.

AB - We study a natural generalization of the classical ε-net problem (Haussler and Welzl in Discrete Comput. Geom. 2(2), 127–151 (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((d(1 + log t) / ε) 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. Finally, we use our techniques to generalize the notion of ε-approximation and to prove the existence of small-sized ε–t-approximations for sufficiently large hypergraphs with a bounded VC-dimension.

KW - Epsilon-nets

KW - Geometric hypergraphs

KW - Linear union complexity

KW - VC-dimension

UR - http://www.scopus.com/inward/record.url?scp=85125728643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125728643&partnerID=8YFLogxK

U2 - 10.1007/s00454-022-00376-x

DO - 10.1007/s00454-022-00376-x

M3 - Article

AN - SCOPUS:85125728643

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

ER -