How to find two most distant points?

Question

EDIT: One way is to find the convex hull http://en.wikipedia.org/wiki/Convex_hull of the set of points and then the two distant points are vertices of this.

Possibly answered here: Algorithm to find two points furthest away from each other

Also:

• http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

Boundary point algorithms abound (look for convex hull algorithms). From there, it should take O(N) time to find the most-distant opposite points.

From the author's comment: first find any pair of opposite points on the hull, and then walk around it in semi-lock-step fashion. Depending on the angles between edges, you will have to advance either one walker or the other, but it will always take O(N) to circumnavigate the hull.

You are looking for an algorithm to compute the diameter of a set of points, Diam(S). It can be shown that this is the same as the diameter of the convex hull of S, Diam(S) = Diam(CH(S)). So first compute the convex hull of the set.

Now you have to find all the antipodal points on the convex hull and pick the pair with maximum distance. There are O(n) antipodal points on a convex polygon. So this gives a O(n lg n) algorithm for finding the farthest points.

This technique is known as Rotating Calipers. This is what Marcelo Cantos describes in his answer.

If you write the algorithm carefully, you can do without computing angles. For details, check this URL.

A stochastic algorithm to find the most distant pair would be

• Choose a random point
• Get the point most distant to it
• Repeat a few times
• Remove all visited points
• Choose another random point and repeat a few times.

You are in O(n) as long as you predetermine "a few times", but are not guaranteed to actually find the most distant pair. But depending on your set of points the result should be pretty good. =)

This question is introduced at Introduction to Algorithm. It mentioned 1) Calculate Convex Hull O(NlgN). 2) If there is M vectex on Convex Hull. Then we need O(M) to find the farthest pair.

I find this helpful links. It includes analysis of algorithm details and program. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Wish this will be helpful.