article
A quantitative Helly-type theorem: Containment in a homothet
published
yes
Grigory
Ivanov
author 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
Marton
Naszodi
author
UlWa
department
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 Mathematics2022
eng
SIAM Journal on Discrete Mathematics
0895-4801
2103.04122
00079315820000210.1137/21M1403308
362951-957
Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2022. <a href="https://doi.org/10.1137/21M1403308">https://doi.org/10.1137/21M1403308</a>.
Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.
G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.
Ivanov, G., & Naszodi, M. (2022). A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/21M1403308">https://doi.org/10.1137/21M1403308</a>
G. Ivanov and M. Naszodi, “A quantitative Helly-type theorem: Containment in a homothet,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2. Society for Industrial and Applied Mathematics, pp. 951–957, 2022.
Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2, Society for Industrial and Applied Mathematics, 2022, pp. 951–57, doi:<a href="https://doi.org/10.1137/21M1403308">10.1137/21M1403308</a>.
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>
114352022-06-05T22:01:50Z2023-10-18T06:58:03Z