TY - GEN
T1 - The ε-T-net problem
AU - Alon, Noga
AU - Jartoux, Bruno
AU - Keller, Chaya
AU - Smorodinsky, Shakhar
AU - Yuditsky, Yelena
N1 - Publisher Copyright:
© Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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.
AB - 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.
KW - Epsilon-nets
KW - Geometric hypergraphs
KW - Linear union complexity
KW - VC-dimension
UR - http://www.scopus.com/inward/record.url?scp=85086498970&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086498970&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2020.5
DO - 10.4230/LIPIcs.SoCG.2020.5
M3 - Conference contribution
AN - SCOPUS:85086498970
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Computational Geometry, SoCG 2020
A2 - Cabello, Sergio
A2 - Chen, Danny Z.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th International Symposium on Computational Geometry, SoCG 2020
Y2 - 23 June 2020 through 26 June 2020
ER -