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

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.

Answer 2

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.

Answer 3

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 4

Given a set of points {(x1,y1), (x2,y2) ... (xn,yn)} find 2 most distant points.

My approach:

1). You need a reference point (xa,ya), and it will be:
xa = ( x1 + x2 +...+ xn )/n
ya = ( y1 + y2 +...+ yn )/n

2). Calculate all distance from point (xa,ya) to (x1,y1), (x2,y2),...(xn,yn)
The first "most distant point" (xb,yb) is the one with the maximum distance.

3). Calculate all distance from point (xb,yb) to (x1,y1), (x2,y2),...(xn,yn)
The other "most distant point" (xc,yc) is the one with the maximum distance.

So you got your most distant points (xb,yb) (xc,yc) in O(n)

For example, for points: (0,0), (1,1), (-8, 5)

1). Reference point (xa,ya) = (-2.333, 2)

2). Calculate distances:
from (-2.333, 2) to (0,0) : 3.073
from (-2.333, 2) to (1,1) : 3.480
from (-2.333, 2) to (-8, 5) : 6.411
So the first most distant point is (-8, 5)

3). Calculate distances:
from (-8, 5) to (0,0) : 9.434
from (-8, 5) to (1,1) : 9.849
from (-8, 5) to (-8, 5) : 0
So the other most distant point is (1, 1)

Answer 5

This seems easy if the points are given in Cartesian coordinates. So easy that I'm pretty sure that I'm overlooking something. Feel free to point out what I'm missing!

1. Find the points with the max and min values of their x, y, and z coordinates (6 points total). These should be the most "remote" of all the boundary points.
2. Compute all the distances (30 unique distances)
3. Find the max distance
4. The two points that correspond to this max distance are the ones you're looking for.