The sharp radius in quantitative Steinitz selection
Let $B^d$ be the closed Euclidean unit ball of $\mathbb{R}^d$. By Steinitz's theorem, if the origin is an interior point of the convex hull of a set $Q \subset \mathbb{R}^d$, it is an interior point of the convex hull of at most $2d$ points of $Q$. Bárány, Katchalski and Pach proved a quantitative version: there is $r(d) > 0$ such that whenever $B^d \subseteq \operatorname{conv}(Q)$, some $F \subseteq Q$ with $|F| \le 2d$ satisfies $r(d) B^d \subseteq \operatorname{conv}(F)$, and $r(d) = d^{-2d}$ will do. Ivanov and Naszódi proved that $r(d) = 1/(6d^2)$ will do, and that no $r(d)$ larger than $2/\sqrt{d}$ works. Ivanov proved that if $Q$ has $\alpha d$ points, $\alpha > 1$, one may take $r = 1/(5\alpha d)$.
Problem. Is there an absolute constant $c > 0$ such that for every integer $d \ge 2$ and every finite set $Q \subset \mathbb{R}^d$ with $B^d \subseteq \operatorname{conv}(Q)$ there is a subset $F \subseteq Q$ with $|F| \le 2d$ and $$\frac{c}{\sqrt{d}}\, B^d \subseteq \operatorname{conv}(F)?$$ Both balls are centred at the origin, and $c$ may not depend on the dimension, on the number of points or on their positions.
Source: Bárány, Katchalski and Pach (1982), as reported by Ivanov and Naszódi (2024), who restate it as their Conjecture 1.1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, convex hulls, quantitative Steinitz theorems, sparse approximation
References
@article{barany1982,
author = {B{\'a}r{\'a}ny, Imre and Katchalski, Meir and Pach, J{\'a}nos},
title = {Quantitative {H}elly-type theorems},
journal = {Proc. Amer. Math. Soc.},
volume = {86},
number = {1},
year = {1982},
pages = {109--114},
doi = {10.1090/S0002-9939-1982-0663877-X},
}
@article{ivanov2024,
author = {Ivanov, Grigory and Nasz{\'o}di, M{\'a}rton},
title = {Quantitative {S}teinitz theorem: a polynomial bound},
journal = {Bull. Lond. Math. Soc.},
volume = {56},
number = {2},
year = {2024},
pages = {796--802},
doi = {10.1112/blms.12965},
eprint = {2212.04308},
archivePrefix = {arXiv},
}
@article{ivanov2026,
author = {Ivanov, Grigory},
title = {Quantitative {S}teinitz theorem and polarity},
journal = {Discrete Comput. Geom.},
volume = {75},
number = {4},
year = {2026},
pages = {1405--1413},
doi = {10.1007/s00454-025-00743-4},
eprint = {2403.14761},
archivePrefix = {arXiv},
}
@misc{aim-quantitative-steinitz-radius,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp radius in quantitative Steinitz selection}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/564-quantitative-steinitz-radius.md},
note = {Entry 564 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00894, "The sharp radius in quantitative Steinitz selection", clopen.solutions.