RAY SHOOTING AMIDST SPHERES IN 3 DIMENSIONS AND RELATED PROBLEMS

We consider the problem of ray shooting amidst spheres in 3-space: giv en n arbitrary (possibly intersecting) spheres in 3-space and any epsi lon > 0, we show how to preprocess the spheres in time O(n(3+epsilon)) into a data structure of size O(n(3+epsilon)) SO that any ray shootin g query can be answered in time O(n(epsilon)). Our result improves pre vious techniques (see [P. K. Agarwal, L. Guibas, M. Pellegrini, and M. Sharir, ''Ray shooting amidst spheres,'' unpublished note] and [P. K. Agarwal and J. Matousek, Discrete Comput. Geom., 11 (1994), pp. 393-4 18]), where roughly O(n(4)) storage was required to support fast queri es. Our result shows that ray shooting amidst spheres has complexity c omparable with that of ray shooting amidst planes in 3-space. Our tech nique applies to more general (convex) objects in 3-space, and we also discuss these extensions.