Epsilon-nets and its Relatives

Epsilon nets and approximations are among the most fundamental notions of sampling. For a given set system and a parameter $epsilon$, an $epsilon$-net is a transveral for the sets of size at least $epsilon n$, $n$ being the size of the ground set. The idea originated in the context of learning theory and was introduced by Haussler and Welzl in 1987. With a delicate use of random sampling, they showed that any set system of finite VC dimension has an $epsilon$-net of small size independent of the size of the set system - and moreover a random sample of this size is an $epsilon$-net with high probability. Epsilon nets are now an important tool that has found applications in many areas including computational geometry, approximation algorithms, discrepancy theory and statistics. Very simple and deterministic constructions were found by Matousek in 1991. Deterministic algorithms for computing $epsilon$-nets have turned them into a general tool for divide & conquer and for derandomization - many of the sophisticated data structures and algorithms are based on $epsilon$-nets. They power tools like cuttings and simplicial partitions that are among the finest algorithmic tools in geometry. Besides algorithmic applications, they have have been used for the proof of other combinatorial results. Recent research on Epsilon nets and related problems has revealed further connections to other areas of mathematics.

In this talk I will give an introduction to $epsilon$-nets and the various related problems that I have worked on. I will describe my results on the construction of $epsilon$-nets, related geometric set cover problems, enumeration problems and weak $epsilon$-nets.