Let T be a planar subdivision with n vertices. Each face of T has a weight from [1, ρ] ∪ {∞}. 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 T in O ((kn+k~4 log(k/ε))/ε log~2 ρn/ε) time, where k is the smallest integer such that the sum of the k smallest angles in T is at least π. Therefore, our running time can be as small as O (n~4/ε log~2 ρn/ε) if there are O(1) small angles and it is O (n~4/ε log n/ε log~2 ρn/ε) in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size O(n + k~2) such that no triangle has two angles less than min{π/(2k), π/12}.
展开▼
