Find all points in a sphere of radius r around an arbitrary coordinate

Question

I am looking for an efficient algorithm that for a space with a known height, width and length, given a fixed radius R, and a list of points N with three-dimensional coordinates in this space will find all points within a fixed radius R of an arbitrary point on the grid. This request will be executed many times with different points, so an expensive preprocessing / sorting step in exchange for quick requests may be worth it. This is a slightly narrow application step I'm working on, so any time I can cut off from it is useful

Things I've tried so far:

- naive algorithm, iterating over all points and calculating the distance

. Place space in a grid with cubes of length R and place dots in them. Thus, for each point I should always request immediate neighboring buckets. It speeds up significantly

- I tried to use the Manhattan distance as a heuristic. That is, within the buckets, before calculating the distance to any point, use the distance in Manhattan to filter out those that cannot be in radius R (that is, those with Manhattan distance <= sqrt (3) * P). I thought this would offer acceleration, since it only needs to add instead of multiplication, but it actually slowed down the program a bit

EDIT: to compare distances, I use the square of the distances to eliminate the need to use the sqrt function.

Obviously, there will be some restriction on how much I can speed this up, but I could use any suggestions on things to try now.

Not that it probably mattered at the algorithmic level, but I work on C.

Answer 1

You can benefit from storing your points in a kd tree with three dimensions. This will give you a search in O (log n), amortized time.

Answer 2

Do not compare the radius, compare the square of the radius. The reason is that if the distance between two points is less than R , then the square of the distance is less than R^2 .

Thus, when you use the distance formula, you do not need to calculate the square root, which is a very expensive operation.

Answer 3

I would recommend using either the KD tree or the z-curve: http://en.wikipedia.org/wiki/Z-order_%28curve%29

Answer 4

How about a binary indexed tree ? (See Topcoder Guide). It can be expanded to n Dimensions and easier to code.

Answer 5

The Nicolas Brodu NEIGHAND library does what you want by improving the bin-lattice algorithm.

More information can be found in his article: Indexing the Request Area for Neighborhood Requests

Answer 6

[Perhaps I do not understand the question. I find it difficult to parse the problem statement.]

In the old days, it was often useful to develop this type of algorithm with "early outputs" that conduct tests to avoid a more expensive calculation. In modern processors, dropping branch prediction is often very expensive, and those early tests can actually be more expensive than a complete calculation. (The only way to know for sure is to measure.)

In this case, the calculation is quite simple, so it’s better to avoid creating a data structure or do some smart early checks, and instead try to optimize, vectorize and parallelize to get the necessary bandwidth.

For point P (x, y, z) and sphere S (x_s, y_s, z_s, radius), the membership criterion:

 (x - x_s)^2 + (x - y_s)^2 + (z - z_s)^2 < radius^2 

where radius^2 can be pre-calculated once for all points in the query (avoiding square-root calculations). These calculations are independent, you can calculate it for several points in parallel. With something like SSE, you could probably do four at a time. And if you have a lot of points for testing, you can split the list and parallelize the work across several cores.