algorithm - 二维 map 上最孤立的点 - 算法

Question

我有一组点，需要知道哪个点与其他点的欧氏距离最远。 我想从 O(n^2) 改进这个

伙计们，我听说过 Kd 树的解决方案，但是 如果 Kd 树中已经存在点 'x'，则 KD 树不提供最近距离。并且没有要删除的实现。

编辑: 您可以通过在“最近的搜索算法”和“我们设置根/父级的位置”最初开始搜索时忽略自身来做到这一点

Answer 1

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

1. 构建 kd-tree(使用中值算法的 O(n) 中值，这是 O(n log n))

2. 对于所有点 Pi:找到第二个最近点(最近点将是点本身)，计算距离，如果距离是新的最小值则记住 Pi；这又是 O(n log n)。

总而言之，这是一个复杂度为 O(n log n) 的算法。