New constructions of weak \(\varepsilon\)-nets (Q1762945): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/s00454-004-1116-4 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S00454-004-1116-4 / rank | |||
Normal rank |
Latest revision as of 09:15, 11 December 2024
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
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