Skip to content

DAN

Seminar

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

Abstract

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.

Video

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 ∧