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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.