Given a set of n points, find two points which is furthest from each other. We need to use 2-approximation algorithm which means actually, we do not need to accurately find these two points, we just need to find a set of points that the distance between them is at least half of the furthest distance, the algorithm should run in linear time.
I have tried WSPD (well separated pair decomposition), but the construction of WSPD itself takes O(n*logn) time. So it's not a valid solution.
Surprisingly, the answer to this question is quite simple:
Randomly select a point from A, find the furthest point B from A, return the distance, and done!