New constructions of weak \(\varepsilon\)-nets (Q1762945)

From MaRDI portal
scientific article
Language Label Description Also known as
English
New constructions of weak \(\varepsilon\)-nets
scientific article

    Statements

    New constructions of weak \(\varepsilon\)-nets (English)
    0 references
    0 references
    0 references
    11 February 2005
    0 references
    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))\).
    0 references
    0 references
    0 references