Find all neighbors at a certain distance, in 3 dimensions 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&gt;0$, find all $i$ such that $|\mathbf{r}_{i} - \mathbf{p}| &lt; 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} &gt; d^2 \implies |\mathbf{r}_{i} - \mathbf{p}|^2 &gt; 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} &lt;= 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}| &lt; 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.
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.