Natan Rubin
Senior Academic
An Improved Bound for Weak Epsilon-nets in the Plane
We show that for any finite point set P in the plane and ϵ > 0 there exist O(ϵ3/12+γ ) points in R2, for arbitrary small γ > 0, that pierce every convex set K with |K ∩ P| ≥ ϵ|P|. This is the first improvement of the bound of O(ϵ12 ) that was obtained in 1992 by Alon, Bárány, Füredi, and Kleitman for general point sets in the plane.
| Publication language | English |
| Journal | Journal of the ACM |
| Volume | 69 |
| Issue number | 5 |
| Publication status | Published - 27.10.2022 |
| Article Number | ART32 |
Keywords
Epsilon-nets
VC-dimension
arrangements of lines
convex sets
geometric transversals
piercing numbers
ASJC Scopus subject areas
Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence
