最大封闭盘
Maximum enclosing disk
设A和B为两组点，每组由n个点组成，都位于单位正方形S内。
我正在尝试找到一种有效的算法来找到最大的磁盘 D，这样：
(i) D的中心在S.
(ii) D 内部为空
(iii) D 的边界至少与 A 的一点和 B 的一点接触。
我对这个问题有一个真正的问题。任何提示都会有用。
要完成 Yves Daoust 的部分解，请计算以 S 为界的 Voronoi 图（与 Delaunay 三角剖分对偶）。我们可以在某个 Voronoi 顶点（即 S 内部的一个点）找到最佳圆心其中 A ∪ B 中最近的三个点等距，或 S 边界上的一个点，其中 A ∪ B 中最近的两个点等距）其中最近的一个点在 A 中，另一个在 B 中。
这样的顶点作为中心显然是可行的。如果我们尝试采用任何其他中心，那么我们可以应用斯塔克的观察。这个中心必须与 A 中的一个点和 B 中的一个点等距，所以假设 A ∩ B 是空的（我真的不想考虑退化的情况；我们总是可以扰乱出路），我们可以滑动沿着 AB 的垂直平分线的中心，直到我们到达第三个点或边界。
设A和B为两组点，每组由n个点组成，都位于单位正方形S内。 我正在尝试找到一种有效的算法来找到最大的磁盘 D，这样：
(i) D的中心在S.
(ii) D 内部为空
(iii) D 的边界至少与 A 的一点和 B 的一点接触。
我对这个问题有一个真正的问题。任何提示都会有用。
要完成 Yves Daoust 的部分解，请计算以 S 为界的 Voronoi 图（与 Delaunay 三角剖分对偶）。我们可以在某个 Voronoi 顶点（即 S 内部的一个点）找到最佳圆心其中 A ∪ B 中最近的三个点等距，或 S 边界上的一个点，其中 A ∪ B 中最近的两个点等距）其中最近的一个点在 A 中，另一个在 B 中。
这样的顶点作为中心显然是可行的。如果我们尝试采用任何其他中心，那么我们可以应用斯塔克的观察。这个中心必须与 A 中的一个点和 B 中的一个点等距，所以假设 A ∩ B 是空的（我真的不想考虑退化的情况；我们总是可以扰乱出路），我们可以滑动沿着 AB 的垂直平分线的中心，直到我们到达第三个点或边界。