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.

What do you mean by distance between vectors? How do you define distance between 2 vectors? Points is clear, but vectors? — mathematician1975, Aug 24 '12 at 11:09
Euclidean distance between two vectors is well defined: sqrt(sum((x_i-y_i)^2)) ? Are you concerned if the vectors are not of equal length? I think his question implies all the vectors are of equal length. (He is using vector in the math sense, not the C++ sense) — Andrew Tomazos, Aug 26 '12 at 12:13
possible duplicate of [How to find two most distant points?](http://stackoverflow.com/questions/2736290/how-to-find-two-most-distant-points) — sdcvvc, Aug 26 '12 at 12:13
@sdcvvc: That question asks about a 2D pointset. This is an kD pointset. — Andrew Tomazos, Aug 26 '12 at 12:18

High Performance Mark · Accepted Answer · 2012-08-26T12:03:12.513

4

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!).

edited Aug 26 '12 at 12:03

answered Aug 24 '12 at 11:13

High Performance Mark

77,191
7
105
161

2

`Computing the distance between two vectors is O(k^2)` -- this is incorrect. It should be O(k). – Leonid Volnitsky Aug 24 '12 at 13:20
1

@HighPerformanceMark Euclidean space has some useful properties, which allow you not to check every pair of points. – Qnan Aug 26 '12 at 11:29
3

Your second paragraph seems to imply that checking every pair is the best we can do. This is not the case, we can do much better. – Andrew Tomazos Aug 26 '12 at 11:53
Well, I've tried to delete this answer but apparently once it's accepted I can't ! – High Performance Mark Aug 26 '12 at 11:56
Haha, just delete the second paragraph. – Andrew Tomazos Aug 26 '12 at 12:02
Please elaborate in the case of O(n!) because the brute force approach does not have this complexity. Below the answer exploiting the fact that you compare euclidean distance where triangular inequality applies can save us some calculations. – partizanos Mar 30 '21 at 13:53

Leonid Volnitsky · Answer 2 · 2012-08-26T11:13:34.870

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)

score 2 · Answer 3 · edited May 23 '17 at 10:34

2

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/

edited May 23 '17 at 10:34

Community

1
1

answered Aug 26 '12 at 11:28

Qnan

3,714
18
15

Andrew Tomazos · Answer 4 · 2012-08-26T12:10:41.540

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.

Calculate the maximum distance between vectors in an array

4 Answers4

Linked