Fast query structures in anisotropic media

We study the minimum cost path problem in an environment in which the cost is direction dependent (anisotropic). The problem arises in sailing, robotics, aircraft navigation, and routing of autonomous vehicles, where the cost is affected by the direction of waves, winds, or slope of the terrain. We present an approximation algorithm to find a minimum cost path for a point robot moving in a planar subdivision, in which each face is assigned a translational flow that reflects the cost of travelling within this face.Our main contribution is a data structure that, given a subdivision with translational flows, returns a (1+ε)-approximate minimum cost path in the subdivision between any two query points in the plane.