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.