Convex polytopes in restricted point sets in ${\mathbb{R}}^d$

Abstract

For a finite point set $P\subset {\mathbb{R}}^d$, denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d,\hat{I}\pm }(n)$ be the largest integer $c$ such that any $n$-point set $P\subset {\mathbb{R}}^d$ in general position, satisfying $\text{diam}(P)<\hat{I}\pm \sqrt[d]{n}$, contains an $c$-point convex independent subset. We determine the asymptotics of $c_{d,\hat{I}\pm }(n)$ as $n\to \infty$ by showing the existence of positive constants ${\hat{I}}^2={\hat{I}}^2(d,\hat{I}\pm )$ and ${\hat{I}}^3={\hat{I}}^3(d)$ such that ${\hat{I}}^2{n}^{\frac{d-1}{d+1}}\le c_{d,\hat{I}\pm }(n)\le {\hat{I}}^3{n}^{\frac{d-1}{d+1}}$ for $\hat{I}\pm \ge 2$.

30 pages, 2 figures; added more detailed explanations throughout the paper