Computer Science Colloquium

Epsilon-nets and Related Problems

Saurabh Ray, Max-Planck-Institut Informatik

February 27, 2013 11:30AM
Warren Weaver hall, 1302
251 Mercer Street
New York, NY 10012

Spring 2013 Colloquia Calendar


Dennis Shasha


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.

top | contact webmaster