最小圆覆盖

最小圆问题（也称为最小覆盖圆问题、边界圆问题、最小边界圆问题、最小封闭圆问题）是计算包含欧几里得平面中所有给定点集的最小圆的数学问题 . n 维空间中的相应问题，即最小包围球问题，是计算包含所有给定点集的最小 n 球。 最小圆问题最初是由英国数学家詹姆斯·约瑟夫·西尔维斯特于 1857 年提出的。

平面中的最小圆问题是设施位置问题（1 中心问题）的一个示例，其中必须选择新设施的位置来为许多客户提供服务，从而xxx限度地减少任何客户的最远距离 必须旅行才能到达新设施。 平面中的最小圆问题和任何有界维的高维空间中的最小包围球问题都可以在最坏情况下的线性时间内解决。

该问题的大多数几何方法都是寻找位于最小圆边界上的点，并基于以下简单事实：

• 最小覆盖圆是xxx的。
• 集合S的最小覆盖圆最多可以由S中位于圆边界上的三个点确定。 如果仅由两点决定，则连接这两点的线段一定是最小圆的直径。 如果是由三个点决定的，那么这三个点组成的三角形就不是钝角。

正如 Nimrod Megiddo 所展示的，最小封闭圆可以在线性时间中找到，同样的线性时间界限也适用于任何常维欧几里德空间中的最小封闭球。 他的文章还简要概述了早期的 O ( n 3 ) {displaystyle O(n{3})} 和 O ( n log ⁡ n ) {displaystyle O(nlog n)} 算法； 通过这样做，Megiddo 证明了 Shamos 和 Hoey 的猜想——最小圆问题的解可以用 Ω ( n log ⁡ n ) {displaystyle Omega (nlog n)} 在 xxx – 是错误的。

Emo Welzl 基于 Raimund Seidel 的线性规划算法，提出了一种简单的随机算法，用于在预期时间 O ( n ) {displaystyle O(n)} 内运行的最小覆盖圆问题。

随后，最小圆问题被包含在一类一般的 LP 类型问题中，可以通过基于线性规划的 Welzl 等算法来解决。 作为此类成员的结果，表明 O ( n ) {displaystyle O(n)} 时间界限中常数因子的维度依赖性，这对于 Seidel 的方法是阶乘的， 可以减少到次指数。

Megiddo 的算法基于称为修剪和搜索的技术，通过删除 n 16 {textstyle {frac {n}{16}}} 不必要的点来减少问题的大小。这导致了递归 t ( n ) ≤ t ( 15 n 16 ) + c n {displaystyle t(n)leq tleft({frac {15n}{16}}right)+cn} 给出 t ( n ) = 16 c n {displaystyle t(n)=16cn} 。

该算法比较复杂，体现在其乘法常数大。 缩减需要解决类似问题的两倍，其中所寻求的外接圆的中心被限制在给定的直线上。子问题的解决方案要么是无约束问题的解决方案，要么用于确定半- 无约束解中心所在的平面。

找到要丢弃的 n 16 {textstyle {frac {n}{16}}} 点如下：点 Pi 成对排列，定义 n 2 {textstyle {frac {n} {2}}} 行 pj 作为它们的平分线。找到按方向排序的平分线的中值平均 pm（指向由平分线 p1 确定的相同半平面）并制作成对的平分线，使得在每一对中有一个 二等分线的方向至多为 pm，另一个至少为 pm（方向 p1 可根据需要视为 − ∞ {displaystyle infty } 或 + ∞ {displaystyle infty }。）设 Qk 为交点 第 k 对中的平分线。

p1 方向的线 q 被放置为通过交点 Qx，使得在该线定义的每个半平面中有 n 8 {textstyle {frac {n}{8}}} 个交点（中位 ). 封闭问题的约束版本在确定中心所在的半平面的直线 q’ 上运行。在 pm 方向上的直线 q’ 被放置通过交点 Qx’ 使得有 n 16 {textstyle {frac {n}{16}}} 在不包含解决方案的半平面的每一半中的交点。