# 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>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.

• I believe the usual approach is to put such point sets into trees; a 3D version of the quadtree might work. – reinierpost Feb 13 '14 at 10:49