One-sided epsilon-approximants

2016/03/17 by Bukh, Boris, Gabriel Nivasch, Nivasch, Gabriel
Neuroscience · Mathematics · #Nuclear Receptors and Signaling #Approximation Theory and Sequence Spaces #Advanced Banach Space Theory

paper · pdf · doi:10.48550/arxiv.1603.05717

Abstract

Given a finite point set P⊂ℝ^d, we call a multiset A a one-sided weak ε-approximant for P (with respect to convex sets), if |P∩ C|/|P|-|A∩ C|/|A|≤ε for every convex set C. We show that, in contrast with the usual (two-sided) weak ε-approximants, for every set P⊂ ℝ^d there exists a one-sided weak ε-approximant of size bounded by a function of ε and d.

Related

• Weighted Epsilon-Nets
• An Improved Bound for Weak Epsilon-Nets in the Plane
• Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
• Approximating a convex body by a polytope using the epsilon-net theorem
• Fine approximation of convex bodies by polytopes