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.