He aquí un $O(n \log n)$ algoritmo que funciona para todos los posibles conjuntos de $A$$B$.
Deje $n = |A| + |B|$.
Esta pregunta se ha hecho en otras plataformas (aquí o aquí), pero ninguno de ellos dar respuestas satisfactorias (...al menos para mí. No puedo comprobar que funcionan en la reclamación del tiempo para todas las posibles entradas. Por ejemplo, el uso de KD árbol no garantiza $O(n \log n)$ menos que los puntos son lo suficientemente aleatorio. La respuesta a la segunda vínculo es aún más malo).
Así que, aquí está una puramente $O(n \log n)$ algoritmo para resolver esto! Buena cosa que haya hecho esta pregunta en matemáticas foro, porque a pesar de ser teóricamente interesante, yo no quiero implementarlo...
En primer lugar, construir el diagrama de voronoi $V_A$ de todos los puntos en $A$. Para cada punto de $b_j \in B$, hallar la celda de voronoi $v_i \in V_A$ que contiene el punto-por la propiedad de un diagrama de voronoi, sabemos que $a_i$ es el vecino más cercano de $b_j$. Por lo tanto, al hacer esto para todos los puntos en $B$ y tomando el mínimo, se obtiene la par con un mínimo de distancia.
Claro, eso suponiendo que somos capaces de encontrar la celda $v_i$ por cada punto de $b_i$ rápidamente. Para hacerlo de forma rápida, podemos utilizar el barrido de la línea de algoritmo: barrido de todos los puntos en el diagrama de voronoi $V_A$ y los puntos de $B$. Podemos almacenar la actual partición del espacio mediante un árbol binario de modo que cada vez que el barrido de la línea se encuentra un punto de $b_i \in B$, somos capaces de encontrar el diagrama de voronoi que contengan $b_i$$O(\log n)$. Siempre que encontremos un punto de $a_i \in A$, podemos actualizar el árbol de la estructura del diagrama de voronoi. Este barrido de la línea es bastante análoga a la de la línea de barrido se realiza para "buscar líneas de intersección" algoritmo.
Desde la construcción de un diagrama de voronoi tarda $O(n \log n)$ a tiempo, todo el procedimiento se $O(n \log n)$.
