Epsilon-net of a set system

Summary

An $\varepsilon$-net of a family of sets is a subset of the ground set that meets every large member of the family. Here large means that the member holds at least an $\varepsilon$ fraction of the points. It is a small sample that is guaranteed to hit every heavy range. The $\varepsilon$-net theorem of Haussler and Welzl says that families of VC dimension $d$ have $\varepsilon$-nets of size $O\big(\frac{d}{\varepsilon} \log \frac{d}{\varepsilon}\big)$, independent of the number of points. This makes $\varepsilon$-nets a central tool in computational geometry and learning theory.