How we can calculate the distance between two points farthest?

Question

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.

Answer 1

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.