Search code examples
algorithmperformancepoints

Algorithm to get the 2 most distant point in a 2D plane (for homework)

I have to make a efficient algorithm that gets two point that are the most distant from each other and I am trying to get the O(nlogn) complexity. I searched for an efficient algorithm, but all I could find is for the closest points.

The output should just print the 2 points.

What I found by now is this algorithm from GeeksForGeeks : https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/ but is for the closest points.

And this solution:

mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

that looks way to complicated for a homework.

First method, looks weird, plus I don't think it works for my problem.

Any help would be appreciated.

Solution

  • Well this is homework so no code examples :)

    Here's O(n log n) approach:

    1. Find Convex Hull of all given points using any of O(n log n) convex hull algorithms

    2. Now we can notice that 2 farthest points will still be on convex hull

    3. We can find such points using Rotating calipers technique in O(n) time