#### 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.

Done