Better Data Structures for Colored Orthogonal Range Reporting

Range searching on categorical, or "colored", data has been studied extensively for over two decades. In this paper, we obtain the current best results for perhaps the most basic, and most often studied, version of the geometric problem: colored orthogonal range reporting.

Given n colored points in two-dimensional space [U ] 2 , we present a data structure with O(n log 3/4+ε n) space, for an arbitrarily small constant ε > 0, so that all k distinct colors in any axis-aligned query rectangle can be reported in (optimal) O(log log U + k) time; this is the first method to break the O(n log n) space barrier.

In three dimensions, we present a data structure with O(n log 9/5+ε n) space and O(log n/ log log n + k) time; this improves the previous space bound of O(n log 4 n).