追踪一组点中最大距离的最佳方法？

Question

假设我有一个2维点的集合，以及一种确定它们之间距离的方法。这个集合经常被修改，添加了额外的点并删除了现有的点。在任何时候，我都需要知道点之间的最大和最小距离，即最远的两点之间的距离以及两点之间最近的距离。有没有一种数据结构或算法可以很好地完成这项任务？每次点改变时，我宁愿不必重新计算整个距离。

Answer 1

从理论上讲，您可以通过存储您所拥有的点的convex hull高效地完成此操作。

每当您添加一个新点时，请测试以确定它是否位于此polytope的内部。如果是这样，则保留最大距离。如果不是，那么它可能已经改变。

同样，如果您从内部删除一个点，最大距离（直径）被保留，所以不做任何改变。但是，如果删除边界点，则必须重新计算凸包。

如果您在2维中，那么当您添加或从边界移除时，多边形的至多两侧都会受到影响。这些应该很容易计算，具体取决于你如何存储信息（例如一系列线段）。

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

Answer 2

我一点也不确定这是最好的，但这是我现在能想到的最好的。

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

同样当然最小。

• 当您添加一个点，计算所有其他点新点的距离，而其对应的一组端点对替换您保存的最大值和最小值在一起，如果新的点在一个更好的最大或最小参与，或者如果它匹配当前最好的，则更新该组端点。

• 删除点时，检查是否清除整个记住的最小或最大点集。如果没有，你不需要做任何事情。但如果是这样，我认为你需要重新计算一切。

为了最大化计算，我相信PengOne的建议可以告诉你，如果你可以完全跳过计算。

Answer 3

而不是使用凸包（如在另一个答案中建议），你可以使用Delaunay三角？

最小投影距离：

要计算从节点的最短距离的任何其他集合中，你应该只需要检查节点的近邻，即那些通过在边缘连接到它三角测量。

因此，如果插入新节点，更新三角测量，找到新节点的邻居以及更新中“涉及”的任何其他节点，计算此本地“更新”集中所有节点的距离，并且检查是否找到新的最小值。类似地，如果现有节点被删除，则再次更新三角测量并重新计算“涉及”的所有节点的距离。

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

最大距离：

如凸包风格回答表明，你只需要重新计算边界节点之间的距离，如果一个新的节点是在现有的三角测量之外，或如果现有的边界节点加入已被删除。

希望这会有所帮助。 “