IMPROVED BOUNDS ON WEAK EPSILON-NETS FOR CONVEX-SETS

Let S be a set of n points in R(d). A set W is a weak epsilon-net for (convex ranges of) S if, for any T subset-or-equal-to S containing epsilonn points, the convex hull of T intersects W. We show the existence of weak epsilon-nets of size O((1/epsilon(d)) log(beta(d))(1/epsilon)), where beta2 = 0, beta3 = 1, and beta(d) almost-equal-to 0.149 . 2(d-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/epsilon) log1.6(1/epsilon)). 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/epsilon), which improves a previous bound of Capoyleas.