Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems

Following groundbreaking work by Haussler and Welzl (1987), the use of small ε-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest ε-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Könemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in ℝ 4 $$\mathbb{R}^{4}$$ by a family of half-spaces such that the size of any ε-net for them is Ω ( 1 𝜖 log 1 𝜖 ) $$\Omega (\frac{1} {\epsilon } \log \frac{1} {\epsilon } )$$ (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in ℝ d , $$\mathbb{R}^{d},$$ for any d ≥ 4, to show that the general upper bound, O ( d 𝜖 log 1 𝜖 ) $$O(\frac{d} {\epsilon } \log \frac{1} {\epsilon } )$$ , of Haussler and Welzl for the size of the smallest ε-nets is tight.