Christian Staib

Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths

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