Title:

Approximate Shortest Paths in Weighted Regions

Abstract: 

The weighted region in the plane models the varying difficulties of traversing different regions by associating different weights with them, and the cost of a path inside a region is equal to the product of its length and the region weight.  There have been extensive research on this problem, but only one FPTAS is known so far that has a running time proportional to n^8, where n is the number of vertices in the polygonal environment.  In this talk, we sketch a new FPTAS that has a worst-case running time proportional to n^4.  In fact, when there are only O(1) small angles in the environment, our running time is linear in n.  We will also discuss some future related research directions.

Host: Peyman Afshani