Triangulation refinement and approximate shortest paths in weighted regions

Let τ planar subdivision with n vertices. Each face of τ has a weight from [l,ρ] ∪infin;. A path inside a face has cost equal to the product of its length and the face weight. In general, the cost of a path is the sum of the subpath costs in the faces intersected by the path. For any ε ∈ (0,1), we present a fully polynomial-time approximation scheme that finds a (1 +ε)-approximate shortest path between two given points in τ in O (kn+k⁴log (k/ε)/εlog² pn/ε)time, where k is the smallest integer such that the sum of the k smallest angles in τ is at least π. Therefore, our running time can be as small as O (n/εlog²pn/ε) if there are O (1) small angles and it is O (n⁴/εlogn/εlog²pn/ε)in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size 0 (n + k²) such that no triangle has two angles less than min{π/ (2k),π/12}.