Calculate the maximum distance between vectors in

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

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 2

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 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/

Answer 4

So suppose you have a pair of points A and B. Consider the hypersphere that have A and B at the north and south pole respectively. Could any point C contained in the hypersphere be farther from A than B?

Further suppose we partition the pointset into sqrt(N) hyperboxes with sqrt(N) points each. For any pair of hyperboxes, we can calculate in k time the maximum distance possible between any two points of the infinite set of points contained within them - by simply calculating the distance between their furthest corners. If we already have a candidate better than this we can discard all pairs of points from those hyperboxes.