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

Question

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.

Answer 1

Start with point with lowest x-coord. (Call it Point X) Construct set of "boundary points" starting with point x, and vertical line through the point, There should be no other points to left of PointX) find the next point in boundary by slowly rotating the line clockwise (Or counterclockwise) until the line touches some other point, (see below). Add that point to the set and repeat with that next point to get the next one, until you eventually get back to the original point x. You npw have a set of points forming the boundary of the complete set. Compare distance between each pair in this reduced set to find the pair that are furthest apart.

To "rotate the line" (to find each sequential boundary point), take the point which is "furthest" in the direction perpindicular to the line used for the last boundary point, and construct a new line between the last boundary point and that "next" point. Then verify that there are no other points furthur in the new perpindicular direction formed by that new line. If there are no other points "furthur out" in the dirtection perpindicular to this line or to the last line, then this is the right cjhoice for the next boundary point, if there is such a point, switch to that one and retest.

Answer 2

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.

Answer 3

You're asking to compute the diameter of the set. The standard technique is to first compute the convex hull, which reduces the problem to finding the diameter of a convex polygon. Even in the case where you don't eliminate any points, this added information is exactly what's needed to solve the problem efficiently. However, finding the diameter of a convex polygon is not entirely trivial; several published papers with algorithms for this task turn out to be incorrect.

Here's a fairly readable discussion of a correct O(n) algorithm for the task (where n is the number of points in the convex hull).

Also, note the the iphone isn't that limited; a carefully written implementation of even the completely naive algorithm can handle 1000 points in less than a tenth of a second. Of course, using the correct algorithm will let you go much faster =)

Answer 4

See these pages (the one linked to and the pages reachable by clicking on the "next" links) on computing the diameter of the convex hull of a set of points.

My quick summary:

1. compute set of points in convex hull (= O(n log n), the only time you get O(n) is if you sort the list first which takes O(n log n) anyway)
2. order along boundary (you get this for free if you use a Graham scan for #1)
3. use one of the O(n) diameter algorithms to scan for antipodal points with greatest diameter. Shamos algorithm looks good to me as it's one of the rotating calipers algorithms.