3d - which data structure is appropriate to query "all points within distance d from point p"

Question

I have a 3D pointcloud and I'd like to efficiently query all points within distance d from an arbitrary point p (which is not necessarily part of the stored pointcloud)

The query would look something like

Pointcloud getAllPoints(Point p, float d);

what accelerationstructure would be appropriate for this? A range-tree seems to be appropriate only for querying rectangular volumes, not sphere volumes (of course I could query the boundingbox of the sphere and then sort out all vertices that have larger distance than d - but maybe there is a better way to do this??)

thanks!

according to Novelocrats suggestion, I try to define the desired functions of the structure:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

Usually, after n queries, the points get displaced and a few (not many!) insertions and deletions are made. the offset vectors are very small compared to the boundingbox of all points

Answer 1

What you want is a structure that decomposes space so that particular regions can be found efficiently. A properly decomposed octree or kD-tree should allow you to do this well, as you would only 'open' the section of the tree containing your point p to look for points nearby. This should let you put a fairly low asymptotic bound on how many extra points you need to compare distance to (knowing that below some level of decomposition, all points are close enough). Unfortunately, I don't know the literature in this area well enough to give more detailed pointers. My encounter with these things is from the Barnes-Hut n-Body simulation algorithm.

Here's another question closely related to this one. And another. And a third, mentioning a data structure (Hilbert R-Trees) that I hadn't previously heard of.