Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths

Funke, Stefan; Koch, Daniel; Proissl, Claudius; Staib, Christian; Weitbrecht, Felix

doi:10.24963/ijcai.2025/946

Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths

Stefan Funke, Daniel Koch, Claudius Proissl, Christian Staib, Felix Weitbrecht

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8510-8517.

https://doi.org/10.24963/ijcai.2025/946

Keywords

Planning and Scheduling: PS: Routing
Search: S: Combinatorial search and optimisation
Search: S: Applications

Abstract

We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions.

Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.

Stefan Funke, Daniel Koch, Claudius Proissl, Christian Staib, and Felix Weitbrecht. 2025. Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8510–8517. https://doi.org/10.24963/ijcai.2025/946

@inproceedings{ijcai2025p946,
  title     = {Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths},
  author    = {Funke, Stefan and Koch, Daniel and Proissl, Claudius and Staib, Christian and Weitbrecht, Felix},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {8510--8517},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/946},
  url       = {https://doi.org/10.24963/ijcai.2025/946},
}

TY  - CPAPER
TI  - Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths
AU  - Funke, Stefan
AU  - Koch, Daniel
AU  - Proissl, Claudius
AU  - Staib, Christian
AU  - Weitbrecht, Felix
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 8510
EP  - 8517
DO  - 10.24963/ijcai.2025/946
UR  - https://doi.org/10.24963/ijcai.2025/946
ER  -