CODEWITHSUNDEEP
algorithmgeometry
Ahmad Faiyaz
Ahmad Faiyaz

Reputation: 326

Faster way to find All Pair Euclidean Distance in c++

Say , In D-dimensional Euclidean space, N lattice points are given, ( E.g.: Highest 6D space is possible ), Now you have to find the all pair Euclidean Distance. Now we generally do with n^2 loop, but if N = 5000, then this O(n^2) is too slow, then is there any efficient way to find the distance ?

Upvotes: 0

Views: 645

Answers (2)

Hooked
Hooked

Reputation: 88148

While @MBo is correct in that O(N^2) is the best big-O time, if the points are indeed on a special kind of lattice, namely a rectangular lattice, you can exploit the symmetry to bring down the prefactor. We can assume, in generality, that we have a D-dimensional square lattice that extends outwards at most m units in each direction. This gives N=2*d*m points. We only need to compute the upper quadrant in this lattice as the other dimensions are going to be the same. For example, in 2D consider the points:

(3,4)   -> 5
(-3,4)  -> 5 
(3,-4)  -> 5 
(-3,-4) -> 5

In general you can reduce the computation by a factor (2^d-1) points, which is significant for higher dimensions. In 6-dimensions, that's a constant factor of 63.

Upvotes: 0

MBo
MBo

Reputation: 80187

There are N*(N-1)/2 pairs, so O(N^2) is the best time possible

Upvotes: 1

Related Questions