3

最近点对问题在计算几何中是众所周知的：给定一个点列表 (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;

这种方法很简单，但计算起来很慢。我想知道是否有一些快速算法可以解决这个问题。谢谢！

4

2 回答 2

2

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

于 2012-07-17T16:20:00.937 回答
2

您可以在 O(n log n) 时间内计算Delaunay 三角剖分，并且对于每个顶点，最近的点将是三角剖分上的相邻点之一。将要检查的总边数为 O(n)，因此它由 O(n log n) 三角剖分成本控制。

于 2012-07-17T16:32:42.367 回答