Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where:$f(r) = \text{argmin}_{b \in B} |r - b|$That is $f(r)$ is the closest point in $B$ to the point $r$ in $R$.What is the current fastest algorithm for computing $f$ in low to mid sized dimensions (for example d=3)?Some things I already know:The trivial brute force algorithm would take $O( |R| |B| )$In 1D the problem is easy, just merge two sorted listsIn 2D it is easy to solve with a Voronoi diagramFor non-bichromatic point sets the well-separated pair decomposition gives a solution in expected $O( c^d n \log(n))$ time.  Other solutions with similar performance are known.Finding the bichromatic closest pair is solvable in $O(2^d n \log(n))$A solution to this problem would be nice for shape matching/registration problems where one is repeatedly querying the same data set with some collection of points.  You could do something like incrementally call out to a nearest-neighbor subroutine for each point, but maybe you can do better amortizing over the cost of many queries?
Bichromatic all nearest neighbors
cg.comp geom