# 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)?

• The trivial brute force algorithm would take $O( |R| |B| )$
• 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))$