Improving the exponential lower bound for peeling sequences
Let $d \ge 2$, and let $P \subset \mathbb{R}^d$ be a finite set in general position, that is, any at most $d + 1$ of its points are affinely independent. A peeling sequence of $P$ is an ordering $(p_1, \ldots, p_n)$ of $P$ in which each $p_i$ is a vertex of $\operatorname{conv}\{p_i, p_{i+1}, \ldots, p_n\}$. Let $g_d(P)$ be the number of peeling sequences of $P$, and $g_d(n)$ the minimum of $g_d(P)$ over all $n$-point sets $P$ in general position. Dumitrescu and Tóth proved that $g_d(n) = \Omega((d + 1)^n)$, since while more than $d$ points remain their convex hull has at least $d + 1$ vertices, together with exponential upper bounds. Simon proved $g_d(n) = O\big((d + d \ln d)^{(2 + (d - 1)/\lfloor d \ln d \rfloor) n}\big)$ for every fixed $d \ge 3$. In the plane, Dumitrescu and Tóth proved $g_2(n) \le 12.29^n / 100$, and the upper bound has since been lowered, to $O(6.57^n)$ by Simon (2026).
Problem. Prove or disprove that for every fixed $d \ge 2$ there are constants $\varepsilon_d > 0$ and $c_d > 0$, independent of $n$, such that $$g_d(n) \ge c_d (d + 1 + \varepsilon_d)^n \qquad (n \ge 1).$$
Source: Dumitrescu and Tóth (2025), Problem 1, in the plane; conjectured in every dimension by Simon (2026), Conjecture 1 (Conjecture 10 in arXiv:2312.00244v2).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, convex hulls, peeling sequences, point sets
References
@article{dumitrescu2025,
author = {Dumitrescu, Adrian and T{\'o}th, G{\'e}za},
title = {Peeling sequences},
journal = {Discrete Comput. Geom.},
volume = {73},
number = {3},
year = {2025},
pages = {837--849},
doi = {10.1007/s00454-023-00616-8},
eprint = {2211.05968},
archivePrefix = {arXiv},
}
@article{simon2026,
author = {Simon, D{\'a}niel G.},
title = {The minimum number of peeling sequences of a point set},
journal = {Discrete Comput. Geom.},
volume = {75},
number = {4},
year = {2026},
pages = {1122--1133},
doi = {10.1007/s00454-024-00713-2},
eprint = {2312.00244},
archivePrefix = {arXiv},
}
@misc{simon2026directional,
author = {Simon, D{\'a}niel G{\'a}bor},
title = {Peeling sequences: a directional method for the three-block construction},
year = {2026},
eprint = {2609.19540},
archivePrefix = {arXiv},
}
@misc{aim-peeling-sequences-lower-base,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Improving the exponential lower bound for peeling sequences}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/566-peeling-sequences-lower-base.md},
note = {Entry 566 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-00886, "Improving the exponential lower bound for peeling sequences", clopen.solutions.