论文标题
在密度限制的集合中查找凸位的位置
Finding Points in Convex Position in Density-Restricted Sets
论文作者
论文摘要
对于有限的集合$ a \ subset \ mathbb {r}^d $，让$δ（a）$表示$ a $的传播，这是最大成对距离与最小成对距离的比率。对于一个正整数$ n $，令$γ_d（n）$表示最大的整数，以便在$ \ mathbb {r}^d $中设置$ a $ n $点的一般位置，满足$Δ（a）\ leqleqαn^{1/d} $，compy $ n $ $ a的位置（cally $ a）的位置，至少为$ unders n $ n $ unige n $ unige。大约$ 30美元前，Valtr证明了$γ_2（n）=θ（n^{1/3}）$。从那时起，在较高的维度中没有得到进一步的结果。在这里，我们在三个维度上继续进行这一研究，并证明$γ_3（n）=θ（n^{1/2}）$。下限意味着以下近似值：给定任何$ n $ element点设置$ a \ subset \ mathbb {r}^3 $一般位置，满足$δ（a）\ leqleqαn^{1/3} $，用于固定$α$，a $ω（n^{ - 1/6}）$ - copte a $ a^$ copte cointer的最大值 - $ o（n \ log {n}）$预期时间的随机算法。
For a finite set $A\subset \mathbb{R}^d$, let $Δ(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 $γ_d(n)$ denote the largest integer such that any set $A$ of $n$ points in general position in $\mathbb{R}^d$, satisfying $Δ(A) \leq αn^{1/d}$ for a fixed $α>0$, contains at least $γ_d(n)$ points in convex position. About $30$ years ago, Valtr proved that $γ_2(n)=Θ(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 $γ_3(n) =Θ(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 $Δ(A) \leq αn^{1/3}$ for a fixed $α$, a $Ω(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.
