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?

  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Apr 24 '13 at 13:53
  • $\begingroup$ you could consider $(\max_i ||x_i||_1)^{1/2+\epsilon}$ and try to minimize $\epsilon$. your conjecture is with $\epsilon =0$. $\endgroup$ – JonMark Perry May 24 '15 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.