MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a set of $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$, for some $n \gg d$. Suppose $\{x_1,\ldots,x_n\} \subset C \subset \mathbb{R}^d$. Say that a set of points $y_1,\ldots,y_m \in C$ covers $x_1,\ldots,x_n$ if $x_1,\ldots,x_m$ lie inside the convex hull of $y_1,\ldots,y_m$.

Are there known conditions under which a set of $n$ points has a cover of size $m$ in some set $C$, for $m$ much smaller than $n$? Clearly, if $C$ contains the $\ell_\infty$ ball of radius $\max_i ||x_i||_1$, then there is a cover of size at most $d$ (i.e. a scaling of the simplex) -- but what if $C$ is smaller? e.g. what if $C$ is only contains the infinity ball of radius $\sqrt{\max_i ||x_i||_1}$?

More generally, is there a literature that studies these kinds of problems?

share|cite|improve this question
One term that will lead you to related literature is the notion of a core set. E.g., P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. "Geometric approximation via core-sets." In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry, volume 52 of MSRI Publications. Cambridge University Press, 2005. – Joseph O'Rourke Apr 24 '13 at 13:53
you could consider $(\max_i ||x_i||_1)^{1/2+\epsilon}$ and try to minimize $\epsilon$. your conjecture is with $\epsilon =0$. – Jon Mark Perry May 24 '15 at 4:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.