2D地图上最孤立的点 - 算法

Question

我有一组点，需要知道哪一个点与其他点的欧几里得距离最远。

为了找到这个点，我需要计算每个点与其他所有点之间的距离，并求平均值，然后选择平均值最大的点作为距离最远的点。

有没有更快的方法来找到这个点呢？

- Sgluive

---

你确定要使用“孤立”的这个定义，并且想要一个更快的算法吗？还是你在询问是否有一个更好/更快的“最孤立”的定义？ - RBarryYoung

为了提高性能，请确保仅计算两点间的距离一次，因为 dist(p1,p2) = dist(p2,p1)。 - jbontinck

请在问题中澄清这一点。听起来你想要平均到所有其他点的距离来衡量“孤立度”，这与“最远的最近邻居”不同。 - Geobits

也许可以建立一个 k-d 树来存储你的点。这样可以用它来找到每个点的最近邻居，并取其中最大的一个。这样做可以得到一个 O(log n) 的算法，而不是 O(n*n)。 - Vaughn Cato

哦，另外，如果你指的是欧几里得距离（作为距离的度量），使用距离的平方应该足够了。 - Arun R

Answer 1

正如其他人建议的那样，为所有N个点构建KD树。这需要O（N logN）时间。对于每个点，找到最近的邻居，单个点可以在O（logN）内完成。对于所有N个点，可以在O（N logN）中通过找到此集合的最小值来找到最孤立的点。

此外，现在您拥有一个方便的KD树可用于其他基于距离的查询。

- Hooked

---

我的理解是，在O(n log n)的时间内构建k-d树很棘手，大多数实现实际上是O(n log^2 n)。对于随机分布的点，最近邻查找通常是O(log n)。如果分布不随机，情况可能会更糟。您还必须使用算法的调整版本，否则每个点的最近邻查找将简单地返回相同的点。如果您需要对树执行其他查询，则肯定是一种胜利。如果没有，您可能需要先尝试一个更简单的高复杂度算法。 - Adrian McCarthy

@Hooked "请注意，x 不必是 P 中预先存在的点" 如果点已经存在，Kd 树将如何工作。它会返回相同的点。 - tashfeen

Answer 2

我看不到比O(n^2)更好的方法。如果将点预处理成空间分区结构，可能会有更好的方法，但这些通常只在进行多个计算时才有用。

但即使是O(n^2)，你也可以进行一些优化，以减少常数因子，从而在几秒钟内检查100,000个点。

基本算法：

nearest_of_most_isolated = 0
for every point A {
  nearest = infinity
  for every point B != A
    nearest = min(nearest, distance(A, B));
  if (nearest > nearest_of_most_isolated) {
    nearest_of_most_isolated = nearest
    most_isolated = A
  }
}
return most_isolated;

优化机会：

1. 在内部循环中可以提前退出。如果 nearest becomes < nearest_of_most_isolated，那么可以跳出内部循环，因为您已经可以排除该点。这是一个相当显著的改进。

2. 您可以对距离计算进行备忘录，但这需要 O(n^2) 的内存。通过聪明地利用对称性（从 A->B 的距离与从 B->A 的距离相同），您可以将其减半。但是，距离计算非常简单，因此可能不值得这样做。

3. 由于您只是比较相对距离，因此可以使用距离的平方，这比实际距离更快计算。这进一步降低了 #2 的价值。

4. 如果您有多个处理器或核心，可以通过在候选城市的 n 个子集中运行 n 个算法实例并在各自的结果上进行后续处理来并行化此过程（内部循环仍必须遍历它们所有）。如果点数非常大，则这可能是值得的。

- Adrian McCarthy

---

@VaughnCato已经提供了一种使用kDtrees的O(nlogn)解决方案，用于解决距离最近邻居的距离最大化问题。 - ile