One-sided epsilon-approximants

Abstract

Given a finite point set $P\subset {\mathbb{R}}^d$, we call a multiset $A$ a one-sided weak $\epsilon$-approximant for $P$ (with respect to convex sets), if $|P\cap C|/|P|-|A\cap C|/|A|\le \epsilon$ for every convex set $C$. We show that, in contrast with the usual (two-sided) weak $\epsilon$-approximants, for every set $P\subset {\mathbb{R}}^d$ there exists a one-sided weak $\epsilon$-approximant of size bounded by a function of $\epsilon$ and $d$.

14 pages