I need to find all points within a given radius of a certain point in euclidean 2D and 3D spaces. The points are updated fairly often (but most commonly are just moved by a limited distance). The point distributions are likely to be very non-uniform in my application. There's a limit to the resolution I need, I'd rather trade resolution for performance (at least if I can over-estimate rather than under-estimate returned point sets).

I know I could use spatial hashed grids or quad/octrees for this. Unfortunately the Wikipedia article for fixed-radius near neighbor search is a stub, and googling gives me very specific results rather than an overview, so my quick rush to gain an overview ended there. ^^ I wonder if someone else has a better idea than spatial grids or oct/quadtrees - if you can give me names of algorithm/data structures that work in your experience, that will save me a couple of hours and I will be very happy.

Edit: Oh and if the data struture can be updated concurrently it's a plus.

I haven't written any code yet (for the search, the application already exists). I understand quad/octrees, but I doubt they're the best option given the number of updates I will be doing from multiple concurrent tasks. Let's say the application is "air traffic control" for illustrative purposes (not really true as the objects will be clustering up more than aircraft).

I will use spatial hashes as a baseline I think, as I suspect they will perform comparatively well and are easy to implement. Then I'll see if any other solutions I try outperform it.

Thanks, I'll check it out!

That concern wasn't for quadtrees specifically, rather it was for any other algorithms proposed for which it might be applicable. But I thank both you and Alvaro for stating your confusion, it means I will try to be more clear next time. I'm not as mathematically minded as I wish I were, unfortunately, so I sometimes come off as logically incoherent in the finer details.

You might also look into an R tree. If you're doing a lot of modifications to the structure at run time, an R tree will outperform a kd tree. A bit more complex though.

Thanks for both suggestions. Thought KD trees were slow to update but maybe it will work. Like you note, it's hard to tell what will work best in practice so I'll have to try a couple of different solutions.