How to find two most distant points?

Question

This is a question that I was asked on a job interview some time ago. And I still can't figure out sensible answer.

Question is:

you are given set of points (x,y). Find 2 most distant points. Distant from each other.

For example, for points: (0,0), (1,1), (-8, 5) - the most distant are: (1,1) and (-8,5) because the distance between them is larger from both (0,0)-(1,1) and (0,0)-(-8,5).

The obvious approach is to calculate all distances between all points, and find maximum. The problem is that it is O(n^2), which makes it prohibitively expensive for large datasets.

There is approach with first tracking points that are on the boundary, and then calculating distances for them, on the premise that there will be less points on boundary than "inside", but it's still expensive, and will fail in worst case scenario.

Tried to search the web, but didn't find any sensible answer - although this might be simply my lack of search skills.

Answer 1

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.

Answer 2

Just a few thoughts:

You might look at only the points that define the convex hull of your set of points to reduce the number,... but it still looks a bit "not optimal".

Otherwise there might be a recursive quad/oct-tree approach to rapidly bound some distances between sets of points and eliminate large parts of your data.

Answer 3

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: http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other

Also:

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

Answer 4

A starting point could be looking at closest-point problems, which have been examined. Wikipedia lists some options:

http://en.wikipedia.org/wiki/Closest_point_query

Answer 5

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