Abstract: Suppose a robot moves in a room from one location to another; how should the robot choose a 'good' path to move? This is a geometric path problem, a topic in computational geometry. In this talk, I will present my recent work on algorithms for computing geometric paths from theoretical perspective. One such problem that has attracted much attention is the shortest path problem among obstacles in the plane. Given a set of pairwise disjoint polygonal obstacles in the plane, the problem is to compute an obstacle-avoiding Euclidean shortest path between two points. The problem has been studied extensively since 1970s. A long-standing (almost 30 years) open question asks for an optimal algorithm (in terms of time and space complexities) for the problem, which was one of the most important open problems on geometric paths. We recently answered the open question affirmatively by giving an optimal algorithm. Besides presenting this result, I will also briefly introduce my previous work on other geometric path problems, such as shortest paths among curved obstacles, shortest paths in the L1 metric, minimum-link paths, quickest visibility paths, bicriteria shortest paths, etc. Finally, I will discuss some future research directions.

Short Bio: Dr. Haitao Wang is an Associate Professor in the Department of Computer Science, Utah State University. He joined the department in 2012 as an Assistant Professor and was promoted to Associate Professor in 2018. Dr. Wang received his Ph.D. degree in Computer Science from University of Notre Dame in 2010. He also served as a research assistant professor at Notre Dame from 2010 to 2012. Dr. Wang's research interests include computational geometry, algorithms, combinatorial optimization, operations research, theoretical computer science, etc.