Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

AbstractWe present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2+ε) storage and preprocessing time, and queries can be answered in O(log2n) time. A trade-off between storage and query time is also possible: for any m with n<m<n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that queries take O((n/m)log2n) time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with n<m