随机 3D Convex Layer 的期望复杂度分析

· · 算法·理论

GPT 教我的，我把它整理成人话。

前情提要

本题的做法是：不断求出最外层凸包并删去。使用卷包裹法，单次时间复杂度为 \mathcal{O}(nd)，总时间复杂度为 \mathcal{O}(n^2)。

还有一种能过的写法是，将点集随机打乱，然后每次跑朴素的增量法。出题人说尝试过卡掉它或者证明它，都没成功，怀疑有些深刻的道理说明是对的，但应该不简单。

结论是只要点集 S 满足任意四点不共面，上面算法的时间复杂度就是 \mathbb{E}[T(S)]=\mathcal{O}(n^2)。

记号和约定

记原点集的所有凸包层为 L_1,L_2,\dots,L_{\ell}，其中 L_1 为最外层凸包 L_{\ell} 为最内层；迭代到第 k 轮时，剩余的点集为 S_k:=\bigcup_{j=k}^{\ell} L_j,\ m_k=|S_k|,\ h_k= |L_k|。

记当前剩余点的随机排列为 p_1,p_2,\dots,p_{m_k}，P_j:=\{p_1,\dots,p_j\}，表示一个前缀点集；V(S) 表示 \textsf{conv}(S) 的顶点集合，每一轮迭代的时间复杂度为：

\mathbb{E}[T_k] = \mathcal{O}\!\left(m+\sum_{j=1}^{m_k}|V(P_j)|\right)

问题变成了估计一个随机排列所有前缀凸包顶点数之和。

定义 1. 点 x 在集合 S 中的半空间深度 D_S(x) 为所有包含 x 的闭半空间 H 中，包含 S 中的点数的最小值。形式化地说 D_{S}(x)=\min_{H \ni x}|S\cap H| 点 x 的归一化半空间深度为 \alpha_{S}(x):=D_{S}(x)/|S|。

根据半空间深度的定义我们可以得到如下推论：

推论 2. 若 x\in L_{r},\ (k\leq r\leq \ell)，则它在 S_k\setminus \{x\} 中的半空间深度至少为 r-k，即 D_{S_k\setminus \{x\}}(x)\geq r-k

复杂度分析

我们需要分析前缀的凸包的顶点数，Hayakawa、Lyons 和 Oberhauser 在 21 年的一篇论文中给出了很强的结论：若一个点相对于分布的归一化半空间深度为 \alpha，那么在 \mathbb R^{d} 中，只需至多 \left\lceil 3d/\alpha \right\rceil 个独立样本，其凸包包含该点的概率就至少为 1/2。

定理 3. [Theorem 16 of HLO21] 令 X 为任意 d 维向量集，N_X := \inf\{n\mid \Pr(x\in \textsf{conv}\{X_1,X_2,\dots,X_n\})\geq 1/2\}，有 \dfrac{1}{2\alpha_X(x)} \leq N_X \leq \left\lceil \dfrac{3d}{\alpha_X(x)} \right\rceil

有了这个定理我们就能求出一个点在出现在一段随机抽取的点集凸包中概率的上界。

推论 4. 当前迭代为第 k 轮，固定点 x\in L_r, k\leq r\leq \ell，随机从 S_k 中不放回地抽取 s 个点 X_1,X_2,\dots, X_s，有

\Pr(x\notin \textsf{conv}\{X_1,X_2,\dots, X_s\}) \leq 2^{-\left\lfloor \frac{s(r-k)}{10|S|}\right\rfloor}

证明. 当前实例中空间维度为 3，因此根据定理 3 至多取 B:=\left\lceil 9|S|/(r-k)\right\rceil\leq 10|S|/(r-k) 个点就可以使得凸包至少以 1/2 的概率包含 x。因此把 s 个点分为不交的 \left\lfloor s/B\right\rfloor 个块，如果 \{X_1,X_2,\dots X_s\} 不包含 x 那么所有块也一定不包含 x，各块独立。

