New constructions of weak epsilon-nets
Jivri Matouaek · 2003
A finite set ? ? Rd is a weak e-net for an n -point set X ? R d (with respect to convex sets) if N intersects every convex set K with | K n X |= en. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. [7], that every point set X in R d admits a weak e-net of cardinality O (e -d polylog(1/e)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak eps-nets in time O ( n ln(1e)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d--1)-dimensional sphere.