An Improved Bound for Weak Epsilon-Nets in the Plane
An Improved Bound for Weak Epsilon-Nets in the Plane
复制标题
平面上弱 Epsilon 网的改进界限
DOI：
10.1145/3555985
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Natan Rubin
中科院分区：
文献类型：
--
作者：
Natan Rubin
我们证明了对于平面上的任意有限点集P，ε>0，存在O（1/ε^3/2+γ）个点，对于任意小的γ>0，它们穿透每个凸集K，|K P| ≥ ε |P|.这是对1992年Alon，Bárány，Füredi和Kleitman在平面上一般点集上得到的O（1）ε^2）的界的第一次改进。
We show that for any finite point set P in the plane and ε>0 there exist O(1/ε^3/2+γ) points, for arbitrary small γ>0, that pierce every convex set K with |K∩ P|≥ ε |P|. This is the first improvement of the bound of O(1)ε^2) that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.