Efficient algorithms for computing and decreasing the dilation of geometric networks, i e the maximum detour that results from using the network as compared to the Euclidian distance

• Applicant: Professor Dr. Rolf Klein
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5411524

Die Dilation eines geometrischen Netzwerks S ist ein wichtiges Maß für seine Güte als Verbindungsmedium, denn sie bezeichnet den maximalen Umweg zwischen zwei Punkten, den man bei Benutzung von S gegenüber dem Luftlinienabstand hinnehmen muss. Wir wollen zunächst Algorithmen entwickeln, mit denen sich die Dilation geometrischer Netzwerke effizient berechnen lässt. Dann wollen wir untersuchen, wie man die Dilation eines Netzwerks durch Einfügen zusätzlicher Kanten mit einer vorgegebenen maximalen Gesamtlänge (Budget) möglichst weit verringern kann. Schließlich soll untersucht werden, wie man Netzwerke minimaler Dilation konstruiert. Dabei kann die Dilation auf zwei unterschiedliche Arten gemessen werden: Man kann entweder nur die Knotenpunkte von S berücksichtigen oder auch sämtliche Punkte auf den Kanten in die Bestimmung des Maximums einbeziehen. Beide Varianten haben wichtige Anwendungen. Sie lassen auf allgemeinere Szenarien übertragen.

• DFG Programme: Research Grants