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.

  • 1
    But then you would have to embed the metric space in $R^{|M|}$ or some other Euclidean space, which you can do, but you need again all non-trivial distances.2012-11-22
  • 0
    @Thomas I am afraid I don't quite follow. Here, $M$ is the set of points and not the number of dimensions. Also, I was under the impression that since the Great Circle distance is metric, simply replacing each computation of $d(a, b)$ from the 2D Euclidean distance to the Great Circle distance will work. Is that an incorrect assumption?2012-11-23
  • 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