10

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.

Community
  • 1
  • 1
willc2
  • 38,991
  • 25
  • 88
  • 99

4 Answers4

9

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.

Chris Bunch
  • 87,773
  • 37
  • 126
  • 127
  • This doesn't make things easier. If the amount of points in a convex hull is O(n), then the complexity remains the same. – P Shved Oct 24 '09 at 16:39
  • Very true. But the hope is that if there are >1000 points, then many of them will be inside the convex hull. – Chris Bunch Oct 24 '09 at 16:42
  • 2
    Great answer. I was going to say this. Start with the Akl-Toussaint heuristic to throw out as many points as possible before finding the convex hull. – Nosredna Oct 24 '09 at 16:42
  • 1
    You have reduced the complexity measure from O(n^2). In the worst case all the points are on the convex hull, but in many cases, you'll reduce the actual work by a large factor. – PanCrit Oct 24 '09 at 16:45
  • @Pavel (and @Chris) the expected number of points on the convex hull is `O(log n)`, so the expected running time for checking those points is `O(log^2 n)`. – Jesse Beder Oct 25 '09 at 03:41
  • @Jesse (and @Pavel, and @Chris): If there are k points on the convex hull, you can find the farthest pair in just O(k) time (using "rotating calipers"); it doesn't need k^2. See the answers at the other question asking the same thing: http://stackoverflow.com/questions/321989/greatest-linear-dimension-2d-set-of-points – ShreevatsaR Oct 25 '09 at 13:04
8

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 =)

Stephen Canon
  • 103,815
  • 19
  • 183
  • 269
  • It's O(n) only after finding the convex hull — if you're just given a set of points it may be O(n log n) to find the convex hull first. – ShreevatsaR Jul 21 '11 at 12:40
  • @ShreevatsaR: Of course. My answer explicitly says "where n is the number of points in the convex hull", which makes pretty clear that you need to find the convex hull first. – Stephen Canon Jul 21 '11 at 17:57
  • Yes, perhaps it does. Clarity is in the eye of the reader. :-) (The algorithm for the task in the question is obviously not O(n) where n is the number of points in the convex hull; it's the second part that is, as you say.) Anyway, I thought it's worth mentioning, just for completeness: people may arrive at these answers years later through search engines may not read carefully, and can get confused, etc. – ShreevatsaR Jul 21 '11 at 20:20
  • The pdf link is dead, a quick google search failed me, anyone have a copy? – Thomas Oct 10 '12 at 21:12
  • 1
    @Thomas: the algorithm is called "rotating calipers", and ShreevatsaR gives a good informal description of it in his answer to another question (http://stackoverflow.com/a/322409/142434) – Stephen Canon Oct 10 '12 at 23:57
0

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.

Charles Bretana
  • 143,358
  • 22
  • 150
  • 216
  • Same comment as to Chris. You don't make anything easier if on the outer bound there is not much less points. – P Shved Oct 24 '09 at 16:40
  • This sounds like an expensive way to compute the complex hull, followed by the rest of Chris Bunch's answer. – PanCrit Oct 24 '09 at 16:43
  • I did not know there was a technical term for this... (convex hull) but it is a rubber band boundary. I will check out other algorithms to calculate it... As to number of points, for any random collection of points, the number of points in the boundary should be O(n) less than the total number of points. (The boundary is a one-dimensional line bounding a 2-Dimensional area.) – Charles Bretana Oct 24 '09 at 16:51
0

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.
Jason S
  • 184,598
  • 164
  • 608
  • 970