One-sided epsilon-approximants

We introduce the notion of "one-sided epsilon-approximants", which is in strength between epsilon-nets and usual (two-sided) epsilon-approximants. Given an n-point set P in R^d, a one-sided epsilon-approximant for P (with respect to convex sets) is a multiset A such that, for every convex set C, we have |P cap C|/|P| - |A cap C|/|A| <= epsilon.

We show that, in contrast with the usual epsilon-approximants, every P has a one-sided epsilon-approximant with respect to convex sets of size g(eps, d) for some g, but independent of n.

Unfortunately, due to the use of a geometric Ramsey theorem, our bound is very weak: g(eps, d) <= 2^2^...^2^(1/epsilon)^c, with d-1 2's.

For more info, see arXiv:1603.05717

Joint work with Boris Bukh.