# 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. – andypea Mar 25 '18 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. – Maxim Umansky Mar 26 '18 at 3:43
• Not in python but asked similar question long time back. scicomp.stackexchange.com/questions/5534/… – Kaustubh Kaluskar Mar 27 '18 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). – Tyler Olsen Mar 24 '18 at 21:24
• Thank you. This will help with looking at how to best go about this. That being said, I tried what I thought was the "slow" approach and it's extremely fast as implemented in panas/numpy even for millions of points: np.sqrt(np.square(df[['x','y','z']]-P).sum(axis=1)). I then index the original dataframe using this. I'll see how this scales though. – Argon Mar 25 '18 at 0:37