Aarhus University Seal / Aarhus Universitets segl
Lecture / talk

MADALGO Seminar

Siu-Wing Cheng (HKUST)

Info about event

Time

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

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