Ultrafast Euclidean Shortest Path Computation Using Hub Labeling
Abstract
Finding shortest paths in a Euclidean plane containing polygonal obstacles is a well-studied problem motivated by a variety of real-world applications. The state-of-the-art algorithms require finding obstacle corners visible to the source and target, and need to consider potentially a large number of candidate paths. This adversely affects their query processing cost. We address these limitations by proposing a novel adaptation of hub labeling which is the state-of-the-art approach for shortest distance computation in road networks. Our experimental study conducted on the widely used benchmark maps shows that our approach is typically 1-2 orders of magnitude faster than two state-of-the-art algorithms.
Cite
Text
Du et al. "Ultrafast Euclidean Shortest Path Computation Using Hub Labeling." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I10.26463Markdown
[Du et al. "Ultrafast Euclidean Shortest Path Computation Using Hub Labeling." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/du2023aaai-ultrafast/) doi:10.1609/AAAI.V37I10.26463BibTeX
@inproceedings{du2023aaai-ultrafast,
title = {{Ultrafast Euclidean Shortest Path Computation Using Hub Labeling}},
author = {Du, Jinchun and Shen, Bojie and Cheema, Muhammad Aamir},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2023},
pages = {12417-12426},
doi = {10.1609/AAAI.V37I10.26463},
url = {https://mlanthology.org/aaai/2023/du2023aaai-ultrafast/}
}