Vertical ray shooting for fat objects
Mark de Berg · 2005
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.