# Bichromatic all nearest neighbors

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 lists
• In 2D it is easy to solve with a Voronoi diagram
• For 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?