# A quantitative Helly-type theorem: Containment in a homothet

Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Ivanov, GrigoryISTA; Naszodi, Marton
Department
Abstract
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}.$
Publishing Year
Date Published
2022-04-11
Journal Title
SIAM Journal on Discrete Mathematics
Acknowledgement
G.I. acknowledges the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926. M.N. was supported by the National Research, Development and Innovation Fund (NRDI) grants K119670 and KKP-133864 as well as the Bolyai Scholarship of the Hungarian Academy of Sciences and the New National Excellence Programme and the TKP2020-NKA-06 program provided by the NRDI.
Volume
36
Issue
2
Page
951-957
ISSN
IST-REx-ID

### Cite this

Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 2022;36(2):951-957. doi:10.1137/21M1403308
Ivanov, G., & Naszodi, M. (2022). A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. SIAM. https://doi.org/10.1137/21M1403308
Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” SIAM Journal on Discrete Mathematics. SIAM, 2022. https://doi.org/10.1137/21M1403308.
G. Ivanov and M. Naszodi, “A quantitative Helly-type theorem: Containment in a homothet,” SIAM Journal on Discrete Mathematics, vol. 36, no. 2. SIAM, pp. 951–957, 2022.
Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.
Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” SIAM Journal on Discrete Mathematics, vol. 36, no. 2, SIAM, 2022, pp. 951–57, doi:10.1137/21M1403308.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
Open Access

### Export

Marked Publications

Open Data ISTA Research Explorer

arXiv 2103.04122