Title : Approximate shortest paths in moderately anisotropic regions

We want to find an approximate shortest path for a point robot moving in a planar
subdivision. Each face of the subdivision is associated with a convex distance function that
has the following property: its unit disk contains a unit Euclidean disk, and is contained
in a Euclidean disk with radius \rho. Obstacles are allowed, so there can be regions that the
robot is not allowed to enter. We give an algorithm that, given any two points s and t,
finds an approximate shortest path between s and t whose length is at most (1+\epsilon) times
the length of the shortest path. When n is the number of vertices in the input subdivision,
the running time of our algorithm is O((\rho n^3/\epsilon^2) log(\rho) log(n\rho/\epsilon)). 
This bound does not depend on any other parameters, in particular it does not depend on 
the minimum angle in the subdivision. As special cases, we can solve the following 
two problems within the same time bound:
- the weighted region problem where all weights are in [1, \rho] [ {+\infinite},
- shortest paths in the flow field when the speed of the robot is 1 and the speed of the
flow is at most (\rho - 1)/(\rho + 1).

Participants : Siu-Wing, Hyeon-Suk, Antoine