EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

Jinchun Du; Bojie Shen; Muhammad Aamir Cheema

AAAI 2026technical0 citations

EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

Jinchun Du, Bojie Shen, Muhammad Aamir Cheema

Abstract

The Euclidean Shortest Path Problem (ESPP) is a classic problem which requires finding the shortest path in a Euclidean plane with polygonal obstacles. The state-of-the-art solution, Euclidean Hub Labeling (EHL), offers ultra-fast query performance but comes with significant memory overhead, requiring up to tens of gigabytes of storage on large maps, limiting its use in memory-constrained environments like mobile phones. Additionally, EHL

BibTeX

@inproceedings{aaai2026_ehlmemorybudgete,
  title = {EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding},
  author = {Jinchun Du and Bojie Shen and Muhammad Aamir Cheema},
  booktitle = {AAAI 2026},
  year = {2026}
}