New constructions of weak ε-nets

J. Matoušek, U. Wagner, Discrete & Computational Geometry 32 (2004) 195–206.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Matoušek, Jiří; Wagner, UliIST Austria
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
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, 32(2), 195–206. https://doi.org/10.1007/s00454-004-1116-4
Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry 32, no. 2 (2004): 195–206. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar