Zichao Dong, Convex polytopes in non-elongated point sets in ${\mathbb{R}}^d$

For any finite point set $P\subset {\mathbb{R}}^d$, we denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d,\alpha }(n)$ be the largest integer $c$ such that any $n$-point set $P\subset {\mathbb{R}}^d$ in general position, satisfying $\text{diam}(P)<\alpha \sqrt[d]{n}$ (informally speaking, `non-elongated’), contains a convex $c$-polytope. Valtr proved that $c_{2,\alpha }(n)\approx \sqrt[3]{n}$, which is asymptotically tight in the plane. We generalize the results by establishing $c_{d,\alpha }(n)\approx n^{\frac{d-1}{d+1}}$. Along the way we generalize the definitions and analysis of convex cups and caps to higher dimensions, which may be of independent interest. Joint work with Boris Bukh.