Quantitative Helly-Type Theorem for the Diameter of Convex Sets

详细信息    查看全文

• 作者：Silouanos Brazitikos
• 关键词：Convex bodies ; Helly’s theorem ; Approximate John’s decomposition ; Polytopal approximation
• 刊名：Discrete & Computational Geometry
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：57
• 期：2
• 页码：494-505
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1432-0444
• 卷排序：57

文摘

We provide a new quantitative version of Helly’s theorem: there exists an absolute constant \(\alpha >1\) with the following property. If \(\{P_i: i\in I\}\) is a finite family of convex bodies in \({\mathbb {R}}^n\) with \({\mathrm{int}} (\bigcap _{i\in I}P_i )\ne \emptyset \), then there exist \(z\in {\mathbb {R}}^n\), \(s\leqslant \alpha n\) and \(i_1,\ldots i_s\in I\) such that $$\begin{aligned} z+P_{i_1}\cap \cdots \cap P_{i_s}\subseteq cn^{3/2}\Big (z+\bigcap _{i\in I}P_i\Big ), \end{aligned}$$where \(c>0\) is an absolute constant. This directly gives a version of the “quantitative” diameter theorem of Bárá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(\sqrt{n})\).KeywordsConvex bodiesHelly’s theoremApproximate John’s decompositionPolytopal approximationEditor in Charge: János Pach