Shortest paths among obstacles in the plane

演讲人: 王海涛 美国圣母大学
时间: 2011-09-19 15:30-2011-09-19 16:30
地点:FIT 1-222

Given a set of obstacles and two points s and t in the plane, a fundamental problem in computational geomtry is to find a shortest path from s to t that avoids the obstacles. The problem has been studied extensively. Various versions of this problem has been considered. We give efficient algorithms for the following two versions. The first version is the L1 polygonal version where all obstacles are polygonal and the length of a path is measured by L1 metric. The second version is the Euclidean curved version where the obstacles may have curved boundaries and the length of a path is measured by Euclidean metric.


Haitao Wang received his Ph.D in Computer Science from University of Notre Dame, Indiana, USA, in May 2010. Since then, he has been a Research Assistant Professor in Department of Computer Science and Engineering at the Uiversity of Notre Dame. His research focuses on algorithm design and analysis in computational geometry.