Find all neighbors at a certain distance, in 3 dimensions

Question

I have two algorithms which I would like to implement:

First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, find all $i$ such that $|\mathbf{r}_{i} - \mathbf{p}| < d$.

Currently, I sort the list over the $x$-coordinate, so that if $x_{i}$ is the $x$-coordinate of $\mathbf{r}_{i}$, then $x_{1} \le x_{2} \le \cdots \le x_{n}$. Then I use the condition $(x_{i}-\mathbf{p}_{x})^{2} > d^2 \implies |\mathbf{r}_{i} - \mathbf{p}|^2 > d^{2}$. This allows me to filter the list by binary search. This leaves me with a subset $\{\mathbf{r}_{i}\}_{i=j_{1}}^{i=j_{2}}$ of the original list where for all $i \in [j_{1}, j_{2}]$, $(x_{i}-\mathbf{p}_{x})^{2} <= d^2$. Then I have to bite the bullet and do an explicit test on each one of these to see if $|\mathbf{r}_{i} - \mathbf{p}| < d$.

This algorithm strikes me as weird and not optimal; is there a better way?

Next: A related problem: Given a list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$ and a point $\mathbf{p} \in \mathbf{R}^{3}$, find $j \in [1,n]$ such that $d_{j}:=|\mathbf{r}_{j} - \mathbf{p}| = \min_{i} |\mathbf{r}_{i} - \mathbf{p}|$. Is there an efficient algorithm to find $j$?

Finally, I should note that any one-time ``sorting'' expense is tolerable, since this operation is repeated many times.

Answer 1

I recommend using a k-d tree or an octree to store the list of points. They support efficient nearest neighbor search.

If you need to update the list, look at R-trees, which allow your list to be dynamic: you can add or delete from the list and efficiently update the R-tree data structure.

Answer 2

The best solution for this problem would be to use a grid. Round every point down by 1/d and then when you query just search all buckets containing the query sphere.