Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 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.

share|improve this answer
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. –  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
    
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. –  Thomas Nov 23 '12 at 9:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.