On range reporting, ray shooting and k -level construction
Edgar A. Ramos · 1999
IntroductionWe describe the following data structures.For halfspace range reporting, in S-space using expected preprocessing time O(n log n), worst-case storage O(n log log n) and worst-case reporting time O(log n + k), where n is the number of data points and k the number of points reported; in d-space, with d even, using worst-case preprocessing time O(nlogn), storage O(n) and reporting time O(n1-1/Ld/21 log'n + k), where c is a constant.For ray shooting in a convex polytope in d-space determined by n facets, using deterministic preprocessing time 0( (n/ log n)ldi2J log' n) and storage 0( (n/ log n) ld/2J2c'os' ") and with query time O(logn).For ray shooting in arbitrary direction amon n hyperplanes using preprocessing O(nd/logld/2 n) and query time O(logn).B We also describe a randomized algorithm for constructing the k-level of n planes in S-space.In the case of planes dual to points in convex position, in which the size of the k-level is O(nk), the algorithm uses nearly optimal expected time O(n logn + nk2c'0g* ").By a standard geometric transformation the same time bound applies for the construction of the k-order Voronoi diagram of n sites in the plane.