New constructions of weak epsilon-nets Conference Paper

Author(s): Matoušek, Jiří; Wagner, Uli
Title: New constructions of weak epsilon-nets
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.
Keywords: Weak Epsilon-Nets
Conference Title: SoCG: Symposium on Computational Geometry
Conference Dates: June 8-10, 2003
Conference Location: San Diego, CA, USA
ISBN: 978-1-4503-2594-3
Publisher: ACM  
Date Published: 2003-06-01
Start Page: 129
End Page: 135
DOI: 10.1145/777792.777813
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work