Efficient Shortest Path Queries on 3D Weighted Terrain Surfaces for Moving Objects
Yinzhao Yan, Raymond Chi-Wing Wong · 2024
Studying the shortest path query for moving objects on a terrain surface has aroused widespread concern in industry and academia. In this paper, we study the weighted region problem, which aims at finding the shortest path between two points passing different regions on a 3D weighted terrain surface and different regions are assigned different weights. We propose an efficient (1 + ϵ)-approximate on-the-fly algorithm to solve it. Our experimental results show that our algorithm is up to 1630 times and 40 times better than the best-known algorithm in terms of running time and memory usage in realistic settings1.