0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Cye Waldman Apr 27 at 14:44
  • $\begingroup$ Thanks for your comment @CyeWaldman, but I need compute distance of two pointer farthest $\endgroup$ – know dont Apr 27 at 14:50
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – know dont Apr 27 at 15:21
  • 1
    $\begingroup$ @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. $\endgroup$ – CR Drost Apr 27 at 16:53
  • 1
    $\begingroup$ 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. $\endgroup$ – CR Drost Apr 27 at 16:57
  • $\begingroup$ 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. $\endgroup$ – Cye Waldman Apr 27 at 23:39
  • $\begingroup$ @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? $\endgroup$ – CR Drost Apr 28 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.