We describe a data structure for vertical ray shooting in a set of n convex fat polyhedra of constant complexity in 3-space. The structure has O(log2 n) query time, and it uses O(n log3 n(log log n)2) storage. It can also be used for fat objects with curved boundaries, at the cost of a small increase in storage.
展开▼
