MAE -- Neeraj Kumar

Date: 
Monday, December 4, 2017 - 3:30pm
Location: 
HFH 1132
Title: 
Geometric Shortest Paths
Speaker: 
Neeraj Kumar
Committee: 
Subhash Suri (chair), Divy Agrawal, Stefano Tessaro

Computing shortest paths is one of the most well studied and widely applicable algorithmic problems. We focus on the shortest path problem under geometric setting. That is, given a source s and a target t in the plane (2D), the goal is to compute a shortest path in presence of polygonal obstacles. In the classical version, these obstacles are considered 'impenetrable' and therefore a shortest path must avoid the region occupied by the obstacles. Our work deals with some interesting variants of this problem, for example what happens if we are allowed to go through (violate) some small number of obstacles? What if the obstacles have a probability of existence and so on.

    

    In this talk, we will start with a brief review of the classical shortest path problem and discuss some of the well-known techniques and results. In the latter half, we formulate our problem of computing shortest paths under violations and discuss some of our results. Finally, we conclude with some interesting open related problems.

Everyone welcome!