Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance between $u$ and $v$ (may be considered as points or vectors). Also what's the most efficient algorithm to determine $u$ and $v$ (not necessarily unique) such that $d(u,v)$ is minimized?
So minimizing $d(u,v)$ is pretty much the same as minimizing $[d(u,v)]^2$, which can be written using the distance formula. But I couldn't think of anything better than a brute-force $O(|A||B|)$ solution (where $|A|$ denotes the cardinality of $A$) which tries every possible $u\in A,v\in B$.
Best Answer
Here's an $O(n \log n)$ algorithm that works for all possible sets $A$ and $B$.
Let $n = |A| + |B|$.
This question has been asked in other platforms (here or here), but none of them give satisfactory answers (...at least to me. I cannot verify that they work in the claimed time for all possible inputs. For example, using KD tree does not guarantee $O(n \log n)$ unless the points are sufficiently random. The answer to second link is even more evil).
So, here's a purely $O(n \log n)$ algorithm to solve this! Good thing you asked this in a math forum, because despite being theoretically interesting, I wouldn't want to implement it...
First, construct the voronoi diagram $V_A$ of all the points in $A$. For each point $b_j \in B$, find the voronoi cell $v_i \in V_A$ that contains the point -- by the property of a voronoi diagram, we know that $a_i$ is the closest neighbor of $b_j$. Thus, by doing this for all points in $B$ and taking the minimum, we get the pair with minimum distance.
Of course, that's assuming we are able to find the cell $v_i$ for each point $b_i$ quickly. To do it quickly, we use the sweep line algorithm: sweep all the points in the voronoi diagram $V_A$ and the points $B$. We store the current partition of the space using a binary tree so that whenever the sweep line encounters a point $b_i \in B$, we are able to find the voronoi diagram containing $b_i$ in $O(\log n)$. Whenever we encounter a point $a_i \in A$, we update the tree from the structure of the voronoi diagram. This sweep line is rather analogous to the sweep line performed for the "find intersecting lines" algorithm.
Since construction of a voronoi diagram takes $O(n \log n)$ time, the entire procedure is $O(n \log n)$.