title: Find all points in sphere of radius r around arbitrary coordinate
body: <p>I'm looking for an efficient algorithm that for a space with known height, width and length, given a fixed radius R, and a list of points N, with 3-dimensional coordinates in that space, will find all the points within a fixed radius R of an arbitrary point on the grid. This query will be done many times with different points, so an expensive pre-processing/sorting step, in exchange for quick queries may be worth it. This is a bit of a bottleneck step of an application I'm working on, so any time I can cut off of it is useful</p>
  
  <p>Things I have tried so far:</p>
  
  <p>-The naive algorithm, iterate over all points and calculate distance</p>
  
  <p>-Divide the space into a grid with cubes of length R, and put the points into these. That way, for each point, I only have to ever query the immediate neighboring buckets. This has a significant speedup</p>
  
  <p>-I've tried using the manhattan distance as a heuristic. That is, within the buckets, before calculating a distance to any point, use the manhattan distance to filter out those that can't possibly be within radius R (that is, those with a manhattan distance of &lt;= sqrt(3)*R). I thought this would offer a speedup, as it only needs addition instead of multiplication, but it actually slowed the program down by a little bit</p>
  
  <p>EDIT: To compare the distances, I use the squared distance to eliminate having to use a sqrt function.</p>
  
  <p>Obviously, there will be some limit on how much I can speed this up, but I could use any suggestions on things to try now.</p>
  
  <p>Not that it probably matters on the algorithmic level, but I'm working in C.</p>