Answer

问题及解答

球覆盖问题

Posted by haifeng on 2011-08-26 10:24:26 last update 2011-08-26 10:57:14 | Edit | Answers (1)

  • 欧氏空间 $\mathbb{E}^{n}$ 中考虑单位球 $B(0,1)$, 现在要用半径为 $\varepsilon$ 的球覆盖 $B(0,1)$, 请问至少需要多少个这样的球?
  • 考虑单位球面 $S^n(1)$, 现试用该球面上半径为 $\epsilon$ 的球 $B_\epsilon$ 覆盖此球面, 问至少需要多少个这样的小球?

注意到欧氏空间 $\mathbb{E}^{n+1}$ 中单位球面 $S^n$ 的面积为 \[\text{area}(S^n)=\frac{2\pi^{\frac{n+1}{2}}}{\Gamma(\frac{n+1}{2})}.\]

1

Posted by haifeng on 2011-08-26 14:27:39

先对于简单的情况加以分析. 比如我们考虑欧氏平面中的一个正方形区域 $[0,1]^2$, 且 $\varepsilon$ 足够小. 则我们可以这样来做实验, 取很多小的一角硬币, 让它们紧凑地排列在桌面上, 则无论怎样, 由周边四个小硬币所围出来的空隙区域总可以用另一个硬币可以完全覆盖住. 类似的可以拿很多小弹珠做三维欧氏空间的实验, 这时让这些小弹珠紧凑地堆在一起, 每紧邻的四个小弹珠的球心形成一个正四面体, 很容易计算得到这个正四面体的外接球半径为 $\frac{\sqrt{3}}{\sqrt{2}}\varepsilon$, 再取一个这样的小弹珠位于此正四面体中心, 则完全可以覆盖住空隙区域. 由此可以看到对于 2 维或 3 维情形, 如果要覆盖住边长为 $\ell$ 的方形区域, 大概需要

\[2\cdot(\frac{\ell}{2\varepsilon})^2\]

个小球.