Calculate the maximum distance between vectors in an array

Question

Assume we have an array that holds n vectors. We want to calculate the maximum euclidean distance between those vectors. The easiest (naive?) approach would be to iterate the array and for each vector calculate its distance with the all subsequent vectors and then find the maximum. This algorithm, however, would grow (n-1)! with respect to the size of the array.

Is there any other more efficient approach to this problem?

Thanks.

Answer 1

Your computation of the naive algorithm's complexity is wonky, it should be O(n(n-1)/2), which reduces to O(n^2). Computing the distance between two vectors is O(k) where k is the number of elements in the vector; this still gives a complexity well below O(n!).

Answer 2

Complexity is O(N^2 * K) for brute force algorithm (K is number of elem in vector). But we can do better by knowing that in euclidean space for points A,B and C:

|AB| + |AC| >= |BC|

Algorithm should be something like this:

If max distance found so far is MAX and for a |AB| there is a point C, such that distance |AC| and |CB| already computed and MAX > |AC|+|CB|, then we can skip calculation for |AB|.

It is difficult to tell complexity of this algorithm, but my gut feeling tells me it is not far from O(N*log(N)*K)

Answer 3

This question has been here before, see How to find two most distant points?

And the answer is: is can be done in less than O(n^2) in Euclidean space. See also http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/