Alladi Ramakrishnan Hall

Algorithms and Data Structures for Geometric Intersection Query Problems

Rahul Saladi

University of Illinois Urbana-Champaign.

Geometric intersection queries (GIQ) a.k.a. range-searching queries have been very well studied
by the computational geometry community and the database community. In a GIQ problem, the
user is not interested in the entire input geometric dataset, but only in a small subset of it and
requests an informative summary of that small subset of data. The goal is to organize the data
into a data structure which occupies a small amount of space and yet responds to any user query in real-time.

In this talk, I will try to give an overview of the contributions I have made along with my co-authors
on some of the GIQ problems. The focus will be on (a) top-k queries which are very popular in the
database community, and (b) point location and rectangle stabbing queries which are fundamental
problems in the computational geometry community.