Given a finite point set $Psubsetmathbb{R}^d$, we call a multiset $A$ a one-sided weak $varepsilon$-approximant for $P$ (with respect to convex sets), if $|Pcap C|/|P|-|Acap C|/|A|leqvarepsilon$ for every convex set $C$. We show that, in contrast with the usual (two-sided) weak $varepsilon$-approximants, for every set $Psubset mathbb{R}^d$ there exists a one-sided weak $varepsilon$-approximant of size bounded by a function of $varepsilon$ and $d$.
تحميل البحث