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

1 Answer 1

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$
7
  • $\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, 2019 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, 2019 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, 2019 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$ Apr 27, 2019 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, 2019 at 0:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .