-----------

Computational Geometry Seminar

Wednesday, March 8th, 2006, 16:10-18:00

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

Colored Range Searching via Matrix Multiplication

Elad Verbin, Tel Aviv University

Abstract:

In a Colored Range Searching Problem, one is given a set of points, each point colored in one of c colors, and a set of hypercubes, each colored in one of the same c colors. The goal is to report all pairs of colors (c_1,c_2) such that a point of color c_1 is contained in a cube of color c_2. The same question can be asked for halfspaces, triangles, etc.

In a Sparse Rectangular Matrix Multiplication Problem, one is given a matrix A with n rows and at most m non-zero entries (the number of columns is not significant). The goal is to compute A*A^T, i.e. the product of A and its transpose.

It is relatively easy to see that the Colored Range Searching Problem is harder than the Sparse Rectangular Matrix Multiplication Problem, in the sense that one can solve the latter using the former. In this talk we show that this relation goes both ways. In other words, we prove that the optimal time it takes to solve the former problem can be stated in terms of the optimal time it takes to solve the latter problem.

This is joint work with Haim Kaplan and Micha Sharir.