An Improved Bound for Weak Epsilon-Nets in the Plane, by Nathan Rubin, is on the arXive

The paper An Improved Bound for Weak Epsilon-Nets in the Plane, by Nathan Rubin is now on the arxive. we mentioned  the result in this post, and the problem in this post (my very first) over Tao’s blog What’s New.

Abstract: We show that for any finite set P of points in the plane and ϵ>0 there exist O(1/\epsilon^{3/2+\gamma}) points in \mathbb R^2, for arbitrary small γ>0, that pierce every convex set K with |KP|ϵ|P|.

This is the first improvement of the bound of O(1/\epsilon^2)  that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.

Advertisements
This entry was posted in Combinatorics, Geometry and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s