# How we can calculate the distance between two points farthest?

We have $$n$$ points in the plane and our problem is to compute distance between two points farthest?

For example:

• With $$n=8$$, and $$8$$ points are: $$(0,5),(1,8),(3,4),(5,0),(6,2),(6,6),(8,3),(8,7)$$ and the result is $$\sqrt{80}$$.

This is my try: I think this problem relevants to convex hull theorem, but I amn't complete.

• There are algorithms for the so-called closest pair problem. See, for example, en.wikipedia.org/wiki/Closest_pair_of_points_problem. You can readily adapt those to the furthest pair. – Cye Waldman Apr 27 at 14:44
• Thanks for your comment @CyeWaldman, but I need compute distance of two pointer farthest – know dont Apr 27 at 14:50

One way to solve is to look for the most extreme single-coördinate separations first: in this case you have an (8,2) and a (4,8), sorting by the first and second coördinates respectively.

Since you have a (4,8) and $$4^2+8^2=80$$ you have some bounds for what can do better:

|(5,7)|² = 25+49 = 74, no
|(6,7)|² = 36+49 = yes
So (7,7), also yes, and (7,6).
|(6,6)|² = 36+36 = no.


So then these sorted lists can be used to find single-coordinate separations of 7; we know 6 is too small.

This quickly shows that we only have to check three other pairings of points,

(1,8) - (8,3)
(1,8) - (8,7)
(5,0) - (8,7)


But in none of the three cases is the other coördinate separated by 6 or 7 as required.

• I'm thanks you for your comment, but can you give me algorithm for this problem to solve it!!! Why we have (8,2) and (4,8) – know dont Apr 27 at 15:21
• @knowdont $(8, 2) = (8,7) - (0,5)$ as you can see from your ordering above, the first and last element. Now it is slightly more complicated than just first and last element: if there are a lot of elements with the same x-coördinate at the top and bottom then we need to sort by y-coördinate and in principle compare two pairs of them, so if M is the maximum x, m is the minimum x, we have four points (M, max y) - (m, min y) and (M, min y) - (m, max y), where minimums are taken over elements that have the right x-coördinate, to look for the biggest y-separation. – CR Drost Apr 27 at 16:53
• So, I looked at pairing (0, 5) with both (8, 7) and (8, 3) and found the y-separation 2 in any case there. Similarly for (4, 8), that is because (-4, 8) = (1, 8) - (5, 0). As I stated, I sorted by y-coordinate and here it is very easy, there is only one pair with y = min y and only one pair with y = max y. So I did not have to compare the two (min, ymax), (max, ymin) and (max, ymax), (min, ymin) pairs because it was all the same point. – CR Drost Apr 27 at 16:57
• I understand what you've done here but it's just an ad hoc solution. Suppose that tomorrow he has n=800 points. I just modified a closest-point algorithm I wrote by changing two 'min' to 'max' and can solve for any n. – Cye Waldman Apr 27 at 23:39
• @CyeWaldman I can say very confidently, that if he or she has 800 points, the best computer algorithm will still be brute force. I didn't know whether he or she wanted a computerized solution, so I gave a human one. However, you can convert this into an algorithm which would be in the average case $n \log n$, which Wiki says is optional. That might also be its worst case. So why are you grumpy? – CR Drost Apr 28 at 0:17