@article{4035,
abstract = {Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas.},
author = {Chazelle, Bernard and Edelsbrunner, Herbert and Grigni, Michelangelo and Guibas, Leonidas and Sharir, Micha and Welzl, Emo},
issn = {0179-5376},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {1 -- 15},
publisher = {Springer},
title = {{Improved bounds on weak ε-nets for convex sets}},
doi = {10.1007/BF02574025},
volume = {13},
year = {1995},
}