New constructions of weak epsilon-nets

J. Matoušek, U. Wagner, in:, ACM, 2003, pp. 129–135.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
;
Abstract
A finite set N ⊃ Rd is a weak ε-net for an n-point set X ⊃ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. [7], that every point set X in Rd admits a weak ε-net of cardinality O(ε-d polylog(1/ε)). 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 ε-nets in time O(n ln(1/ε)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d - 1)-dimensional sphere.
Publishing Year
Date Published
2003-06-01
Page
129 - 135
Conference
SoCG: Symposium on Computational Geometry
IST-REx-ID

Cite this

Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: ACM; 2003:129-135. doi:10.1145/777792.777813
Matoušek, J., & Wagner, U. (2003). New constructions of weak epsilon-nets (pp. 129–135). Presented at the SoCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/777792.777813
Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets,” 129–35. ACM, 2003. https://doi.org/10.1145/777792.777813.
J. Matoušek and U. Wagner, “New constructions of weak epsilon-nets,” presented at the SoCG: Symposium on Computational Geometry, 2003, pp. 129–135.
Matoušek J, Wagner U. 2003. New constructions of weak epsilon-nets. SoCG: Symposium on Computational Geometry 129–135.
Matoušek, Jiří, and Uli Wagner. New Constructions of Weak Epsilon-Nets. ACM, 2003, pp. 129–35, doi:10.1145/777792.777813.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar