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.
기초과학연구원 이산수학그룹