Range Queries on Grids

John Howat

We describe some data structures due to Overmars (1988) that solve the range searching problem when input points and query points are restricted to the set {0,1,...,U-1} x {0,1,...,U-1}, i.e., a U by U grid. Queries include dominance reporting queries, half-infinite queries, and orthogonal queries. The query time O(log log U + k) can be achieved for each of these cases, where k is the number of points in the query range; the first two query ranges use O(n) space and the last uses O(n log n) space, where n is the number of input points.