Quantitative Helly-type theorems via sparse approximation

Abstract

We prove the following sparse approximation result for polytopes. Assume that $Q$ is a polytope in John's position. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q^{\prime }$ satisfies $Q\subseteq -2d^2{Q}^{\prime }$. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Naszódi: We prove that given a finite family $\mathcal{F}$ of convex bodies in ${\mathbb{R}}^d$ with intersection $K$, we may select at most $2d$ members of $\mathcal{F}$ such that their intersection has volume at most $(cd{)}^{3d/2}\mathrm{vol}K$, and it has diameter at most $2d^2\mathrm{diam}K$, for some absolute constant $c>0$.

Final version, to appear in Discrete and Computational Geometry