Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$. For each $x_i \in X$, I need to find all $y \in Y$ such that the distance between $x_i$ and $y$ is less than a (fixed) radius $R$. That is, for each $x_i$, I want the set $E_i = \{y \in Y: \|x_i-y\|\ \leq R\}$.

Now this looks to me like a nearest-neighbors type problem just with two different sets of points. If I'm correct, usually something like an R-tree or kd-tree is good for finding nearest neighbors within a single set $X$. But this seems a bit different. I could naively just iterate through $X$ and find the $y_j \in Y$ such that $\|x_i-y_j\| \leq R.$ and I suppose store that in a gigantic array, but this seems like the worst possible method. On the bright side, this is at least embarassingly parallel so there is that at least.

Any suggestions would be greatly appreciated and I apologize if this is a trivial question (I'm not a computer scientist!) Also, if this is the incorrect place to ask such a question, please let me know. If the question is unclear or requires additional information, just let me know. Thanks!

  • 1
    $\begingroup$ Why do you consider using a R-tree or a kd-tree the worst possible method? One natural thing to do is to store $Y$ in the k-d tree and then iterate through $X$ to perform near-neighbor search once per element of $X$; why do you conclude that is the worst possible method? $\endgroup$ – D.W. Mar 3 '15 at 12:02

Sort the big set $Y$ into a regular grid, then for any query point $x_i,$ find its cell and you only have to check the adjacent cells to determine $E_i$ very quickly. For sorting, indeed, some parallel algorithms are faster than others, see this poster for an overview and example of using fast GPU radix and count sort.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.