Aarhus University Seal / Aarhus Universitets segl
Lecture / talk


Siu-Wing Cheng (HKUST)

Info about event


Thursday 27 August 2015,  at 14:15 - 15:00


Approximate Shortest Paths in Weighted Regions


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