Maximum distance in a set of points

This topic is 4843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Given a set of points in two or three dimensions, is there a good fast way to find the maximum distance between two points in the set, short of the n^2 / 2 method of taking the distance between each pair?

Share on other sites
Well, just a few ideas:

1) Spacially divide the points somehow and use the larger divisions of points to search for the furthest set. Not quite sure how I would go about this.

2) Use the properties of a triangle to inteliggently prune the possibilities quickly. Find all the distances from one point to all the others. The maximum is obviously the best candidate so far, but we can do more with this information. Find every combination of pairs of points such that the distances to each from our 'special' point is less than the maximum we have so far. Due to the properties fo a triangle, we know that the distance between the two must also be less than the current max.

That should be able to prune the possibilities down. Best case, there is a lot of clumping in the points and this will knock out those points. Even in the worst case aq good number of connections will be pruned.

Continue with the other points.

Share on other sites
This is a well-known problem; you want to find the diameter of a set of points. The generally accepted solution is to compute the convex hull of the set of points (which is O(n lg h) in the worst case, O(n) in the average case), then examine each pair of antipodal points (which is O(n)). The points farthest apart form the diameter.

The best algorithm to use for two or three dimensions is quickhull. It's O(n) in the average case and O(n2) in the worst case where all points lie on a circle, but using Chan's paper (see below) you'll get the O(n lg h) worst-case performance described above. Chan's improvements do not improve the average case. Additional optimizations and refinements exist for higher-order dimensions.

If it is important only that you find the approximate diameter rather than the actual diameter, there are more efficient algorithms that can do it very quickly by making intelligent pruning decisions, giving you near O(lg n) performance. I don't know those off the top of my head, but a Google or Citeseer search would probably turn up some results.

Graham's scan is much simpler to implement than quickhull (with Chan's improvements), but it is O(n lg n) in the worst case rather than O(n lg h).

References:

T. M. Chan and J. Snoeyink and C. K. Yap, "Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d {Voronoi} diagrams," Discrete Comput. Geom., 18, 1997, p. 433-454.

Share on other sites
Thanks people, looks like just what I needed. Just a quick question, kSquared; what is the 'h' that appears in your orders? I don't see it in any of the papers you linked.

Share on other sites
'h' is the number of points that end up on the convex hull.

Share on other sites
Quote:
 Original post by King of MenThanks people, looks like just what I needed. Just a quick question, kSquared; what is the 'h' that appears in your orders? I don't see it in any of the papers you linked.

As FatSimon said, h is the number of points that wind up being on the hull (h <= n, of course, and h is typically much smaller than n for random points). Quickhull is is in the class of output-sensitive algorithms, which means that its performance depends partially on the results. Output-sensitive algorithms can be somewhat tricky to analyze (you can't tell how much it's going to cost you until you do it), but luckily this is a fairly well-studied problem.

On another note, if you know ahead of time that the number of points you're testing is small (say, < 20), I'd consider brute-forcing it just for the simplicity, assuming that your performance isn't absolutely critical. A correct but slower algorithm is infinitely better than a fast algorithm that's wrong.

Share on other sites
Ah, now I see. So in the worst case h=n, which would be when there are no interior points - all the points are on a circle. But actually, thinking about it, this is one place in my code where optimising totally doesn't matter, because it's in initialisation. So I guess it'll be brute force after all. Still, I learned something.

:)

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 9
• 9
• 14
• 12
• 10
• Forum Statistics

• Total Topics
633271
• Total Posts
3011163
• Who's Online (See full list)

There are no registered users currently online

×