最小圆覆盖

最小圆覆盖是数学中的一个算法问题，研究如何寻找能够覆盖平面上一群点的最小圆。这个问题在一般的n维空间中的推广是最小包围球的问题，即寻找能覆盖n维空间中某个点集的最小球。最小圆覆盖问题最早由十九世纪的英国数学家詹姆斯·约瑟夫·西尔维斯特在1857年提出。

最小圆覆盖也是运筹学中设施选址问题的一种。广义的设施选址问题研究的是当已知一些目标点（仓库、销售终端、供应商等等）的位置时，求满足与这些目标点的距离相关的点的某些极值。最小圆覆盖可以看作是研究“到一些点的距离之最大值最小的点”的问题。现有的算法可以在线性时间内计算最小圆覆盖或最小包围球的问题。

问题刻画

寻找最小覆盖圆的大部分几何方法都是寻找给定点集中经过最小覆盖圆的那些点。这是基于以下两个事实：

1. 最小覆盖圆是唯一存在的。
2. 给定的点集中，最多有三个点在最小覆盖圆上。如果有三个点在最小覆盖圆上，那么最小覆盖圆就是这三点的外接圆；如果只有两个点在最小覆盖圆上，那么最小覆盖圆就是以这两点之间的直线段为直径的圆。