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.

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

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.


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.


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.