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

I need to get two points that have biggest distance between.

The easiest method is to compute distance between each of them, but that solution would have an quadratic complexity.

So i'm looking for any faster solution.

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.

To elaborate on rossom's answer:

1. 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
2. Start at a point, say A, and loop through the other points to find the one furthest from it, say B.
3. 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).