Closest pair algorithm for comparing points from 2 different arrays

Question

I would like to compare the points from one array to the points from another array and find the closest pair. Till now whatever I have come across is with a single array. I do not want to compare the points from the same array. The brute force algorithm works but it is too slow. Is there an algorithm or implementation for this using divide and conquer method?

EDIT 1 : A point is defined as the pair (latitude, longitude) on the earth's surface.

Answer 1

You can build a kd-tree for the first array of points and then find the closest point from the first array for each point of the second array using this tree. It works in O(n log n) on avarage(n is the size of the largest of two arrays). To use kd-tree, you can convert your initial coordinates into 3D-space coordinates.