Personal tools
You are here: Home CG seminar 2018 An improved bound for weak epsilon nets in the plane
« September 2018 »
September
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

An improved bound for weak epsilon nets in the plane

Wednesday, May 2nd, 2018, 16:10

Schreiber 309

underline

An improved bound for weak epsilon nets in the plane

Natan Rubin, Ben Gurion University

Abstract: 

We show that for any set $P$ of $n$ points in the plane and $\eps>0$ there exists a set of $O(1/\eps^{1.5+\gamma})$ points in the plane, for any \gamma>0, that pierce every convex set $K$ containing at least $\eps |P|$ points of P. This is the first improvement of the 1992 upper bound $O(1/eps^2)$ of Alon, Bárány, Füredi, and Kleitman.

Document Actions