Linear algorithm to find two points with at least half diameter distance in a point set

0
votes

I am stuck with the following homework problem:

Consider a point set P in the plane with |P| = n and let D(P) the diameter of P, i.e. the maximum Euclidean distance between any two points in P. I am tasked to find an algorithm of O(n) time that on input of P returns two points x and y of P with d(x,y) >= D(P)/2, where d denotes the Euclidean distance.

I have no idea how I could do that. Could you give me a hint?

1
algorithmcomputational-geometry
Any point is at least that far from at least one of the two points in the diameter... – David Eisenstat
Thanks for your answer, but I can not follow you. We can not assume that D(P) is given, the algortihm ONLY input is P and computing D(P) takes O(n log(n)) time – 3nondatur
If it's even further from some other point, so much the better. – David Eisenstat
Just to make sure I understand you correctly. We pick some arbitrary point, say x, and then we compute d(x,y) for all the other points y in P. We then just pick the y with the greatest d(x,y), correct? – 3nondatur

1 Answers

1
votes

Assume your points are (xi,yi)

  1. find point with min(xi) with O(n) and name it minX_point
  2. find point with max(xi) with O(n) and name it maxX_point
  3. find point with min(yi) with O(n) and name it minX_point
  4. find point with max(yi) with O(n) and name it maxY_point

now consider rectangle which boxes these 4 point (with horizontal and vertical edges) the diameter of this rectangle is bigger or equal to D(P) because all of P points are boxed in it. the diameter of rectangle is as following Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2) now find max((mixX-maxX),(minY-maxY)) the maximum would be your desired point for example maxX_point and minX_point because if the distance be less than D(P)/2 then we have Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2) < sqrt((D(P)/2)^2+(D(P)/2)^2)=D(P)/sqrt(2) which Rec_Diameter>=D(P) < D(P)/sqrt(2) is not true