Axel Schneewind

Scalable Ultrafast Almost-optimal Euclidean Shortest Paths

We consider the problem of computing high-quality Euclidean shortest paths amidst obstacles on a large scale. By transferring and adapting speed-up techniques from the road network setting, we are able to compute source target paths for problem instances with several million obstacle vertices within…