I am stuck with a problem, and don't know where to start. I need to calculate the closest pair of points on the Earth using a divide and conquer method. I know I should calculate the orthodromic distance (or in other words the great-circle distance) but I don't know what to do. This calculation has to last at most nlog(n). I found this:
"The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:
Sort points according to their x-coordinates.
Split the set of points into two equal-sized subsets by a vertical line x=xmid.
Solve the problem recursively in the left and right subsets. This yields the left-side and right-side minimum distances dLmin and dRmin, respectively.
Find the minimal distance dLRmin among the set of pairs of points in which one point lies on the left of the dividing vertical and the other point lies to the right.
The final answer is the minimum among dLmin, dRmin, and dLRmin."
But this algorithm is for (x,y) points. I have to calculate (x,y,z) points on the Earth. I have to cin>> longitude and cin>>latitude. Then do some calculations and return two points with a minimal distance. What can I do? Do you have any suggestions or ideas?
PS. I'm not a native English speaker, so please don't correct my mistakes. I just want to communicate with you. I don't care, if there are mistakes.