假设我有一个二维点的集合,并且有一种方法来确定它们之间的距离。这个集合经常被修改,添加新点和删除现有点。在任何给定时间,我需要知道点之间的最大和最小距离,也就是两个最远的点之间的距离和两个最近的点之间的距离。有没有一种数据结构或算法特别适合这个任务?我希望不必每次更改点时都重新计算整组距离。
我并不确定这是最好的方法,但这是我现在能想到的最好的方法。
将最大值与该距离下的一组点对保存在一起。(最大值不一定唯一。)
当然,最小值也是如此。
添加一个点时,计算新点到所有其他点的距离,并替换已保存的最大值和最小值以及其相应的端点对集合,如果新点参与更好的最大值或最小值,或者如果它匹配当前最佳值,则更新端点集合。
删除一个点时,请检查是否清除了整个记忆中的最小或最大端点集。如果没有,您无需执行任何操作。但如果是,我认为您需要重新计算所有内容。
对于最大值的计算,我相信PengOne的建议可以告诉您是否可以完全跳过计算。