4
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.