hide
Free keywords:
-
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$).
