-----------

Computational Geometry Seminar

Wednesday, May 10th, 2006, 16:10-18:00

Room 309
Schreiber Building
-----------

Counting Colors in Boxes

Natan Rubin, Tel Aviv University

Abstract:

In the Generalized Orthogonal Range Counting problem, our goal is to preprocess a set of colored points in R^d for efficient colored orthogonal range counting queries. Each such query is of the form: Given a d-dimensional orthogonal box B, count the number of different colors of the points in B.
We present a unified approach for arbitrary dimension d. Applying a certain geometric transformation on the input, we reduce the problem to standard orthogonal range counting. The resulting data structure supports colored range queries in time O(polylog(n)), and has space and preprocessing complexity of O(n^d polylog(n)).
Moreover, if our query boxes are orthants, that is they are semi-unbounded in each of the d coordinates, we can do better. In this case colored range counting queries can be answered in time O(polylog(n)), using a data structure with space and preprocessing complexity of only O(n^floor(d/2) polylog(n)).
In the plane, we can reduce the storage to O(n^{1.186}), at the cost of increasing the query time to about O(n^{0.4}). This is achieved by using fast matrix multiplication in the preprocessing stage (similar in spirit, but quite different in details, from the recent offline algorithm of Kaplan et al. that has been presented by Elad Verbin at the seminar).

This is joint work with Haim Kaplan, Micha Sharir and Elad Verbin.