<p>The classical Steinitz theorem asserts that if the origin lies within the interior of the convex hull of a set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(S \subset {\mathbb {R}}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>, then there are at most 2<i>d</i> points in <i>S</i> whose convex hull contains the origin within its interior. Bárány, Katchalski, and Pach established a quantitative version of Steinitz’s theorem, showing that for a convex polytope <i>Q</i> in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\mathbb {R}}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation> containing the standard Euclidean unit ball <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textbf{B}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="bold">B</mi> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>, there exist at most 2<i>d</i> vertices of <i>Q</i> whose convex hull <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(Q'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>Q</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> satisfies <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(r\textbf{B}^d \subset Q' \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <msup> <mi mathvariant="bold">B</mi> <mi>d</mi> </msup> <mo>⊂</mo> <msup> <mi>Q</mi> <mo>′</mo> </msup> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(r \ge d^{-2d}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <msup> <mi>d</mi> <mrow> <mo>-</mo> <mn>2</mn> <mi>d</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. Recently, Márton Naszódi and the author derived a polynomial bound on <i>r</i>. This paper aims to establish a bound on <i>r</i> based on the number of vertices of <i>Q</i>. In other words, we demonstrate an effective method to remove several points from the original set <i>Q</i> without significantly altering the bound on <i>r</i>. Specifically, if the number of vertices of <i>Q</i> scales linearly with the dimension, i.e., <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\alpha d\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation>, then one can select 2<i>d</i> vertices such that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(r \ge \frac{1}{5 \alpha d}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mfrac> <mn>1</mn> <mrow> <mn>5</mn> <mi>α</mi> <mi>d</mi> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation>. The proof relies on a polarity trick, which may be of independent interest: we demonstrate the existence of a point <i>c</i> in the interior of a convex polytope <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(P \subset {\mathbb {R}}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>P</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> such that the vertices of the polar polytope <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\((P-c)^\circ \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <mi>P</mi> <mo>-</mo> <mi>c</mi> <mo stretchy="false">)</mo> </mrow> <mo>∘</mo> </msup> </math></EquationSource> </InlineEquation> sum up to zero.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantitative Steinitz Theorem and Polarity

  • Grigory Ivanov

摘要

The classical Steinitz theorem asserts that if the origin lies within the interior of the convex hull of a set \(S \subset {\mathbb {R}}^d\) S R d , then there are at most 2d points in S whose convex hull contains the origin within its interior. Bárány, Katchalski, and Pach established a quantitative version of Steinitz’s theorem, showing that for a convex polytope Q in \({\mathbb {R}}^d\) R d containing the standard Euclidean unit ball \(\textbf{B}^d\) B d , there exist at most 2d vertices of Q whose convex hull \(Q'\) Q satisfies \(r\textbf{B}^d \subset Q' \) r B d Q with \(r \ge d^{-2d}\) r d - 2 d . Recently, Márton Naszódi and the author derived a polynomial bound on r. This paper aims to establish a bound on r based on the number of vertices of Q. In other words, we demonstrate an effective method to remove several points from the original set Q without significantly altering the bound on r. Specifically, if the number of vertices of Q scales linearly with the dimension, i.e., \(\alpha d\) α d , then one can select 2d vertices such that \(r \ge \frac{1}{5 \alpha d}\) r 1 5 α d . The proof relies on a polarity trick, which may be of independent interest: we demonstrate the existence of a point c in the interior of a convex polytope \(P \subset {\mathbb {R}}^d\) P R d such that the vertices of the polar polytope \((P-c)^\circ \) ( P - c ) sum up to zero.