---
title: "Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths"
authors:
  - "Stefan Funke"
  - "Daniel Koch"
  - "Claudius Proissl"
  - "Christian Staib"
  - "Felix Weitbrecht"
doi: "10.24963/ijcai.2025/946"
url: "https://ijcai.org/proceedings/2025/946"
pdf: "https://ijcai.org/proceedings/2025/0946.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8510-8517"
track: "Main Track"
keywords:
  - "Planning and Scheduling: PS: Routing"
  - "Search: S: Combinatorial search and optimisation"
  - "Search: S: Applications"
---

# Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8510-8517. DOI: [10.24963/ijcai.2025/946](https://doi.org/10.24963/ijcai.2025/946)

## 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.