Quantitative Helly-type theorem for the diameter of convex sets

DOI10.1007/S00454-016-9840-0zbMATH Open1368.52001arXiv1511.07779OpenAlexW2551850732MaRDI QIDQ517461FDOQ517461

Silouanos Brazitikos

Publication date: 23 March 2017

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We provide a new quantitative version of Helly's theorem: there exists an absolute constant $alpha>1$ with the following property: if $P_i:iinI$ is a finite family of convex bodies in ${mathbbR}^n$ with $$, then there exist $zin{mathbbR}^n$, $sleqalphan$ and $i_1,ldots{i}_{s}inI$ such that �egin{equation*} z+P_{i_1}capcdotscap P_{i_s}subseteq cn^{3/2}left(z+�igcap_{iin I}P_i ight), end{equation*} where $c>0$ is an absolute constant. This directly gives a version of the "quantitative" diameter theorem of B'{a}r'{a}ny, Katchalski and Pach, with a polynomial dependence on the dimension. In the symmetric case the bound $O(n^{3/2})$ can be improved to $O(sqrtn)$.

Full work available at URL: https://arxiv.org/abs/1511.07779

Recommendations

• A quantitative Helly-type theorem: containment in a homothet
• Polynomial esimates towards a sharp Helly-type theorem for the diameter of convex sets
• Helly-type theorems for the diameter
• A mélange of diameter Helly-type theorems
• Quantitative fractional Helly and \((p,q)\)-theorems

zbMATH Keywords

convex bodiesHelly's theoremapproximate John's decompositionpolytopal approximation

Mathematics Subject Classification ID

Asymptotic theory of Banach spaces (46B06) Asymptotic theory of convex bodies (52A23) Helly-type theorems and geometric transversal theory (52A35)

Cites Work

• Asymptotic Geometric Analysis, Part I
• Convex Bodies The Brunn-MinkowskiTheory
• Title not available (Why is that?)
• Gelfand numbers of operators with values in a Hilbert space
• Twice-ramanujan sparsifiers
• A Remark on Vertex Index of the Convex Bodies
• Thrifty Approximations of Convex Bodies by Polytopes
• Title not available (Why is that?)
• BRASCAMP–LIEB INEQUALITY AND QUANTITATIVE VERSIONS OF HELLY'S THEOREM
• Helly's Theorem with Volumes
• Convex Bodies with Few Faces
• Quantitative Helly-Type Theorems
• On Contact Points of Convex Bodies
• Random approximation and the vertex index of convex bodies
• Approximating Matrices and Convex Bodies
• Proof of a conjecture of Bárány, Katchalski and Pach

Cited In (14)

• Helly-type theorems for the diameter
• Isometric and affine copies of a set in volumetric Helly results
• Quantitative combinatorial geometry for concave functions
• Quantitative Helly-type theorems via sparse approximation
• A Mélange of Diameter Helly-Type Theorems
• Helly-type problems
• Title not available (Why is that?)
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• A Helly-type theorem for unions of convex sets
• A Quantitative Helly-Type Theorem: Containment in a Homothet
• Continuous quantitative Helly-type results
• Random approximation and the vertex index of convex bodies
• The norm of linear extension operators for \(C^{m-1,1}(\mathbb{R}^n)\)
• Quantitative versions of almost squareness and diameter 2 properties

This page was built for publication: Quantitative Helly-type theorem for the diameter of convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517461)