7
$\begingroup$

$M$ is a finite set of points in a metric space. I want to calculate the diameter of the set, i.e. the greatest distance between two points. Is there a smarter way to do this than to calculate the distance between all pairs of points?

$ \delta = \max_{x,y\in M} d(x,y) $

I suppose the triangle inequality could let me know that some distance don't have to be calculated, but it seems like a lot of work to do those checks, and the distance function isn't very expensive.

In case someone was wondering, the points are longitude-latitude points and the distance function the Great Circle distance (which is a metric).

1 Answers 1

1

I believe this can be done in $O(n$log$n)$, where $n$ is the number of points. The algorithms that I saw use the Euclidean distance, but I believe that it can be replaced by any metric distance measure. I am not aware of the Great Circle distance, but if it is metric, then this method should work.

The idea is to compute the convex-hull of the points, which can be done in $O(n$log$n)$, and then find the pair of furthest points from the vertices of this convex hull in $O(n)$ time.

Have a look at a similar question on Euclidean distances. Some description of the algorithm can be found here. Here is a paper treating diameter calculations in $d$ dimensions.

  • 0
    Well, you would have to embed a general metric space in a vector space in order to construct the convex hull. I'm not sure if you can do it directly on the sphere.2012-11-23