# Find the diameter of a set faster than $O(|M|^2)$

$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).

-

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.
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. – Thomas Nov 22 '12 at 14:24
@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? – Paresh Nov 23 '12 at 8:02