### 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.

## Comments

Start the discussion!