New constructions of weak ε-nets
Matoušek J, Wagner U. 2004. New constructions of weak ε-nets. Discrete & Computational Geometry. 32(2), 195–206.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
Author
Matoušek, Jiří;
Wagner, UliISTA 
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., that every point set X in Rd admits a weak ε-net of cardinality O(ε-dpolylog(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/ε)).
Publishing Year
Date Published
2004-07-01
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Volume
32
Issue
2
Page
195 - 206
IST-REx-ID
Cite this
Matoušek J, Wagner U. New constructions of weak ε-nets. Discrete & Computational Geometry. 2004;32(2):195-206. doi:10.1007/s00454-004-1116-4
Matoušek, J., & Wagner, U. (2004). New constructions of weak ε-nets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-004-1116-4
Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry. Springer, 2004. https://doi.org/10.1007/s00454-004-1116-4.
J. Matoušek and U. Wagner, “New constructions of weak ε-nets,” Discrete & Computational Geometry, vol. 32, no. 2. Springer, pp. 195–206, 2004.
Matoušek J, Wagner U. 2004. New constructions of weak ε-nets. Discrete & Computational Geometry. 32(2), 195–206.
Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry, vol. 32, no. 2, Springer, 2004, pp. 195–206, doi:10.1007/s00454-004-1116-4.
Google Scholar