Good data structure for finding all points in one set a distance from each point in another set

Question

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!

Answer 1

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.