最小包围球科技 最后更新于 2025-05-01 17:03:31

### Welzl's Algorithm 一个集合的最小包围球肯定是唯一的。否则假如有两个同样大小但不同位置的 $D_1, D_2$，那么 $D_1 \cap D_2$ 也可以包围但比 $D_1, D_2$ 拥有更短的“直径”，矛盾。 #### 算法流程 维护集合 $P, R$，函数 $work(P, R):$ 包含所有$P$，$R$ 中的点全部在边界上的最小包围球。根据事实，$|R| \leq 3$。 从 $P$ 中随机选取一个点 $p$，考察 $P$ 去掉 $p$ 之后的集合 $P'$，若 $work(P', R)$ 返回的包围球包含 $p$ 则直接返回这个球。 否则返回 $work(P', R \cup \{p\})$，边界是 $|R| \leq 3$ 或者$P'$ 为空。 #### 复杂度分析 不会，Welzl 先生的 paper 表示期望是 $O(qq!n)$，其中 $q=\frac{d(d+3)}{2}$.