CODEWITHSUNDEEP
algorithmgeometry
feelfree
feelfree

Reputation: 11753

A variation of closest pair of points algorithm

Closest pair of points problem is well-known in computational geometry:given a list of points (x, y) find the pair of points that has the smallest Euclidean distance. Now I have a variation of this problem to ask: given a list of n points (xi,yi) (n+1>i>0), find the nearest Euclidean distance for each point (xi, yi), and then calculate the average nearest Euclidean distance for all the points. I know the brute-force method:

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;

This method is straightforward but rather slow to compute. I was wondering whether there are some quick algorithms to solve this problem. Thanks!

Upvotes: 3

Views: 913

Answers (2)

Larry
Larry

Reputation: 4559

You can calculate a Delaunay triangulation in O( n log n ) time, and for each vertex, the closest point will be one of the adjacent points on the triangulation. There will be O( n ) total edges to examine, so it is dominated by the O( n log n ) triangulation cost.

Upvotes: 2

Running Wild
Running Wild

Reputation: 3011

This problem is typically best solved by a kd-tree or quadtree, but if you want something quick-and-dirty then you should probably try bucketing your points in some way. That is, lets say your points are all roughly evenly distributed in the range (0,0) to (10,10), you could make buckets that are 1 unit square, for 100 buckets in this case. Now you process a point by looking for its nearest point in its bucket and all eight adjacent buckets. If you find any points that are 1 unit or less away then you know that it is the nearest point, since a closer point would have to not be in one of the adjacent buckets, which means it must be more than 1 unit away. If you don't find a point this close then you will need to check all points, or you can expand to the next ring of buckets.

Upvotes: 2

Related Questions