This award supports the US-India cooperative research entitled Geometric Query-retrieval Problems on Aggregated Data. Professors Ravi Janardan, University of Minnesota-Twin Cities and Prosenjit Gupta, International Institute of Information Technology (IIIT), Hyderabad will investigate the design of efficient algorithms and data structures for various query-retrieval problems defined on geometric objects that are aggregated in disjoint groups. The goal is to preprocess these groups into a data structure so that useful questions about the groups, relative to a query object, can be answered efficiently. The research addresses algorithm design and analysis as well as software development and testing on application-specific data. Problems involving aggregated geometric data arise in diverse applications such as VLSI (Very Large Silicon Integration) layout verification, retrieval of data from spatial databases, facilities location, sensor networks, and network traffic analysis.
Scope: This project has international implications and mutual benefits expected for senior scientists, graduate students and undergraduates at both institutions. The investigators have a 12-year history of successful collaboration that has thus far resulted in the publication of nearly two-dozen refereed journal and conference papers. Gupta completed his Ph.D. in 1995 under Janardan's supervision at the University of Minnesota. The proposed work represents a new research direction for them in an area in which they both have significant academic and industrial expertise. The project will provide an opportunity for graduate students to collaborate across geographic and cultural boundaries; it will also encourage undergraduate participation in the small, self-contained software development experiments, which may be incorporated in applied computational geometry courses. The findings of this research will be broadly disseminated in scientific journals.
