New constructions of weak epsilon-nets
Matoušek, Jiří
Uli Wagner
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.
ACM
2003
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/2423
Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: ACM; 2003:129-135. doi:<a href="https://doi.org/10.1145/777792.777813">10.1145/777792.777813</a>
info:eu-repo/semantics/altIdentifier/doi/10.1145/777792.777813
info:eu-repo/semantics/closedAccess