New constructions of weak ε-nets

A finite set N ⊂ Rd is a weak ε-net for an n-point set X ⊂ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set X in Rd admits a weak ε-net of cardinality O(ε-dpolylog(1/ε)). 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 ε-nets in time O(n ln(1/ε)).