最小包围圆 | Codeboy's Blog

形式陈述

从覆盖到最优证书

把一批站点放在平面上，要选一个中心，使最远站点到它的距离尽量小。输入有限点列 $P=(p_0,\ldots,p_{n-1})$ ，采用 Euclidean 内积及其平方距离，求

\min_{c\in\mathbb R^2}\max_{p\in P}\|p-c\|^2.

输出是包含全部点的闭圆盘；中文“包围圆”在此同时指它的边界与内部。非空输入返回圆心 $c$ 、平方半径 $\rho$ ，不用先开平方。空输入返回专门的空圆标记；它与以原点为心、半径零的圆不同。坐标为有理数时，平面最小圆的 $c,\rho$ 都可用有理数精确表示。

一个可独立核验的最优证书是至多三个输入点及非负系数 $\lambda_i$ ，满足

\sum_i\lambda_i=1,\qquad c=\sum_i\lambda_i p_i,\qquad \|p_i-c\|^2=\rho.

还须检查所有输入点都在圆内。对任意另一个中心 $z$ ，平方展开给出

\sum_i\lambda_i\|p_i-z\|^2=\rho+\|c-z\|^2.

因此任何覆盖这些证书点的圆，其平方半径至少为右端，尤其不小于 $\rho$ 。覆盖检查给上界，凸组合等式给下界；两个检查合在一起才证明最优。

为什么总有三个点以内的证书

非空有限点集的目标连续，并在 $\|c\|\to\infty$ 时趋于无穷，所以最优中心存在。它也唯一：若不同中心 $c_1,c_2$ 都用平方半径 $\rho$ 覆盖全部点，中点满足

\left\|p-\frac{c_1+c_2}{2}\right\|^2 =\frac{\|p-c_1\|^2+\|p-c_2\|^2}{2} -\frac{\|c_1-c_2\|^2}{4}<\rho,

会得到更小圆，矛盾。

最优中心必须在圆上输入点的凸包内。否则取该凸包中距中心最近的点，沿中心指向它的方向移动一小步，会严格缩短到每个边界点的距离；有限个内部点有正的剩余余量，足够小的移动仍使它们在圆内，于是可以缩小半径。这与最优性矛盾。再用 Carathéodory 定理，平面凸包中的中心只需至多三个边界点表示。这些点不一定唯一，圆心却唯一。

递归中的点为什么必须留在边界

定义 $D(P,R)$ 为覆盖 $P$ 、并让 $R$ 的每个点都在圆上的最小圆。它不是 $P\cup R$ 的普通最小圆。顶层要求 $D(P,\varnothing)$ ；递归把暂时无法覆盖的新点加入 $R$ 。

随机选 $p\in P$ ，先求 $D_0=D(P\setminus\{p\},R)$ 。若 $p\in D_0$ ，直接返回。否则求

D(P\setminus\{p\},R\cup\{p\}).

其正确性依靠：在新的最优圆中，违反旧圆的 $p$ 必须成为边界点。固定非空 $R$ 并取 $r_0\in R$ ，圆心的条件可改写为

2(r-r_0)\cdot c=\|r\|^2-\|r_0\|^2\quad(r\in R),

以及

2(q-r_0)\cdot c\ge\|q\|^2-\|r_0\|^2\quad(q\in P).

在这个凸可行集上最小化 $\|c-r_0\|^2$ ，就是原来的强制边界问题。若新点约束在新最优中心处仍严格松弛，就可沿新中心朝旧中心移动少量：其他约束保持可行，目标严格下降，产生矛盾。 $R=\varnothing$ 时，对两圆的标准圆方程作凸组合也得到同样结论。[1, §2, Lemma 1]

直觉

违反一次，少一个自由方向

普通圆可以移动圆心并改变半径。指定一个边界点后，半径由圆心到它的距离决定；指定两个不同边界点后，圆心只能在垂直平分线上移动；指定三个不共线点后，圆已唯一确定。递归不是每次重新盲猜三个点，而是把已经证明必须贴住的点保留下来。

三点最小圆的边界证书，以及一个钝角三角形的外接圆和真正最小圆 — 覆盖检查与凸组合下界

可以停止的两个基例

$P$ 为空时，直接构造经过 $R$ 的最小圆：零点为空圆，一点为零半径圆，两点取直径圆，三个不共线点取外接圆。三点共线且互异时不存在经过它们的有限圆，不能随意返回最远点对的直径圆，因为它没有让中间点留在边界。

合法顶层调用生成的子问题总可行，且 $R$ 内不会新增重复位置。因而当 $|R|=3$ 时，可以直接返回三点外接圆，不再扫描剩余 $P$ ：它们已由这个可达子问题的不变量保证被覆盖。若把子程序当成可接受任意 $(P,R)$ 的公共接口，这个快捷出口就不再安全，必须另外检查可行性。[1, pp.4–5]

实现不复制整个前缀

附件用一个点 ID 数组保存当前 $P$ ，每个递归帧记录有效前缀长度、至多三个边界 ID 和返回阶段。每次从有效前缀均匀抽一个位置，与末项交换；先算不含末项的子问题，必要时再把末项加入边界。两个分支结束后恢复交换，所以调用者仍看到同一份点集。

递归由显式栈模拟，不受 Python 递归深度限制。新随机选择在每个节点重新取得；没有在每层复制长度为 $|P|$ 的列表。若照着递归公式不断写 P[:-1]，光复制成本就可能破坏线性期望界。

例子与边界

三个真正参与最优性的点

