跟踪一组点的最大距离的最好方法

理论上，您可以通过存储所拥有的点的凸包来有效地做到这一点。

每当你添加一个新的点，测试看看它是否在多面体的内部。如果是，则保留最大距离。如果没有，那么它可能已经改变了。

同样，如果你从内部删除一个点，最大距离(直径)被保留，所以什么也不改变。但是，如果删除边界点，则必须重新计算凸包。

如果你是在二维空间中，那么当你在边界上添加或删除时，最多只能影响多边形的两条边。这些应该很容易计算，这取决于您如何存储信息(例如，一个线段序列)。

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

与其使用凸包(如另一个答案所建议的)，你可以使用Delaunay三角剖分法吗?

最小距离:

要计算从一个节点到集合中任何其他节点的最小距离，你只需要检查节点的近邻，即在三角剖分中通过一条边连接到它的节点。

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

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

最大距离:

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

我不确定这是最好的，但这是我目前能想到的最好的。

将最大值与该距离上的一组点对一起保存。(最大值不一定唯一)

最小值也一样。

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

• 当您删除一个点时，检查是否清除了整个记住的最小或最大端点集。如果不是，你什么都不需要做。但如果是的话，我想你需要重新计算所有的东西。

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