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.

Joe

If you can do the sorting in O(nlogn), try to use it. – Midstream

You cannot "sort" a multidimensional space, or more precisely, you can sort it in many different ways – Chitter

you know there may not be a unique answer, do you need all most distant pairs or just a most distant pair – Gracchus

@jk - single most distant pair will do. – Joe

Answer 1

For this specific problem, with just a list of Euclidean points, one way is to find the convex hull of the set of points. The two distant points can then be found by traversing the hull once with the rotating calipers method.

Here is an O(N log N) implementation:

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

If the list of points is already sorted, you can remove the sort to get the optimal O(N) complexity.

---

For a more general problem of finding most distant points in a graph: Algorithm to find two points furthest away from each other

The accepted answer works in O(N^2).

Babylonian

That questions is about graph algorithms, not computational geometry, isn't it? – Condorcet

you can model the problem as a complete weighted graph – Gracchus

Answer 2

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.

Retene

Now assume all given N points are on the convex hull. Still O(N)? – Condorcet

Yes, because you 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 vertices, you will have to advance either one walker or the other, but it will always take O(N) to circumnavigate the hull. – Retene

Please, post a complete algorithm for checking what points are furthest, given the convex hull (a set of nodes and their order). – Condorcet

Sorry, that's more work than I can be bothered with right now. – Retene

Well, your comment anyway is the best explanation of a correct algorithm on this page, so I'll put it into answer text and upvote then. – Condorcet

Thanks Pavel! I was not trying to be dismissive, by the way (my last comment reads worse than I intended). It's just a fair bit of fiddly geometry and edge-cases to get it right. – Retene

@Marcelo, oh, saying "complete algorithm" in computational geometry usually means "as complete as possible before it gets boring" :-) – Condorcet

Very cool! Thanks Rafal (And here was I, thinking I made it up ;-). – Retene

Answer 3

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.

Breastbone

URL is broken .. any chance you can pass along a new one? – Disorientate

@Disorientate you can find it here web.archive.org/web/20180528104521/http://www.tcs.fudan.edu.cn/… – Roustabout

Answer 4

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.

Healy

Fixed link via the wayback machine URL – Scroop

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

Cider

Consider this, and then correct or delete your answer so you don't get downvotes: imagine you have an almost-square set of points, {A=(0, 0), B=(10, 10), C=(10, 0), D=(0, 11)}; most distant points are BD (distance = 14.86); but if you try to start at A or B you'll feel tempted to remove C (AC = BC = 10) or D (AD = 11, BD = 10.05) since they're closer to the chosen vertex than the opposite vertex (AC = 14.14), while in reality the longest distance is really 14.86 . – Rufford

@sr pt: In your example, CD are the most distant points, not BD. Starting in A or B one would always choose the other in step 2, so only these two get removed in step 4. – Cider

Answer 6

Find the mean of all the points, measure the difference between all points and the mean, take the point the largest distance from the mean and find the point farthest from it. Those points will be the absolute corners of the convex hull and the two most distant points. I recently did this for a project that needed convex hulls confined to randomly directed infinite planes. It worked great.

See the comments: this solution isn't guaranteed to produce the correct answer.

Conciliar

I think this answer it the most understandable for people like me who aren't math geniuses. Thanks – Diffidence

Assuming this is correct, this is the best answer to this question (IMO), since it is O(n), can be generalized to 3 dimensions, and would be trivial to implement. – Bully

This algorithm doesn't work. Try with these points: (-10, 0), (100, 0), (0, 70), (0, -70). Farthest point from mean is (100, 0), but the two most distant points are (0, 70) and (0, -70). – Stone

Any algorithm that uses "mean" position (i.e. centre of gravity) could be biased by points being clustered unevenly near a "bad" position, so IMHO such an algorithm is unlikely to be efficient in finding the correct result. But I guess it could find a good approximation in many cases. If you are OK with a fast approximate solution then a "mean" algorithm could work OK for evenly distributed points, and a way that picks points on the bounding box could work OK (with sqrt2) for unevenly distributed points. – Lupine

this only works in the one-dimensional case. not even two-dimensional: imagine a T with width 4 and height 3 and mean in the crossing. the bottom point has the largest distance from the mean and has only distance sqrt(2²+3²)=3.6 from the left and right point, not 4. – Malvina

Answer 7

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.

Mobley

Answer 8

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.

Irrelative

Okay so after further thought this isn't guaranteed to find the two farthest points. Doh! It does however give you the minimum size of the region delineated by the point array, which will not be exceeded by a scale of more than sqrt(2). Might be useful! – Irrelative

Answer 9

Here's a good solution, which works in O(n log n). It's called Rotating Caliper’s Method. https://www.geeksforgeeks.org/maximum-distance-between-two-points-in-coordinate-plane-using-rotating-calipers-method/

Firstly you find the convex hull, which you can make in O(n log n) with the Graham's scan. Only the point from the convex hull can provide you the maximal distance. This algorithm arranges points of the convex hull in the clockwise traversal. This property will be used later.

Secondly, for all the points on the convex hull, you'll need to find the most distant point on this hull (it's called the antipodal point here). You don't have to find all the antipodal points separately (which would give quadratic time). Let's say the points of the convex hall are called p_1, ..., p_n, and their order corresponds to the clockwise traversal. There is a property of convex polygons that when you iterate through points p_j on the hull in the clockwise order and calculate the distances d(p_i, p_j), these distances firstly don't decrease (and maybe increase) and then don't increase (and maybe decrease). So you can find the maximum distance easily in this case. But when you've found the correct antipodal point p_j* for the p_i, you can start this search for p_{i+1} with the candidates points starting from that p_j*. You don't need to check all previously seen points. in total p_i iterates through points p_1, ..., p_n once, and p_j iterates through these points at most twice, because p_j can never catch up p_i as it would give zero distance, and we stop when the distance starts decreasing.

Yardarm

Answer 10

A solution that has runtime complexity O(N) is a combination of the above answers. In detail: (1) One can compute the convex hull with runtime complexity O(N) if you use counting sort as an internal polar angle sort and are willing to use angles rounded to the nearest integer [0, 359], inclusive.

(2) Note that the number of points on the convex hull is then N_H which is usually less than N.
We can speculate about the size of the hull from information in Cormen et al. Introduction to Algorithms, Exercise 33-5. For sparse-hulled distributions of a unit-radius disk, a convex polygon with k sides, and a 2-D normal distribution respectively as n^(1/3), log_2(n), sqrt(log_2(n)).

The furthest pair problem is then between comparison of points on the hull. This is N_H^2, but each leading point's search for distance point can be truncated when the distances start to decrease if the points are traversed in the order of the convex hull (those points are ordered CCW from first point). The runtime complexity for this part is then O(N_H^2).

Because N_H^2 is usually less than N, the total runtime complexity for furthest pair is O(N) with a caveat of using integer degree angles to reduce the sort in the convex hull to linear.

Penner

Answer 11

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)

Whensoever

first you didn't even prove why this is correct, but here is an example why it's wrong {{0, 0},{10,0},{-10,0},{0,17}} correct answer is 20, your answer is ~19.72 – Eogene