Closest pair of points between two sets, in 2D

I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as possible. How efficiently can this be done? Can it be done in $O(n \log n)$ time, where $n = |S|+|T|$?

I know that if I'm given a single set $S$, then it's possible to find the closest pair of points $s,s' \in S$ in $O(n \log n)$ time using a standard divide-and-conquer algorithm. However, that algorithm doesn't seem to generalize to the case of two sets, because there's no connection between the distance between the two closest points within $S$ or $T$ vs. the distance between the two closest points across those sets.

I thought of storing the set $T$ in a $k$-d tree, then for each $s \in S$, using a nearest-neighbor query to find the closest point in $T$ to $s$. However, the worst-case running time of this might be as bad as $O(n^2)$ time. There are results saying that if the points of $T$ are randomly distributed, then the expected running time for each query is $O(\log n)$, so we'd obtain an algorithm with expected running time $O(n \log n)$ if we were guaranteed that the points are randomly distributed -- but I'm looking for an algorithm that will work for any collection of points (not necessarily randomly distributed).

Motivation: An efficient algorithm would be useful for this other question.

Yes, this can be $O(n \log n)$ time. Build a Voronoi diagram for $T$. Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in. The center of that cell is the point $t \in T$ that is closest to $s$.

You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log n)$ time, so the total running time is $O(n \log n)$ time.

StackExchange Computer Science Q#65573, answer score: 13