ON RAY SHOOTING IN CONVEX POLYTOPES

Let P be a convex polytope with n facets in the Euclidean space of a ( small) fixed dimension d. We consider the membership problem for P (gi ven a query point, decide whether it lies in P) and the ray shooting p roblem in P (given a query ray originating inside P, determine the fir st facet of P hit by it). It was shown in [AM2] that a data structure for the membership problem satisfying certain mild assumptions can als o be used for the ray shooting problem, with a logarithmic overhead in query time, Here we show that some specific data structures for the m embership problem can be used for ray shooting in a more direct way, r educing the overhead in the query time and eliminating the use of para metric search. We also describe an improved static solution for the me mbership problem, approaching the conjectured lower bounds more tightl y.