Epsilon-nets and Related Problems

Speaker: Saurabh Ray, Max Planck Institute für Informatik

Abstract: Since their introduction by Haussler and Welzl in 1987, Epsilon-nets have become a central tool in computational geometry and have found several applications in approximation algorithms, discrepancy theory and statistics. Deterministic algorithms for computing Epsilon-nets have turned them into a general tool for divide and 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 also been used for proving combinatorial results. Recent research on Epsilon-nets and related problems has revealed further connections to other areas of mathematics.

I will give a brief introduction to Epsilon-nets and the some of the related problems that I have worked on. I will focus mainly on an algorithm for approximating minimum hitting sets.