CODEWITHSUNDEEP
algorithmcomputational-geometry
3nondatur
3nondatur

Reputation: 475

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

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?

Upvotes: 0

Views: 63

Answers (1)

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

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

Upvotes: 1

Related Questions