algorithm - 放置一个点以最小化与最远点的距离

Question

我有个问题，

给定一组点，你如何放置一个点，约束条件是到最远点的距离尽可能小？

这是参考这个问题。我不知道该怎么做。有人指点吗？

谢谢

score 1 · Accepted Answer

您需要使用Voronoi图，可能是Farthest-Point Voronoi图，其中平面被划分为区域，同一区域中的点具有相同的最远点

更新

你需要先构建一个 Farthest-Point voronoi 图，时间为 O(nlogn)，然后找到所有顶点（如果圆由三个点定义）和所有边（如果圆由两点定义）。这种方法的总时间复杂度是O(nlogn)

我刚刚看到最小圆问题wiki 页面，似乎有一个O(n)时间算法。如果你关心速度，你可以检查一下，否则没关系。

score 1 · Accepted Answer

_{万一上面的链接死了，这里是描述最直接方法的相关部分：}

O(n2) 时间算法

在圆心 c 处画一个圆，使得给定集合的点位于圆内。显然，这个圆圈可以做得更小（或者我们有解决方案）。
找到离圆心最远的点A，使圆变小，并以相同的中心画一个新的圆，并通过点A。这两个步骤产生一个更小的封闭圆。新圆更小的原因是这个新圆仍然包含给定集合的所有点，除了现在它通过最远的点 x，而不是包围它。
如果圆通过 2 个或更多点，则继续执行步骤 4。否则，通过将中心移向 A 点来使圆变小，直到圆与集合中的另一个点 B 接触。
在这个阶段，我们是一个圆 C，它通过给定集合的两个或多个点。如果圆包含的弧的间隔（无点间隔）大于圆的周长的一半，并且没有点位于该圆弧上，则可以使圆更小。令 D 和 E 为该无点区间末端的点。在将 D 和 E 保持在圆的边界上的同时，减小圆的直径，直到出现情况 (a) 或情况 (b)。
- 情况 (a) 直径是距离 DE。
  - 我们完了！
- 情况 (b) 圆 C 接触集合中的另一个点 F。
  - 检查是否存在长度超过 C 圆周一半的无点圆弧区间。
  - 如果没有这样的无点弧间隔存在，那么我们就完成了！
- 别的
  - 转到第 4 步。
  - 在这种情况下，三个点必须位于长度小于圆周一半的弧上。我们在弧上三个点的外部两个重复步骤 4。

2 回答 2