|
|
本帖最后由 hbghlyj 于 2023-6-17 09:34 编辑 凸包上点个数期望
Hong 编辑于 2019-06-01 01:24
前几天在1e4U裙看到了一个有意思的结论：平面上随机 $N$ 个点，这 $N$ 个点的凸包上的点的个数的期望为 $O(\log N)$ 。随便搜了搜没有搜到证明，就尝试证明了一下。
考虑使用Andrew算法求凸包的过程。首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是“左拐”的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。
考虑使用单调栈求凸包的过程，问题等价于：随机 $N$ 个数字，将这些数字依次加入单调栈，单调栈长度的期望为 $O(\log N)$ 。
设 $f(n)$ 为随机加入 $N$ 个数字的单调栈的期望长度。随机 $N$ 个数字等价于随机 $1,2,..,N$ 的一个排列。考虑将数字 $N$ 插入前 $N-1$ 个数字的排列。对于 $1..N-1$ 的排列，共有 $N$ 个位置可以插入数字 $N$ （等概率）。设这 $N$ 个位置自右向左依次编号为 $1,2,...,N$ 。当 $N$ 被插入到第 $i$ 个位置时，那之后的 $i-1$ 个数字一定不会被加入单调栈中，单调栈长度=（加入前 $N-i$ 个数字的单调栈的长度+加入 $N$ 之后的单调栈长度）。前 $N-i$ 个数字均 $\leq N-1$ ，所以 $N$ 一定会被加入单调栈使其长度加一。因此插入第 $i$ 个位置的单调栈长度期望为 $f(n-i)+1$ 。由此可得：
$$f(n)=\sum_{i=1}^n \frac{f(n - i) + 1}{n} $$
可以得到递推式：
$$nf(n)-(n-1)f(n-1)=f(n-1)+1 $$
化简得：
$$f(n)-f(n-1)=\frac{1}{n} $$
$$f(n)=\sum_{i=1}^{n} \frac{1}{n}=O(log n)$$
证毕。
（一开始用数学归纳法证，发现没有头，GG
（果然证复杂度不能用归纳法
（感觉结论有点精彩
On the Expected Complexity of Random Convex Hulls
Lemma 2.4 The expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from the unit square, is $O(\log n)$. |
|
