The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



A non-linear lower bound for planar epsilon-nets

Alon, N (Tel Aviv University and IAS, Princeton)
Tuesday 11 January 2011, 15:30-16:30

Seminar Room 1, Newton Institute


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.

Back to top ∧