The $\epsilon$-$t$-Net Problem

Abstract

We study a natural generalization of the classical $\epsilon$-net problem (Haussler--Welzl 1987), which we call the "$\epsilon$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $\epsilon \ge \frac{t}{n}$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\epsilon$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\epsilon$-$t$-net of size $O(\frac{(1+\log t)d}{\epsilon }\log \frac{1}{\epsilon })$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\epsilon })$-sized $\epsilon$-$t$-nets. We also present an explicit construction of $\epsilon$-$t$-nets (including $\epsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\epsilon$-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.

This is the full version of the paper to appear in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020)

References in corpus (2)

• On Pseudo-disk Hypergraphs
• On the VC-dimension of half-spaces with respect to convex sets