A quantitative Helly-type theorem: Containment in a homothet
Ivanov, Grigory
Naszodi, Marton
We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \subset {\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\prime \prime}$ satisfies $Q \subset - 8d^3 Q^{\prime \prime}.$
Society for Industrial and Applied Mathematics
2022
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/11435
Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. 2022;36(2):951-957. doi:<a href="https://doi.org/10.1137/21M1403308">10.1137/21M1403308</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1137/21M1403308
info:eu-repo/semantics/altIdentifier/issn/0895-4801
info:eu-repo/semantics/altIdentifier/wos/000793158200002
info:eu-repo/semantics/altIdentifier/arxiv/2103.04122
info:eu-repo/semantics/openAccess