|
|
设 $\sigma=\{x_0,\dots,x_k\}$ 为 $n$ 维欧几里得空间中的有限点集，且任两点之间的距离小于 $1$。那么这组点的最小包围球的半径是多少？
这等价于找到最小的 $\delta$ 使得 $\bigcap_{i=1}^k B(x_i,\delta) \neq \emptyset$。
Helly 定理
如果 $\mathbb{R}^d$ 中的有限个凸集的任意 $d+1$ 个都有非空交集，那么这些凸集的交集非空。
使用该定理可将问题简化为 $k\le n$ 的情况。
设 $z$ 为最小包围球的中心。下面证明它存在且唯一。
设 $f:\mathbb{R}^n\to\mathbb{R}$ 为一个函数，使得 $f(y)=\max_i\|y-x_i\|$。那么 $f$ 是连续的，并且当 $\|y\|\to\infty$ 时 $f(y)\to\infty$，所以它有一个全局最小值 $z$。假设存在 $z,z'$ 使得 $f(z)=f(z')$ 是最小值。那么以 $z$ 和 $z'$ 的中点为中心，半径为 $\sqrt{f(z)^2-\left\|z-z'\over2\right\|^2}$ 的球也包含所有点，由于 $f(z)$ 的最小性必须有 $\|z-z'\|=0$，所以最小值点 $z$ 是唯一的。
如果 $x_i$ 位于 $\partial B(z,f(z))$，则称 $x_i$ 为临界点。那么 $\|z-x_i\|=f(z)$。
如果只有一个临界点 $x_0$，那么我们可以沿着从 $z$ 到 $x_0$ 的直线将 $z$ 移近 $x_0$ 以减小 $f(z)$。所以必须至少有两个临界点。
$z$ 位于临界点的凸包内。如果 $z$ 不在临界点的凸包内，那么存在一个超平面将 $z$ 和凸包分开，设这个超平面的法向量为 $v$，$\|v\|=1$，则 $\langle v,x_i-z\rangle>0$ 对所有 $i=1,\dots,k$ 成立。对于小的正数 $\lambda$，$$\|x_i-(z+\lambda v)\|^2=\|x_i-z\|^2+\lambda^2-2\lambda\langle v,x_i-z\rangle<\|x_i-z\|^2$$所以 $f(z+\lambda v)<f(z)$，矛盾。
重新编号后，设临界点为 $\{x_0,\dots,x_{k'}\}\subseteq \sigma$，其中 $k'\le k$。
我们可以将 $z$ 写成临界点 $\{x_0,\dots,x_{k'}\}$ 的凸组合 $z=\sum_{i=0}^{k'}a_i x_i$ 其中 $\sum_{i=0}^{k'}a_i=1$ 且 $0<a_i<1$，并且 $a_0=\min_i a_i$。
设 $\hat{x_i}=x_i-z$ 那么 $\sum_{i=0}^{k'}a_i \hat{x_i}=0$ 因此 $\hat{x_0}=-\sum_{i=1}^{k'}\frac{a_i}{a_0} \hat{x_i}$。
现在$$-f(z)^2=-\|x_0-z\|^2=-\|\hat{x_0}\|^2=\sum_{i=1}^{k'}\frac{a_i}{a_0} \langle \hat{x_0},\hat{x_i}\rangle$$
至少有一项小于等于这$k'$项的平均值，设第$i$项是那一项，那么 $\langle \hat{x_0},\hat{x_i}\rangle\le\frac{a_i}{a_0}\langle \hat{x_0},\hat{x_i}\rangle\le-\frac{f(z)^2}{k'}\le-\frac{f(z)^2}{n}$。
即 $-\langle \hat{x_0},\hat{x_i}\rangle\ge\frac{f(z)^2}{n}$。
$$1^2\ge\|x_0-x_i\|^2=\|\hat{x_0}-\hat{x_i}\|^2=\|\hat{x_0}\|^2+\|\hat{x_i}\|^2-2\langle \hat{x_0},\hat{x_i}\rangle\ge f(z)^2(1+1+\frac2n)$$
所以$$\max_i\|x_i-z\|=f(z)\le\sqrt{n\over 2(n+1)}$$
当 $x_i$ 是边长为 $1$ 的正单形的顶点时达到等号。 |
|
