Routing on the hyperbolic plane

Abstract

Das Problem des kürzesten euklidischen Weges ist ein Problem aus der Algorithmischen Geometrie. Es stellt die Frage nach dem kürzesten Pfad zwischen zwei Punkten in der euklidischen Ebene, auf dieser sind polygonale Hindernisse verteilt, die der Pfad nicht überschreiten darf. Diese Arbeit untersucht eine Variante des Problems auf einer Fläche mit einer anderen Geometrie, der hyperbolischen Ebene. Um mit der euklidischen Geometrie arbeiten zu können, führen wir das Beltrami-Klein-Modell sowie das Poincaré-Kreisscheiben-Modell ein, zwei bekannte Projektionen der hyperbolischen Ebene in die euklidische Ebene. Unter Verwendung dieser Modelle übertragen wir den kanonischen Ansatz, der die euklidische Version des Problems löst, auf die hyperbolische Ebene. Der Algorithmus umfasst die Berechnung einer Triangulierung des polygonalen Gebiets, um mit deren Hilfe den Visibility-Graph zu bestimmen. Unter Anwendung von A* oder Dijkstra auf diesem Graphen kann dann der kürzeste Weg zwischen zwei Punkten berechnet werden. Zusätzlich evaluieren wir ein Näherungsverfahren, das diese Algorithmen auf einem Untergraphen der Triangulierung anwendet. Da es keine Landkarten in der hyperbolischen Ebene gibt, wird ein Algorithmus zur Erzeugung polygonaler Gebiete vorgestellt und implementiert.