Title: Approximate Homotopic Shortest Paths in Anisotropic Regions with Symmetric Cost

Speaker: Jiongxin Jin
HKUST


Date: Friday  April 3, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: 
We present an algorithm to find an approximate shortest 
path of a given homotopy type in a planar subdivision with 
n vertices and h obstacles.  The path cost is measured using 
symmetric convex distance functions associated with the 
subdivision faces, whichgeneralizes the weighted region model.  
We assume that the unit disk of each distance
function is contained in a concentric unit Euclidean disk, 
and contains a concentricEuclidean disk with radius 1 / \rho for 
some \rho > 1.  For any input path P with k segments and for 
any \eps \in (0,1), our algorithm computes a (1+\eps)-approximate
shortest path homotopic to P in 
O(\frac{\rho^5h^5}{\eps} k^2n^3 \log^4 \frac{\rho kn}{\eps}) time.
This bound does not depend on any other parameter; in particular, 
it does not depend on the
minimum angle or spread in the subdivision.