Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron · 2014
Let be a planar subdivision with n vertices. Each face of 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 in 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 if there are O(1) small angles and it is in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size O(n + k2) such that no triangle has two angles less than min{π/(2k), π/12}.