Algorithms and Data Structures for Geometric Intersection Query Problems

Title : Algorithms and Data Structures for Geometric Intersection Query Problems

Date : Monday, March 25, 2019

Time : 11:00 AM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract

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.

Biography of the speaker Rahul Saladi is currently a postdoc at Univ. of Illinois Urbana-Champaign (UIUC) hosted by Prof. Sariel Har-Peled and Prof. Timothy Chan. His research interests are in the field of geometric data structures and geometric approximation algorithms. He did his Ph.D. at Univ. of Minnesota where his adviser was Prof. Ravi Janardan, and did his B.Tech and Masters at IIIT-Hyderabad.

Host Faculty : Prof. Matthew Jacob