论文标题
随机Tukey层和凸面的预期大小
Expected Size of Random Tukey Layers and Convex Layers
论文作者
论文摘要
我们研究了平面点集的Tukey层和凸面层，该层由$ n $点组成，独立且均匀地从带有$ K $顶点的凸多边形进行采样。我们表明，第一个$ t $ tukey层上的预期顶点是$ o \ left（kt \ log（n/k）\右）$，并且第一个$ t $ convex层上的预期顶点是$ o \ o \ left（kt^{3} \ log log（n/（kt^2）\ right）$。在$ k = 3,4 $的特殊情况下，我们还显示了这两个量的$ω（t \ log n）$的下限。然后讨论了这些结果在两种计算几何算法的平均案例分析中的含义。
We study the Tukey layers and convex layers of a planar point set, which consists of $n$ points independently and uniformly sampled from a convex polygon with $k$ vertices. We show that the expected number of vertices on the first $t$ Tukey layers is $O\left(kt\log(n/k)\right)$ and the expected number of vertices on the first $t$ convex layers is $O\left(kt^{3}\log(n/(kt^2))\right)$. We also show a lower bound of $Ω(t\log n)$ for both quantities in the special cases where $k=3,4$. The implications of those results in the average-case analysis of two computational geometry algorithms are then discussed.
