Effiziente Algorithmen zur Berechnung und Verringerung der Dilation geometrischer Netze, d.h. des maximalen Umwegs, der sich bei Benutzung des Netzes gegenüber dem Luftlinienabstand ergibt.

• Antragsteller: Professor Dr. Rolf Klein
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen