Find all nearest points

Question

I have two sets:
$$P = \{p_1, p_2, ..., p_n\}$$ $$Q = \{q_1, q_2, ..., q_m\}$$

For each $p_i$ point I need to find all nearest points in $Q$.
I.e.,

$$p_i \rightarrow \{ q_{i_1}, q_{i_2}, ..., q_{i_k} \}, 1 \leq i \leq n$$

where $d(p_i, q_{i_j}) = min\{d(p_i, q_l) : q_l \in Q\}$.

I'm searching for the fastest algorithm to do this.
I'm working in two-dimensional euclidean space.
Would using k-D tree be efficient for this case?
And another question,we can treat this problem as $n$ independent problems, and for each point from $P$ find nearest points in $Q$, but in wikipedia article, in All nearest neighbors section it's written that n improved strategy would be an algorithm that exploits the information redundancy between these $n$ queries to produce a more efficient search. Where can I find such algorithm(any links maybe)?

Thanks in advance.

Answer 1

Here is a somewhat efficient approach:

1. Build a matrix $P$ of distances, $P_{ij} = P_{ji} = d(p_i, p_j)$
2. Keep an array $d_i = \min_{q\in Q} d(p_i, q)$ and an array of lists
   $Q_i = \{q\in Q \mid d(p_i,q) = d_i\}$. We'll build these on-the-fly
3. For $i = 1$ perform the normal search.
4. For each $i \ge 2$:
   
   1. Find $\bar d = \min_{j = 1}^{i-1} P_{ij} + d_j$ and populate $d_i = \bar d$, $Q_i = Q_j$ with the minimizing $j$
   2. For each $q\in Q\setminus Q_i$ check if $d(p_i, q) \le d_i$
      • If equal, add $q$ to $Q_i$
      • If smaller, update $d_j$ and set $Q_j = \{q\}$ (won't happen too often)
      • If larger, do nothing

This will work especially good if some $p$ are clustered together so that they have the same nearest neighbors. If they are all random, it will at least help migitate some re-initialisations of the set $Q_i$ (wich should be the most expensive of all operations)