Given a set of points, how to find the two points that are farthest from each other?


Possible Duplicate:
Greatest linear dimension 2d set of points

I could compute the distance between each point and take the largest but that doesn't sound like a very efficient way to do it when there are a large (> 1000) number of points.

Note: This is for iPhone so I don't have a ton of processing power.

Best Solution

Why not just compute the convex hull of the points? Depending on the algorithm you use, it takes either O(n) or O(n log n) time and eliminates all the inner points from consideration. Then, only check these outermost points to find the two that are the farthest away.