取 $A=(0,0),B=(4,0),C=(1,3)$ ，另加内部点 $(1,1)$ 、边内点 $(2,0)$ 和一个重复的 $B$ 。仅看 $A,B$ 时，直径圆的中心为 $(2,0)$ 、平方半径为 $4$ ； $C$ 到该中心的平方距离为 $10$ ，确实违反。

三点等距方程给出圆心 $(2,1)$ 、平方半径 $5$ 。证书系数为

\frac14A+\frac5{12}B+\frac13C=(2,1).

三项系数非负、和为一；全部六个输入位置都通过覆盖检查。所以最小平方半径恰为 $5$ ，而不是仅凭图形猜到的数值。内部点和重复点不改变最优圆，但重复 ID 仍是输入记录，不能在程序里不说明就改变它们的身份。

三点外接圆不总是三点最小圆

改成 $A=(0,0),B=(4,0),C=(1,1)$ 。三点外接圆为中心 $(2,-1)$ 、平方半径 $5$ ；真正最小圆却是 $AB$ 的直径圆，中心 $(2,0)$ 、平方半径 $4$ ，且 $C$ 严格在内部。这解释了为什么“任意取三个点求外接圆”不能替代最小圆算法，也解释了强制边界子问题和普通子问题的差别。

全部点共线时，最小圆以两个极端位置为直径；全部位置重合时，半径为零。四点共圆时可能有多个支撑集，不能把每个圆上点都计成“删除它会改变最优值”的关键点。算法只在严格在外时重建，圆上相等不触发违反。

从最终圆线性提取证书

最终递归留下的三个边界记录未必就是最方便展示的最小证书。附件再扫描真正圆上的输入点。以一个非零半径方向 $a=p-c$ 为参照：遇到反向共线向量，直接得到一对直径端点；否则在叉积为正、为负的两侧，分别保留与 $a$ 内积最小的边界方向。因为所有这些向量等长，这恰是两侧最远离 $a$ 的角方向。

中心属于边界凸包，故选出的三个方向不能全落在同一开半平面；解二维重心坐标得到非负系数。零系数删掉即可。这个扫描只用 $O(n)$ 次精确运算，没有为提取证书再枚举全部三元组。圆内检查和证书验证也各为线性。

推论与应用

期望线性到底怎样得到

强制边界集合大小为 $r$ 时，只需至多 $3-r$ 个额外点决定其最优圆。 $r=0$ 已由三点证书证明； $r=1$ 时，前述圆心问题是在平面半空间交中找距 $r_0$ 最近的点，最优点在内部、边的投影或两条有效边界的交点，至多需两条约束； $r=2$ 时只剩直线上一个区间，最近点由至多一个端点约束决定； $r=3$ 时无需额外点。

不要求决定点唯一。固定当前集合后，任何删除会改变答案的点都必须属于每一份决定集，所以这样的点至多 $j=3-r$ 个。均匀抽最后处理点，触发第二次递归的概率至多 $j/n$ 。令 $t_j(n)$ 为期望圆内测试数，得到

t_0(n)=0,\qquad t_j(n)\le t_j(n-1)+1+\frac jn t_{j-1}(n-1).

逐层代入可取 $t_1(n)\le n,t_2(n)\le3n,t_3(n)\le10n$ 。常数工作与测试数同阶，加上输入、输出证书扫描，总期望算术操作数为 $O(n+1)$ ，辅助空间为 $O(n+1)$ 。这是对每个固定输入、内部独立随机选择取期望的 Las Vegas 保证，并非所有随机轨迹都线性。固定种子仅用于复算，不能把一次测试的速度当成概率证明。

算术与推广的边界

圆心、平方半径和内外分支采用精确几何计算，避免用固定 epsilon 把边界点移到错误一侧。若输入分子分母至多 $L$ 位，本页固定维数公式只含常数个输入数，约分后的中间几何数位长为 $O(L)$ ；设这种位长下含约分的有理运算成本为 $A(L)$ ，几何部分期望为 $O((n+1)A(L))$ 。均匀抽取位置另需随机整数生成成本，理想拒绝抽样平均用 $O(\log(n+1))$ 位随机数一次。

在 $d$ 维，最小球有至多 $d+1$ 个支撑点，但基例求球和随机递归常数都依赖 $d$ 。不能把平面中的常数 $10$ 或“固定维数线性”改写成同时对 $d,n$ 的统一线性界。LP-type 模型整理小基与违反集合的关系；它还需要局部性，不能仅凭“存在短证书”就调用所有抽样结论。

终结任务要求交付圆、证书、三点外接圆反例和精确复算记录。完整执行器中的审计模式会扫描各递归前缀，它用于核验，不计入以上关闭审计时的核心界。

参考资料

Emo Welzl，“Smallest enclosing disks (balls and ellipsoids)” 原稿，1991，§2，PDF pp.2–5，Lemma 1、递归与 Theorem 2；§3 讨论扩展。原稿页码与出版页码359–370不同。
Bernd Gärtner、Emo Welzl，“A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization”，2001，§2 “Smallest enclosing ball”、§3 Fact 3.3：删除关键点、抽样和非唯一基。

形式陈述 ​

从覆盖到最优证书 ​

为什么总有三个点以内的证书 ​

递归中的点为什么必须留在边界 ​

违反一次，少一个自由方向 ​

可以停止的两个基例 ​

实现不复制整个前缀 ​

三个真正参与最优性的点 ​

三点外接圆不总是三点最小圆 ​

从最终圆线性提取证书 ​

期望线性到底怎样得到 ​

算术与推广的边界 ​

反向链接