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

Question

我有一组点，需要知道哪一个离其它所有点的欧几里得距离最远。 我想从O(n^2)上改进这个算法。

现在，我听说了Kd树可以解决这个问题，但是如果点'x'已经存在于Kd树中，Kd树无法提供最近的距离。而且没有相应的实现来移除它。

编辑： 您可以通过在“最近搜索算法”和“设置根/父节点”的开始搜索时忽略自身来解决此问题。

- tashfeen

---

使用 'dist' 函数。 - IRTFM

无论如何都会使用dist函数，我想要一个比O（n ^ 2）更好的算法。 - tashfeen

请参见：https://dev59.com/T3E85IYBdhLWcg3whD7k - wschella

你听说过凸包吗？ - Shravan40

可能是在大型集合中查找最远的球体的高效算法的重复问题。 - XCS

Answer 1

给定n个点Pi，1 <= i <= n:

1. 构建kd树（使用O(n)中位数算法，时间复杂度为O(n log n)）。 2. 对于所有的点Pi：寻找第二近的点（最近的点是它本身），计算距离并记住Pi，如果距离是新的最小值；这又是一个O(n log n)的操作。 总之，这是一个O(n log n)的算法。

- coproc

---

ld n 是什么？log2是什么？ - XCS

ld 是以 2 为底的对数；在大 O 表示法中，这实际上与 log n (以 e 为底) 相同。 - coproc

@coproc 你来自德国吗？我在维基百科上看到 ld 在德国被广泛使用 :D - XCS

@tashfeen “k-nearest”是kd树上的标准函数；您还可以修改“nearest”函数以忽略给定点本身。 - coproc

@coproc，你能提供一下k最近邻算法的代码链接吗？我找不到。或者如果你能帮我解决在最近邻算法中如何“忽略自身”的问题，我会非常感激的。 - tashfeen

Answer 2

我猜你想找到最大化距离最近邻居的点，就像南太平洋上的小岛距离最近的陆地有1100英里。

好吧，你不应该使用O(n^2)。假设你有一百万个点，将这些点分成一个1000 x 1000的网格。要找到最近的点，你只需要检查九个相邻的网格，所以你远远低于O(n^2)。如果一个网格包含很多点，它们会很接近，因此你可以快速从搜索中删除它们。

- gnasher729

---

此解决方案仍为“O(N^2)”时间复杂度。你怎样能确保“9个相邻网格”中不包含所有N个点？ - XCS