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

Abstract

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
Pages239-244
Number of pages6
DOIs
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

Other

Other23rd Annual Symposium on Computational Geometry, SCG'07
CountryKorea, Republic of
CityGyeongju
Period6/6/076/8/07

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint 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