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

Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticle

Abstract

Given a set P of n points in ℝ d and >0, we consider the problem of 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 ℝ d 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)
Pages (from-to)84-91
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume40
Issue number1
DOIs
StatePublished - May 2008

Keywords

  • Combinatorial geometry
  • Hitting convex sets
  • Weak -nets

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • 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