EUVIMEDEUVIMED entdecken
Crossref

Constrained Shortest Path Finding on Terrain Surfaces

Victor Junqiu Wei, Min Xie, Weicheng Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →