  We study range-searching for colored objects, where one has to count
(approximately) the number of colors present in a query range. The problems
studied mostly involve orthogonal range-searching in two and three dimensions,
and the dual setting of rectangle stabbing by points. We present optimal and
near-optimal solutions for these problems. Most of the results are obtained via
reductions to the approximate uncolored version, and improved data-structures
for them. An additional contribution of this work is the introduction of nested
shallow cuttings.
