We present new results for three problems dealing with a set P of n convex constant-complexity fat polyhedra in 3-space. (i) We describe a data structure for vertical ray shooting in P that has O(log2 n) query time and uses O(n log2 n) storage. (ii) We give an algorithm to compute in O(n log3 n) time a depth order on P, if it exists. (iii) We give an algorithm to verify in O(n log4 n) time whether a given order on P is a valid depth order. All three results improve on previous results.
|Title of host publication||Proceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)|
|Publisher||Association for Computing Machinery, Inc|
|Publication status||Published - 2006|