Research Projects

Computational geometry deals with the design and analysis of problems which are geometric in nature. Rigorous mathematical analysis (of aspects such as running time, space and query time, approximation factor) has been the strength of the computational geometry community. The explosion of the volume of data being generated these days implies that ``traditional'' queries are not informative enough for the user and in many cases the output of these queries are overwhelming for the user. There is an urgent need to formulate novel queries which can extract interesting insights from the data and summarize them in a meaningful way for the user. A large percentage of the data being generated these days is ``geometric'', for e.g., Google Maps, Spatial Databases, Robotics and Internet Data. Also, new applications such as smartphones, ad auctions and social media platforms give rise to challenging geometric problems if we consider the business locations of the advertisers or the locations of the users on social media. Finally, the pandemic (i.e., COVID) in the last couple of years has led to the need to design geometric data structures which can quickly identify the "hotspots'' with maximum affected patients, or find the number of affected patients in one's neighbourhood (such as Aarogya setu app). The PI is an expert in the field of designing efficient data structures for geometric data. Along with his students, the plan of the PI is to design data structures and algorithms for classical problems in the field, and for modern problems which arise from big geometric data and newer applications. Recently, the PI has also explored problems at the intersection of computational geometry and machine learning. The goal is to study problems which are geometric in nature and would require expertise in both computational geometry and machine learning. The solutions to these problems would benefit machine learning applications. Going forward, one of the research themes which excites the PI is the design of routing algorithms for problems involving drones. The computational geometry community is yet to actively take up research on the challenging problems arising in coordination and routing of drones. The study of drones will hugely benefit from PIs expertise in theoretical computer science. Some interesting problems include (a) designing scheduling algorithms for dispatching packages from a warehouse using drones, and (b) delivering packages in a city using a combination of trucks and drones, where the drones are launched from the trucks to do the last-mile delivery.