algorithm - 最近点对算法的一种变体

Question

最近点对问题在计算几何中是众所周知的:给定一个点列表 (x, y) 找到具有最小欧氏距离的点对。现在我要问这个问题的变体:给定一个包含 n 个点 (xi,yi) (n+1>i>0) 的列表，找到每个点 (xi, yi) 最近的欧几里得距离，然后计算所有点的平均最近欧氏距离。我知道蛮力法:

all_distance = [];
for i= 1 to n
    p = (xi,yi);
    dis = [];
    for j= 1 to n
      if j==i
          continue;
      else
          q = (xj,yj);
          pt_dis = distance(p,q);
      end 
      dis = [dis; pt_dis];
    end
    all_distance = [all_distance; nearest(dis)]

end
mean_distance = all_distance/n;

此方法简单明了，但计算速度相当慢。我想知道是否有一些快速算法可以解决这个问题。谢谢!

Answer 1

这个问题通常最好通过 kd-tree 解决。或 quadtree ，但是如果你想要一些快速而肮脏的东西，那么你应该尝试以某种方式对你的观点进行分类。也就是说，假设您的点都大致均匀分布在 (0,0) 到 (10,10) 的范围内，您可以制作 1 个单位正方形的桶，在这种情况下为 100 个桶。现在你通过在它的桶和所有八个相邻的桶中寻找它最近的点来处理一个点。如果您发现距离不超过 1 个单位的任何点，那么您就知道它是最近的点，因为更近的点必须不在相邻的桶之一中，这意味着它必须超过 1 个单位。如果您没有在这附近找到一个点，那么您将需要检查所有点，或者您可以扩展到下一个桶环。