Constrained Shortest Path Finding on Terrain Surfaces
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-24
DOI: 10.1145/3802031 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Victor Junqiu Wei und 2 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben. Gefördert von: Guangdong Basic and Applied Basic Research Foundation, Macau Science and Technology Development Fund, Faculty Research Grant of MUST.
Abstract (Originalsprache)
With the advancement of geo-positioning technologies, the terrain surface has become more and more popular and has drawn a lot of attention from academia and industry. In this paper, we propose a fundamental problem, namely C onstrained Shortest P ath Finding on T errain S urfaces (CPTS). Given a source point s , a destination point t , and a set P of point-of-interests on the terrain surface, the goal is to find the shortest s - t path passing through all points in P on the terrain surface. This problem finds a plethora of applications in map services, military vehicle path planning, scientific studies, etc. We prove that CPTS is an NP-hard problem. Due to its hardness, we then develop an approximation algorithm for the problem. Let N and k denote the number of vertices on the terrain surface and the number of points in P , respectively. The running time and space overhead of our algorithm are O ( k-N log 2 N over ∈ 2β ) and O ( k over ∈ 2β ), where ∈ is a real-valued user-specified parameter in the range of [0,1] and β is a small constant in the range of [1.5, 2]. The approximation ratio of our algorithm is 2 ⋅ (1+∈). Our theoretical analysis and empirical study both demonstrate that our algorithm significantly outperforms all baselines in terms of running time and space overhead, with a nearly identical or better approximation ratio.
Förderung
- Guangdong Basic and Applied Basic Research Foundation
- Macau Science and Technology Development Fund
- Faculty Research Grant of MUST
- Guangdong Science and Technology Department
- National Natural Science Fund of China
Zitieren
APA
Wei, V. J., Xie, M., & Wang, W. (2026). Constrained Shortest Path Finding on Terrain Surfaces. Proceedings of the ACM on Management of Data, 4(3), 1-24. https://doi.org/10.1145/3802031
Vancouver
Wei VJ, Xie M, Wang W. Constrained Shortest Path Finding on Terrain Surfaces. Proceedings of the ACM on Management of Data. 2026;4(3):1-24. doi:10.1145/3802031
BibTeX
@article{Wei2026,
author = {Wei, Victor Junqiu and Xie, Min and Wang, Weicheng},
title = {Constrained Shortest Path Finding on Terrain Surfaces},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--24},
doi = {10.1145/3802031}
}
EUVIMED