Return to Answer

Complexity is O(N^3) for brute force algorithm. 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))

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)

Complexity is O(N^3) for brute force algorithm. 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 > |AB|+|AC|, 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))

Complexity is O(N^3) for brute force algorithm. 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))

Complexity is O(N^3) for brute force algorithm. 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 we know distances for AB and AC and MAX > (AB+AC), then we can skip calculation for BC.

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

Complexity is O(N^3) for brute force algorithm. 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 > |AB|+|AC|, 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))