For a finite set $A\subset \mathbb{R}^d$, let $\Delta(A)$ denote the spread of $A$, which is the ratio of the maximum pairwise distance to the minimum pairwise distance. For a positive integer $n$, let $\gamma_d(n)$ denote the largest integer such that any set $A$ of $n$ points in general position in $\mathbb{R}^d$, satisfying $\Delta(A) \leq \alpha n^{1/d}$ for a fixed $\alpha>0$, contains at least $\gamma_d(n)$ points in convex position. About $30$ years ago, Valtr proved that $\gamma_2(n)=\Theta(n^{1/3})$. Since then no further results have been obtained in higher dimensions. Here we continue this line of research in three dimensions and prove that $\gamma_3(n) =\Theta(n^{1/2})$. The lower bound implies the following approximation: Given any $n$-element point set $A\subset \mathbb{R}^3$ in general position, satisfying $\Delta(A) \leq \alpha n^{1/3}$ for a fixed $\alpha$, a $\Omega(n^{-1/6})$-factor approximation of the maximum-size convex subset of points can be computed by a randomized algorithm in $O(n \log{n})$ expected time.
翻译:对于限定值 $A\ subset {mathb{R} 美元, 美元=Delta(A) 美元表示固定 $a$, 也就是最大对称距离与最小对称距离之比。 正整数$, 美元=gamma_ d(n) 表示最大整数, 以$\mathbb{R} 美元表示任何设定的总价为美元( mathbb{R} 美元, 满足美元\Delta(A)\leq =alpha n ⁇ 1/d} 美元, 固定值中至少包含$\ gamma_ d(n) 点。 大约30美元前, Valtr 证明$\ gamma_ (n) {Theta (n_1/3} 美元。 自此以后没有在更高维度上获得任何进一步结果。 我们在这里继续进行三维的研究, 并证明 美元=climal_ 3 (n) a_ a_ a_ dal_ dal_ minalxalal_ a.