CODEWITHSUNDEEP
algorithm
AngusTheMan
AngusTheMan

Reputation: 582

Distance calculation optimisation

I am writing an algorithm that computes the nearest neighbours of points in a 2d plane. Currently I brute force compute every distance via two for loops 

for(i=0; i<N ;i++){
   for (j=0; j<N; j++{ 
      /* distance computation */
      /* remember smallest distance for all i */
   }
}

I already have an if(i==j) continue; statement so that we avoid computing the distances between the same points. I am wondering how can I optimise this algorithm further. For instance how can I account for the symmetry of distance(i,j) = distance (j,i)? Are there any other points that I should think about?

Further, could you describe to me another algorithm that would be a better way to perform this calculation? I have looked into binary trees but am quite unsure how they actually could be applied to my problem!

Upvotes: 1

Views: 118

Answers (2)

B. D
B. D

Reputation: 7823

You want to use quadtrees as your data structure

This nice post gives you details on how to proceed

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

You can account for symmetry by starting j at i+1. This will also take care of the i == j situation without a special case:

for (i = 0 ; i != N ; i++) {
    for (int j = i+1 ; j != N ; j++) {
        dist = ... // Compute the distance
        distance[i][j] = distance[j][i] = dist; // Set in both directions
    }
}

Upvotes: 1

Related Questions