VERTICAL RAY SHOOTING AND COMPUTING DEPTH ORDERS FOR FAT OBJECTS.

We present new results for three problems dealing with a set P of n convex constant-complexity fat polyhedra in ³-space. (i) We describe a data structure for vertical ray shooting in P that has O(log² n) query time and uses O(n log² n) storage. (ii) We give an algorithm to compute in O(n log³ n) time a depth order on P if it exists. (iii) We give an algorithm to verify in O(n log³ n) time whether a given order on P is a valid depth order. All three results improve on previous results. [ABSTRACT FROM AUTHOR]