论文标题
随机点的孔和岛屿
Holes and islands in random point sets
论文作者
论文摘要
对于$ d \ in \ mathbb {n} $，让$ s $是$ \ m athbb {r}^d $的一组点。 $ s $的$ i $ $ k $点是$ s $ s $的$ k $ island，如果凸赫尔$ \ mathrm {cons}（cons}}（i）$ o $ i $ of $ i $满足$ \ mathrm {cons}（cons}（i）\ cap s = i $。 $ s $ s $ invex位置的$ k $ island是$ s $的$ k $洞。 对于$ d，k \ in \ mathbb {n} $和一个凸件$ k \ subseteq \ subseteq \ mathbb {r}^d $ of Volume $ 1 $，让$ s $是一组$ n $点，以$ k $从$ k $中随机选择均匀地选择。我们表明，$ s $中的$ k $孔的预期数为$ O（n^d）$。我们的估计改进并概括了所有以前的范围。特别是，我们估计$ s $中的预期空简短数量为$ 2^{d-1} \ cdot d！\ cdot \ binom {n} {d} $。直到较低的术语，这在平面上很紧。 我们的方法即使在更一般的环境中，我们的方法也给出了渐近的上限$ O（n^d）$，我们估计预期的$ k $ islands数量为$ s $。
For $d\in\mathbb{N}$, let $S$ be a set of points in $\mathbb{R}^d$ in general position. A set $I$ of $k$ points from $S$ is a $k$-island in $S$ if the convex hull $\mathrm{conv}(I)$ of $I$ satisfies $\mathrm{conv}(I) \cap S = I$. A $k$-island in $S$ in convex position is a $k$-hole in $S$. For $d,k\in\mathbb{N}$ and a convex body $K\subseteq\mathbb{R}^d$ of volume $1$, let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$. We show that the expected number of $k$-holes in $S$ is in $O(n^d)$. Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in $S$ by $2^{d-1}\cdot d!\cdot\binom{n}{d}$. This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound $O(n^d)$ even in the much more general setting, where we estimate the expected number of $k$-islands in $S$.
