skip to content

A non-linear lower bound for planar epsilon-nets

Presented by: 
N Alon [Tel Aviv University and IAS, Princeton]
Tuesday 11th January 2011 - 15:30 to 16:30
INI Seminar Room 1
After a brief description of the notion of epsilon-nets for range spaces and of the main known results about them, I will show that the minimum possible size of an epsilon-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/epsilon. This settles a problem raised by Matousek, Seidel and Welzl in 1990.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons