ray shooting in convex polytopes
Let H be a set of n halfspaces in E d (where the dimension d ? 4 is fixed), and P ( H ) the convex polytope defined as their intersection. We show that P ( H ) can be preprocessed in time and space O ( n [ d /2] /(log n ) [ d /2]-&egr; ) (for any fixed &egr; > 0) so that ray shooting queries with rays starting in P ( H ) can be answered in time O (log n ). This improves previous bounds by obtaining optimal query time and by improving the product Q ( n ) S ( n ) 1/[ d /2] ( Q ( n ) and S ( n ) denoting query time and storage of a data structure for this problem) to O ( n (log n ) &egr; ) for an arbitrarily small &egr; > 0. By a well known lifting transformation, the results imply the same bounds for nearest (or furthest) neighbor queries in space of one dimension lower, which is an improvement in itself. We furthermore show that a structure for the ray shooting problem can be dynamically maintained under a sequence of random insertions, using the history of the maintenance process for the polytope as a point location data structure. The expected update time is O ( m [ d /2]-1 (log m ) O (1) ), the query time for ray shooting queries is O (log 2 m ) with high probability, where m is the current number of points.
intersection process timing space log queries queries optimality product storage data structures structure sequence randomization histories maintenance point locatability update probability query