Computer Science Colloquium
Epsilon-nets and Related Problems
Saurabh Ray, Max-Planck-Institut Informatik
February 27, 2013
Warren Weaver hall, 1302
251 Mercer Street
New York, NY 10012
Spring 2013 Colloquia Calendar
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 & 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.