View Related Documents

Abstract

A finite set N Ì \RdN \subset \R^d is a {\em weak \eps\eps-net} for an nn-point set X Ì \RdX\subset \R^d (with respect to convex sets) if NN intersects every convex set KK with |K Ç X| ³ \eps n|K\,\cap\,X|\geq \eps n. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set XX in \Rd\R^d admits a weak \eps\eps-net of cardinality O(\eps-d\polylog(1/\eps))O(\eps^{-d}\polylog(1/\eps)). 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\eps-nets in time O(nln(1/\eps))O(n\ln(1/\eps)).

Fulltext Preview

Image of the first page of the fulltext document