Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

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.