Title: Querying Approximate Shortest Paths in Anisotropic Regions 
Speaker:  Yajun WANG
HKUST

Date: Friday, March 30,2007
Time 11-12PM
Venue: Room  3464, HKUST

  
Abstract:
We present a data structure for answering approximate shortest path
queries in a planar subdivision from a fixed source. Let r >= 1 be a
real number. Distances in each face of this subdivision are measured
by a possibly asymmetric convex distance function whose unit disk is
contained in a concentric unit Euclidean disk, and contains a
concentric Euclidean disk with radius 1/r. Different convex distance
functions may be used for different faces, and obstacles are allowed.
Our data structure returns an (1+ e) approximation of the shortest
path cost from the fixed source to a query destination in O(log
(rn/e)) time. Afterwards, an (1+ e)-approximate shortest path can be
reported in time linear in its complexity. The data structure uses
O((r^2 n^4/e^2) log (rn/e)) space and can be built in O((r^2 n^4/e^2)
(log (rn/e))^2) time. Our time and space bounds do not depend on any
geometric parameter of the subdivision such as the minimum angle.