We investigate the approximate shortest path problems in anisotropic regions in the plane. The anisotropic regions are defined by a triangulation with n vertices. Let ρ ≥ 1 be a real number. Distances in each face of this triangulation are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk, and contains a concentric Euclidean disk with radius 1/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. ^{2 3 2}...[ Read more ]

We investigate the approximate shortest path problems in anisotropic regions in the plane. The anisotropic regions are defined by a triangulation with n vertices. Let ρ ≥ 1 be a real number. Distances in each face of this triangulation are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk, and contains a concentric Euclidean disk with radius 1/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric.

For all ε ∈ (0,1), and for any two points s and t, we give an algorithm that finds a path from s to t whose cost is at most (1 + ε) times the optimal. Our algorithm runs in Ο(ρ²n³log ρ/ε²*log(ρn/ε)) time. For any fixed vertex s of the triangulation and ε ∈ (0,1), we develop a data structure to answer (1 + ε)-approximate shortest path queries for any point t in the triangulation in O(log*ρn/ε) time. The preprocessing takes time O(ρ²n³/ε²(log*ρn/ε)²), and the space complexity of the data structure is O(ρ²n³/ε²*log*ρn/ε). The complexity of the data structure matches the bound for the approximate shortest path algorithm up to a logarithmic factor.

Unlike most related previous work, our time and space bounds do not depend on the geometry of the environment; in particular they do not depend on the minimum angle in the triangulation.