What is the fastest way to detect two points in 2D space with biggest distance between them?

How about: 1 Determine the convex hull of the set of points 2 Find the longest distance between points on the hull That should allow you to ignore all points not on the hull when checking for distance.

How about: 1 Determine the convex hull of the set of points. 2 Find the longest distance between points on the hull. That should allow you to ignore all points not on the hull when checking for distance.

This is a good solution but too hard to implement, I think. And Quadratic complexity isn't that bad. – McOmghall Aug 27 at 9:37 @McOmghall Too hard to implement?

Do more algorithms, man... and more programming... and more SO. – quasiverse Aug 27 at 9:40 I think this solution also has an n-square complexity as the basic solution (i. E finding distance between each two points) – suat Aug 27 at 9:41 @suat No because you can do a double traversal of the points in O(N) time.

– quasiverse Aug 27 at 9:43 @quasiverse I considered the operations to determine a convex hull. It is also possible that I am missing a point. – suat Aug 27 at 9:46.

The third post in this discussion gives a linear algorithm that requires the convex hull. Convex hull is O(n log h), where h = number of points on the hull, so that's the minimum.

To elaborate on rossom's answer: Find the convex hull of the points which can be found in O(n log n) time with an algorithm like Graham's Scan or O(n log h) time with other algorithm's which I assume are harder to implement Start at a point, say A, and loop through the other points to find the one furthest from it, say B. Advance A to the next point and advance B until it is furthest from A again. If this distance is larger than the one in part 2, store it as the largest.

Repeat until you have looped through all points A in the set Parts 2 and 3 take amortized O(n) time and therefore the overall algorithm takes O(n log n) or O(n log h) time depending on how much time you can be bothered spending on implementing convex hull. This is great and all but if you only have a few thousand points (like you said), O(n^2) should work fine (unless you're executing it many times).

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.