Improved Bounds on Weak ϵ-Nets for Convex Sets

Let S be a set of n points in R, . A set W is a weak e-net for (convex ranges of) S if for any T C S containing en points, the convex hull of T intersects W. We show the existence of weak ϵ-nets of size O (1/ϵdlogβd1/ϵ), where β2 = 0, β3 = 1, and βd ≈0.149 . 2^d-1!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time (1/ϵ)^O(1). 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 0(1/ϵ log 1.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 0(l/ϵ), which improves a previous bound of Capoyleas.