8

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.

Improve this question
4
  • 3
    What do you mean by distance between vectors? How do you define distance between 2 vectors? Points is clear, but vectors? Commented Aug 24, 2012 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) Commented Aug 26, 2012 at 12:13
  • 1
    possible duplicate of How to find two most distant points? Commented Aug 26, 2012 at 12:13
  • 2
    @sdcvvc: That question asks about a 2D pointset. This is an kD pointset. Commented Aug 26, 2012 at 12:18

4 Answers 4

Reset to default
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!).

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Computing the distance between two vectors is O(k^2) -- this is incorrect. It should be O(k).
@HighPerformanceMark Euclidean space has some useful properties, which allow you not to check every pair of points.
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.
Well, I've tried to delete this answer but apparently once it's accepted I can't !
Haha, just delete the second paragraph.
|
3

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)

Improve this answer

Comments

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/

Improve this answer

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.