Weak -nets have basis of size o(1/ log (1/)) in any dimension

Nabil Mustafa, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given a set P of n points in Rd and > 0, we consider the problemof constructing weak -nets for P.We show the following: pick a random sample Q of size O(1/ log (1/)) from P. Then, with constant probability, a weak -net of P can be constructed from only the points of Q. This shows that weak -nets in Rd can be computed from a subset of P of size O(1/ log(1/)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/. However, our final weak -nets still have a large size (with the dimension appearing in the exponent of 1/).

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Number of pages6
StatePublished - 2007
Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
Duration: Jun 6 2007Jun 8 2007

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other23rd Annual Symposium on Computational Geometry, SCG'07
Country/TerritoryKorea, Republic of


  • Combinatorial geometry
  • Discrete geometry
  • Hitting convex sets
  • Weak epsilon nets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Weak -nets have basis of size o(1/ log (1/)) in any dimension'. Together they form a unique fingerprint.

Cite this