Dynamic point location in fat hyperrectangles with integer coordinates.
John Iacono, Stefan Langerman · 2000
A data structure is presented for point location in a disjoint set of hyperrectangles in arbitrary fixed dimension with integer coordinates less than U . Point location query times are O(log log U ), in any dimension. The space and construction costs are dependent of the fatness of the hyperrectangles stored in the structure. The fatness of a hyperrectangle x is defined to be the size of the smallest set of hypercubes whose union is x. Given a set of n hyperrectangles with average fatness f the time to construct the data structure is O(fn log U log log U ) randomized, and the structure will use O(fn log log U ) space. Semidynamic and fully dynamic variants of this data structure are also presented. 1 Introduction Point location is one of the fundamental problems in computational geometry. In a point location problem, we are given a set of disjoint regions in space and are required to, given a query point, identify which region, if any, the point lies in. Point location data structures...