二维地图上最孤立的点 - 算法
Most isolated point on 2d map - algorithm
我有一组点，需要知道哪个点与其他点的欧氏距离最远。
我想从 O(n^2)
改进这个
伙计们，我听说过 Kd 树的解决方案，但是
如果点 'x' 已经存在于 Kd 树中，则 KD 树不提供最近距离。并且没有要删除的实现。
编辑：
您可以通过忽略 "nearest search algo" 和 "where we set root/parent" 中的自我来开始搜索
我假设您想找到使到最近邻居的距离最大化的点。就像南太平洋的一个小岛，距离最近的陆地有 1100 英里。
好吧，你应该离O(n^2)还很远。假设你有一百万分。将点划分为 1000 x 1000 的网格。要找到最近的点，您只需检查九个相邻的网格，因此您远低于 O (n^2)。如果网格包含很多点，它们将靠得很近，因此您可以快速将它们从搜索中删除。
给定 n 个点 Pi, 1 <= i <= n:
build kd-tree（使用中值算法的 O(n) 中值，这是 O(n log n)）
对于所有点 Pi：找到第二个最近点（最近点将是点本身），计算距离，如果距离是新的最小值则记住 Pi；这又是 O(n log n)。
总而言之，这是一个复杂度为 O(n log n) 的算法。
我有一组点，需要知道哪个点与其他点的欧氏距离最远。 我想从 O(n^2)
改进这个伙计们，我听说过 Kd 树的解决方案，但是 如果点 'x' 已经存在于 Kd 树中，则 KD 树不提供最近距离。并且没有要删除的实现。
编辑： 您可以通过忽略 "nearest search algo" 和 "where we set root/parent" 中的自我来开始搜索
我假设您想找到使到最近邻居的距离最大化的点。就像南太平洋的一个小岛，距离最近的陆地有 1100 英里。
好吧，你应该离O(n^2)还很远。假设你有一百万分。将点划分为 1000 x 1000 的网格。要找到最近的点，您只需检查九个相邻的网格，因此您远低于 O (n^2)。如果网格包含很多点，它们将靠得很近，因此您可以快速将它们从搜索中删除。
给定 n 个点 Pi, 1 <= i <= n:
build kd-tree（使用中值算法的 O(n) 中值，这是 O(n log n)）
对于所有点 Pi：找到第二个最近点（最近点将是点本身），计算距离，如果距离是新的最小值则记住 Pi；这又是 O(n log n)。
总而言之，这是一个复杂度为 O(n log n) 的算法。