Jump to content
  • Advertisement
Sign in to follow this  
King of Men

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by King of Men
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.

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 this post


Link to post
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.

:)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!