Here is another thought for a possible fast approximation:
1. Calculate the arithmetic mean of the points and call it cp.
2. Order the points by their angle relative to cp as the origin.
3. Iterate through the points and find the point that is closest to 180 deg away from the point under consideration.
4. Find the distance between the points and if it is greater than the previous pair then set those points as the new best choice.
5. Run through half the list that way and return the result.
This algorithm would eliminate two points with every iteration and exploits the general observation that the farthest points are probably going to be fairly opposite the arithmetic mean point. Guess I better figure it out