Home > Reprint of: Weak epsilon-nets have basis of size O(1/epsilonlog(1/epsilon)) in any dimension |

Given a set P of n points in R-d and epsilon > 0, we consider the problem of constructing weak E-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 R-d 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). (C) 2010 Published by Elsevier B.V.

- Export as: BibTeX | MARC | MARCXML | DC | EndNote | NLM | RefWorks | RIS
- View as: MARC | MARCXML | DC
- Add to your basket:

Record created 2010-11-26, last modified 2018-03-17