---
_id: '2423'
abstract:
- lang: eng
text: 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.
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: ACM; 2003:129-135.
doi:10.1145/777792.777813'
apa: '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'
chicago: Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets,”
129–35. ACM, 2003. https://doi.org/10.1145/777792.777813.
ieee: 'J. Matoušek and U. Wagner, “New constructions of weak epsilon-nets,” presented
at the SoCG: Symposium on Computational Geometry, 2003, pp. 129–135.'
ista: 'Matoušek J, Wagner U. 2003. New constructions of weak epsilon-nets. SoCG:
Symposium on Computational Geometry, 129–135.'
mla: Matoušek, Jiří, and Uli Wagner. *New Constructions of Weak Epsilon-Nets*.
ACM, 2003, pp. 129–35, doi:10.1145/777792.777813.
short: J. Matoušek, U. Wagner, in:, ACM, 2003, pp. 129–135.
conference:
name: 'SoCG: Symposium on Computational Geometry'
date_created: 2018-12-11T11:57:34Z
date_published: 2003-06-01T00:00:00Z
date_updated: 2021-01-12T06:57:24Z
day: '01'
doi: 10.1145/777792.777813
extern: 1
month: '06'
page: 129 - 135
publication_status: published
publisher: ACM
publist_id: '4502'
quality_controlled: 0
status: public
title: New constructions of weak epsilon-nets
type: conference
year: '2003'
...