Ray shooting amidst spheres in three dimensions and related problems. - Mohaban, Shai (SIAM journal on computing.)
We consider the problem of ray shooting amidst spheres in 3-space: given n arbitrary (possibly intersecting) spheres in 3-space and any e > 0, we show how to preprocess the spheres in time O (n3+e) into a data structure of size O(n3+e) so that any ray-shooting query can be answered in time O (ne). Our result improves previous techniques, where roughly O (n4) storage was required to support fast queries. Our result shows that ray shooting amidst spheres has complexity comparable with that of ray shooting amidst planes in 3-space. Our technique applies to more general (convex) objects in 3-space, and we also discuss these extensions.