Algorithmik großer dynamischer geometrischer Graphen

点击翻译按钮获取中文摘要

Wir wollen uns in diesem Projekt mit der Modellierung, Entwicklung und Evaluierung von Algorithmen für Probleme auf großen dynamischen geometrischen Graphen beschäftigen, wie sie z.B. bei Problemen der Computergraphik, der Verkehrsüberwachung, oder der Telekommunikation auftreten. Ein geometrischer Graph ist ein Graph, dessen Knoten mit Positionen im euklidischen Raum versehen sind. Dynamik entsteht in geometrischen Graphen häufig dadurch, dass sich Knoten auf verschiedene Art und Weise bewegen dürfen. Diese Bewegungen induzieren Veränderungen in der Struktur des Graphen. Über die bisher bekannten Ansätze hinaus, wollen wir in unsere Modellierung von Bewegung anwendungsspezifische Charakterisierung wie Geschwindigkeit, Vorhersagbarkeit und Einschränkung von Bahnen einbeziehen. In der ersten Antragsphase werden Labeling (Flugzeuge in Verkehrskontrollsystemen), Partitionierungsprobleme, und Walkthrough Animation jeweils für bewegliche Objekte im Vordergrund stehen. Da diese Probleme entweder aufgrund ihrer Komplexität oder der zu erwartenden Größe der Instanzen nicht exakt zu lösen sind, werden wir moderne algorithmische Techniken zur Behandlung groer Datenmengen wie I/O-effiziente Algorithmen, Property Testing und Streaming einsetzen.