# Efficiently finding all (x,y,z) points within certain distance of point P

I am using Python, and I have a Pandas dataframe with hundreds of thousands, if not millions, of $(x,y,z)$ coordinates. I am looking to find an efficient method to index the original dataframe so that I'm only left with entries that are within some distance of a given point $P$ that's not necessarily in the set of coordinates.

The trivial, but surely most expensive, method is to construct a vector between each $(x,y,z)$ point and the point $P$, take the norm, and only keep those that are within the cutoff distance. For millions of points though, as I have to do it dozens of times, this seems terribly inefficient.

What are optimal but still somewhat intuitive methods to do this?

• A very simple modification which will speed up the calculation is to use the square of the norm, which will allow you to avoid calculating the square root of each distance. You might also get some speed up by initially filtering out any point which lies outside a cube. Mar 25, 2018 at 6:23
• There are different norms; some may be easier to calculate than others. It looks like you have in mind the Euclidean norm ||r||=sqrt(x^2+y^2+z^2). But maybe the overall algorithm would be fine using a norm like this ||r||=abs(x)+abs(y)+abs(z)? I.e. locating points within a certain size cube, not sphere centered at a given location. Mar 26, 2018 at 3:43
• Not in python but asked similar question long time back. scicomp.stackexchange.com/questions/5534/… Mar 27, 2018 at 14:55

You can use Morton keying to sort the coordinate locations by binning them into cubes of some specified size $d$. This is an $\mathcal{O}(N\log N)$ operation. Then, given any point P, you can use its Morton key to search only in a small number $(\mathcal{O}(1))$ of nearby boxes, bounded by your distance criterion. The search for each box is $\mathcal{O}(\log N)$.
• Using the same idea and consuming a bit more memory, you can actually improve the query time for finding a box to $O(1)$ by binning the data in a uniform grid and storing the boxes in a hash table (assuming that the data is spatially sparse enough to make a dense grid a bad approach). Mar 24, 2018 at 21:24