4

I meet a question that given a set of data points, I need to find two points that are most distant. In my setting, there is no coordinate for each point, only I can do is calculate the distance between two points with a specific distance metric (which satisfies all three axioms, identity of indiscernibles, symmetry, and triangle inequality).

I know if these points are in the plane, i.e. they have coordinates, then there are algorithms that are better than O(n^2) to find the two most distant points, for example this question How to find two most distant points?. But is there any algorithm better than O(n^2) that can solve my question?

Thanks!

cbyh
  • 163
  • 4
  • It seems relatively clear that if the algorithm runs is shorter time than n², then it doesn't have time to examine all the pairwise distances. In that case, how can it be sure that one of the non-looked-at distances isn't much higher than the others? – Stef Nov 18 '21 at 16:28
  • 2
    Long story short: it might be possible to do better than n² if you have additional assumptions on your distances (for instance, do they satisfy the [triangular inequality](https://en.wikipedia.org/wiki/Triangle_inequality#Metric_space)?). But without any extra assumptions, you can't hope to do better than computing all the pairwise distances and keeping the maximum. – Stef Nov 18 '21 at 16:30
  • 1
    Thank you for the reply! Yes here by saying "distance metric" I mean the distance that satisfies all three axioms (identity of indiscernible, symmetry, triangle inequality), under these conditions, can we have some better algorithm? – cbyh Nov 18 '21 at 17:13
  • I think that the answer to this question is: "No". I am not an expert in this, but those "*Less than O(n^2)*" for Euclidian geometry actually exploit low dimensionality and are something like `O(N^[d/2])` where `d` is the number of dimensions. So even if you had coordinates, but they were in say, 10 dimensions, you couldn't use that approach to get less than O(n^2), it would be at least `O(n^5)`. So effectively, above 4 dimensions, you'd just use the brute-force "*compare all pairs*" method anyway. So without more knowledge of your distance metric, its `O(n^2)`. – RBarryYoung Nov 18 '21 at 17:45

2 Answers2

3

No. Consider the metric induced by a complete graph minus one edge.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
0

A counter-example:

In the Euclidean metric, A-B are the farthest. In Manhattan, B-C.

enter image description here