Vertical Ray Shooting and Computing Depth Orders for Fat Objects
Mark de Berg, Chris Gray · SIAM Journal on Computing · 2008
We present new results for three problems dealing with a set $\mathcal{P}$ of n convex constant-complexity fat polyhedra in 3-space. (i) We describe a data structure for vertical ray shooting in $\mathcal{P}$ that has $O(\log^2 n)$ query time and uses $O(n\log^2 n)$ storage. (ii) We give an algorithm to compute in $O(n\log^3 n)$ time a depth order on $\mathcal{P}$ if it exists. (iii) We give an algorithm to verify in $O(n\log^3 n)$ time whether a given order on $\mathcal{P}$ is a valid depth order. All three results improve on previous results.