What are fast algorithms/data structures for querying near points on the surface of a sphere?

Question

I want data structure with the following methods:

insert :: Point3D -> a -> SphereMap a -> SphereMap a
remove :: Point3D -> a -> SphereMap a -> SphereMap a
query :: Float -> Point3D -> SphereMap a -> [a]

Where insert and remove add 3D-indexed values to the data structure, query receives an angle and a point, and returns a list of all values that are within that angular distance of the point with respect to origin (0,0,0).

What kinds of data-structures exist for such requirements?

Answer 1

The usual approach is to use either quad-trees for 2d data or octrees for 3d data. A quad-tree splits the area of concern into 4 quadrants based on X and Y thresholds. For each quadrant, if it contains zero or 1 points then end, otherwise subdivide the quadrant into sub-quadrants and repeat. This gives you a tree of points in which the tree geometry reflects neigbouring geometry. You can then write an algorithm to traverse the tree finding all the quadrants that intersect the radius of your search. Oct-trees are the same in 3 dimensions,splitting by X, Y and Z. See http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374 for details.