Fully-polynomial-time approximation schemes for the Euclidean shortest path problem

Abstract

The shortest path problem is a well-studied problem in computer-science. For transport networks, there exist natural graph representations and highly efficient algorithms that can compute shortest paths on millions of nodes within milliseconds. In contrast, computing shortest paths in space (e.g. in R^2) poses some challenges. Shortest path computations in space have applications in robotics, naval routing or video games. As shortest paths in a continuum are hard to compute (with the Euclidean shortest-path problem in 3D even proven to be NP-hard), approximations can be necessary to obtain acceptable runtimes. In this thesis, an approximation scheme is studied that guarantees solutions with cost at most (1+ε) times the optimum. It uses a triangulation of the domain and, given ε, construct a discretization. By performing a Dijkstra search, one can then approximate shortest paths with the given quality guarantee. This scheme is implemented and its practicality evaluated on larger instances.

Die Berechnung kürzester Pfade ist ein zentrales Problem der Informatik. Ein häufiges Anwendungsgebiet sind Berechnungen in Straßennetzwerken, welche sich leicht als Graph darstellen lassen. Für diese existieren sehr effiziente Algorithmen, welche innerhalb von Millisekunden kürzeste Pfade in Graphen mit Millionen von Knoten finden. Die Berechnung euklidischer Pfade hat unter Anderem Anwendungen in der Robotik, im Schiffsrouting und in Videospielen, stellt aber zusätzliche Herausforderungen dar und ist im dreidimensionalen Raum sogar NP-schwer. Um in der Realität akzeptable Query-Zeiten zu ermöglichen, kann allerdings auf Näherungen zurückgegriffen werden. In dieser Arbeit wird ein solches Näherungsschema untersucht, welches kürzester Pfade mit Kosten von höchstens (1+ε) approximiert. Genutzt wird eine Triangulierung des Raums um, gegeben ε, eine Diskretisierung zu erzeugen. In dieser Diskretisierung können dann durch Dijkstra-Suchen kürzeste Pfade mit der gegebenen Qualitätsgarantie approximiert werden. Dieses Näherungsschema wird implementiert und die Anwendbarkeit auf größeren Instanzen evaluiert.