CODEWITHSUNDEEP
geometry2dcoordinates
Matt
Matt

Reputation: 2680

Max spread of multiple points

I have a group of points (x,y) and I need to find out the distance between the two that are farthest apart.

What is the most efficient way to find this?

Thanks

Upvotes: 1

Views: 191

Answers (1)

Jeff B
Jeff B

Reputation: 30099

Well, compairing every point against every other point is certainly not efficient.

The most efficient way involves finding the convex hull, which is the convex polygon (no angles > 180) surrounding all points.

After that, you find the farthest points on the hull, using antipodal pairs.

Algorithm described here:

http://www.seas.gwu.edu/~simhaweb/cs153/lectures/module1/module1.html

Upvotes: 3

Related Questions