在一组点中跟踪最大距离的最佳方法是什么？

Question

假设我有一个二维点的集合，并且有一种方法来确定它们之间的距离。这个集合经常被修改，添加新点和删除现有点。在任何给定时间，我需要知道点之间的最大和最小距离，也就是两个最远的点之间的距离和两个最近的点之间的距离。有没有一种数据结构或算法特别适合这个任务？我希望不必每次更改点时都重新计算整组距离。

- GWLlosa

Answer 1

理论上，您可以通过存储已有点的凸包来高效完成此操作。

每当添加新点时，请测试其是否位于此多面体的内部。如果是，则最大距离得以保留。如果不是，则可能已更改。

同样地，如果您从内部删除一个点，则最大距离（直径）得以保留，因此不需要更改任何内容。但是，如果您删除了一个边界点，则必须重新计算凸包。

如果您处于二维空间中，则在添加或删除边界时，最多会影响到多边形的两个侧面。这些应该很容易计算，具体取决于您如何存储信息（例如，一系列线段）。

编码可能有点麻烦，但最简单的方法是标记边界上的点，然后拥有一个函数来测试一个点是否位于标记点的凸包内。

- PengOne

---

@Kevin：给定一组点，任意两个点之间的最大距离是这些点构成的凸包的直径。我的断言源自这个事实。 - PengOne

你说得对，我的简单示例确实说明了这一点。哎呀，谢谢。 - Kevin D.

+1：虽然我不认为这对于最小距离有帮助。 - Don Roby

@Don：在这一点上非常正确。然而，如果你想要最小距离，你实际上可以计算对偶，但这可能会涉及到过于复杂的数学和计算密集型的操作。 - PengOne

@GWLlosa：实际上，在二维情况下，你不需要遍历凸包中的每一对点。可以使用旋转卡尺算法将复杂度降低到与点数成线性关系的函数。详见旋转卡尺算法。 - abeln

Answer 2

与其使用凸包（如另一个答案所建议的），你能否使用Delaunay三角剖分？

最小距离：

要计算节点到集合中任何其他节点的最小距离，您只需要检查节点的直接邻居，即与它通过三角剖分中的边相连的那些节点。因此，如果插入新节点，请更新三角剖分，找到新节点和任何其他“涉及”更新的节点的邻居，计算此本地“已更新”集合中所有节点的距离，并检查是否发现新的最小值。同样，如果删除现有节点，则再次更新三角剖分并重新计算所有“涉及”的节点的距离。

有一类所谓的“增量”算法可用于构建仅在插入/删除新节点时需要对整个三角剖分进行局部修改的Delaunay三角剖分，因此这是我建议频繁插入/删除的方法。

最大距离：

如凸包样式答案所建议的，如果在现有三角剖分之外添加了新节点或删除了现有边界节点，则只需重新计算边界节点之间的距离。

希望这可以帮助您。

- Darren Engwirda

Answer 3

我并不确定这是最好的方法，但这是我现在能想到的最好的方法。

将最大值与该距离下的一组点对保存在一起。（最大值不一定唯一。）

当然，最小值也是如此。

• 添加一个点时，计算新点到所有其他点的距离，并替换已保存的最大值和最小值以及其相应的端点对集合，如果新点参与更好的最大值或最小值，或者如果它匹配当前最佳值，则更新端点集合。

• 删除一个点时，请检查是否清除了整个记忆中的最小或最大端点集。如果没有，您无需执行任何操作。但如果是，我认为您需要重新计算所有内容。

对于最大值的计算，我相信PengOne的建议可以告诉您是否可以完全跳过计算。

- Don Roby