Path Refinement in Weighted Regions

In this paper, we study the weighted region problem (WRP) which is to compute a shortest path in a weighted partitioning of a plane. Recent results show that WRP is not solvable in any algebraic computation model over the rational numbers. Therefore, it is unlikely that WRP can be solved in polynomial time. Research has thus focused on determining approximate solutions for WRP. Approximate solutions for WRP typically show qualitatively different behaviors. We first formulate two qualitative criteria for weighted shortest paths. Then, we show how to produce a path that is quantitatively close-to-optimal and qualitatively satisfactory. More precisely, we propose an algorithm to transform any given approximate linear path into a linear path with the same (or shorter) weighted length for which we can prove that it satisfies the required qualitative criteria. This algorithm has a linear time complexity in the size of the given path. At the end, we explain our experiments on some triangular irregular networks (TINs) from Earth's terrain. The results show that using the proposed algorithm, on average, 51% in query time and 69% in memory usage could be saved, in comparison with the existing method.