Item

Abstract

Given a set P of n points in Rd and $\epsilon$ > 0, we consider the problem of constructing weak $\epsilon$-nets for P. We show the following: pick a random sample Q of size O(1/$\epsilon$ log (1/$\epsilon$)) from P. Then, with constant probability, a weak $\epsilon$-net of P can be constructed from only the points of Q. This shows that weak $\epsilon$-nets in Rd can be computed from a subset of P of size O(1/$\epsilon$ log (1/$\epsilon$)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/$\epsilon$. However, our final weak $\epsilon$-nets still have a large size (with the dimension appearing in the exponent of 1/$\epsilon$).