因此概率小于每个块的凸包不含 x 的概率（至多 1/2）的乘积。\Box

现在我们考虑点 x\in L_r 对复杂度的贡献，进行分类讨论：

Case 1. r=k

此时 x 是 \textsf{conv}(S_k) 的顶点，因此只要任意一个前缀包含 x 那么它就会对 \mathbb{E} [|V(P_j)|] 贡献 1，即 \Pr(x\in V(P_j)) = \frac{j}{m_k}。所以 x 在所有前缀中的期望贡献为

\sum_{j=1}^{m_k} \dfrac{j}{m_k} = \dfrac{m_k+1}{2}

Case 2. r>k

考虑随机前缀 P_j，此时剩余的点是从 S_k\setminus \{x\} 中均匀无放回抽出的，由推论 4

\Pr(x\in V(P_j))=\Pr(x\notin \textsf{conv}(P_j\setminus \{x\})) \leq \dfrac{j}{m_k}\cdot 2^{-\left\lfloor \frac{(j-1)(r-k)}{10(m_k-1)}\right\rfloor}

其中 j/m_k 这一项是加上 x\in P_j 的条件。把所有前缀的贡献求和

\begin{aligned} \sum_{j=1}^{m_k}\Pr(x\in V(P_j))&\leq \dfrac{1}{m}\sum_{j=0}^{m_k-1}(j+1)2^{-j\cdot \Omega\left(\frac{r-k}{m_k-1}\right)}\\ &\leq \dfrac{1}{m}\sum_{j=0}^{\infty}(j+1)2^{-j\cdot \Omega\left(\frac{r-k}{m_k-1}\right)}\\ &=\dfrac{1}{m_k}\cdot \left(1-2^{-\Omega\left(\frac{r-k}{m_k-1}\right)}\right)^{-2}\\ &=\mathcal{O}\!\left(\dfrac{m_k}{(r-k)^2}\right) \end{aligned}

最后一步是因为 1\leq r-k \leq m_k-1 \Leftrightarrow 0<\frac{r-k}{m_k-1}\leq 1 因此有 1-2^{-x}=\Omega(x)。

第 k 轮中，L_k 中的每个点贡献 O(m_k)；L_r 中的每个点，其中 r>k，贡献 \mathcal{O}\left(\frac{m_k}{(r-k)^2}\right)，因此

\mathbb E\left[ \sum_{j=1}^{m_k}|V(P_{j})| \right] = \mathcal{O}\!\left( m_kh_k + m_k\sum_{r=k+1}^{\ell} \frac{h_r}{(r-k)^2} \right).

于是第 k 轮随机增量凸包的期望时间为

\mathbb E[T_k] = \mathcal{O}\!\left( m_k+ m_kh_k+ m_k\sum_{r=k+1}^{\ell} \frac{h_r}{(r-k)^2} \right).

对 \ell 层凸包求和：

\begin{aligned} \mathbb{E}[T(S)]&=\sum_{k=1}^{\ell} \mathbb{E}[T_k]=\mathcal{O}\!\left(\sum_{k=1}^{\ell}m_k + \sum_{k=1}^{\ell}m_kh_k + \sum_{k=1}^{\ell}\sum_{r=k+1}^{\ell} \frac{ m_kh_r}{(r-k)^2}\right)\\ &\leq \mathcal{O}\!\left(n + n\sum_{k=1}^{\ell}h_k + \sum_{k=1}^{\ell}m_k\sum_{r=k+1}^{\ell} \frac{n}{(r-k)^2}\right)\\ &\leq \mathcal{O}\!\left(n^2 + n\sum_{k=1}^{\ell}m_k\sum_{r=1}^{\infty} \frac{1}{r^2}\right)\\ &\leq \mathcal{O}\!\left(n^2 + \dfrac{\pi^2}{6}n\sum_{k=1}^{\ell}m_k\right)\\ &= \mathcal{O}\!\left(n^2\right). \end{aligned}

这就是我们要证的结论。