New constructions of weak \(\varepsilon\)-nets (Q1762945): Difference between revisions

A finite set \(N \subset \mathbb R^d\) is a weak \(\varepsilon\)-net for an \(n\)-point set \(X\subset \mathbb R^d\) (with respect to convex sets) if \(N\) intersects every convex set \(K\) with \(|K \cap X|\geq \varepsilon\). We give an alternative, and arguably simpler, proof of the fact, first shown by \textit{B. Chazelle}, \textit{H. Edelsbrunner}, \textit{M. Grigni}, \textit{L. Guibas}, \textit{M. Sharir} and \textit{E. Welzl} [ibid. 13, 1--15 (1995; Zbl 0822.68110)], that every point set \(X\) in \(\mathbb R^d\) admits a weak \(\varepsilon\)-net of cardinality \(O(\varepsilon^{-d}\text{polylog}(1/\varepsilon))\). 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 \(\varepsilon\)-nets in time \(O(n\ln(1/\varepsilon))\).