Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and
spatial databases. Given a set of geometric objects, a typical range query asks for reporting all the objects that intersect
a query object. However in many applications, including databases and network routing, input objects are partitioned into
categories and a query asks for reporting the set of categories of objects that intersect a query object. Moreover in many
such applications, objects lie on a grid. We abstract the category of an object by associating a color with each object. In
this paper, we present efficient data structures for solving the colored range-searching and colored point-enclosure problem
on U x U grid. Our data structures use near- linear space and answer a query in O(log log U +k) time, where k is the output size. As far as we know, this is the first result on colored range-searching for objects lying on a grid.
Research by the first two authors is supported by NSF under grants CCR-00-86013 EIA-98-70724, EIA-01-31905, and CCR-97-32787,
and by a grant from the U.S.- Israel Binational Science Foundation. Part of this work was done when the second author was
visiting the third author at DIMACS.