Startseite > Fachgruppen > Algorithmen und Komplexität > Projekte > Algorithmik großer dynamischer geometrischer Graphen

Algorithmik großer dynamischer geometrischer Graphen

Ziele

Ziel dieses Projekts ist es, Methoden zur Analyse und Bearbeitung sehr großer dynamischer geometrischer Graphen zu entwickeln, wie sie u.a. in Anwendungen in der Computergrafik und in mobilen ad-hoc Netzwerken entstehen. Unter Dynamik verstehen wir dabei in erster Linie Dynamik, die durch Bewegung induziert wird. Wir gehen außerdem davon aus, dass die betrachteten Graphen wegen ihrer enormen Größe nicht mehr in den Hauptspeicher passen. Daher sind selbst Linearzeit-Algorithmen auf solchen Eingaben häufig unakzeptabel langsam. Das Aufrechterhalten von Datenstrukturen ist aufgrund der Bewegungsdynamik ebenfalls ineffizient. Daher entwickeln und analysieren wir in diesem Projekt Methoden, mit deren Hilfe man in sublinearer Zeit Informationen über große geometrische Graphen erhalten kann. In der ersten Projektphase haben wir uns darauf konzentriert, Methoden zu entwickeln und zu analysieren, die Informationen über solche Graphen in sublinearer Zeit berechnen, wobei wir in erster Linie Algorithmen zum Testen von Eigenschaften von Graphen entwickelt haben (Property Testing). In der zweiten Projektphase lag der Schwerpunkt unserer Arbeit dann auf der Entwicklung von sublinearen Approximationsalgorithmen für grundlegende Graphenprobleme wie Berechnung von minimalen Spannbäumen oder Clustering Problemen.

Ein weiterer Schwerpunkt des Projektes ist Modellierung und Komplexität von Bewegung. Bewegung untersuchen wir insbesondere an Beispielen aus der Computergrafik: Durch bewegliche Teile einer 3D-Szene sowie die Bewegung eventuell mehrerer Besucher im Sinnes eins Walkthough ist die Folge der in Echtzeit darzustellenden 2D-Sichten der 3D-Szene hochgradig dynamisch. Somit sind klassische statische Methoden nicht erfolgsversprechend. Daher benötigen wir Methoden, die z.B. den Rendering Prozeß unterstützen, ohne dabei komplexe Dastenstrukturen aufrechtzuerhalten. Insbesondere on-line Methoden sind für diese Art von Anwendung besonders geeignet.

Zur Zeit beschäftigen wir uns hauptsächlich mit Fragestellungen aus den Gebieten 'Sublineare Algorithmen für Probleme auf großen Graphen' sowie 'Datenstrukturen und Algorithmen für sich bewegende Objekte'. Dabei liegt in beiden Teilbereichen der Schwerpunkt unserer Arbeit auf der Entwicklung von Algorithmen für Clustering Probleme. Solche Clustering Verfahren können sowohl bei der Strukturierung von (mobilen) Netzwerken als auch in der Entwicklung von Datenstrukturen für Probleme aus der Computergrafik eingesetzt werden.

Sublineare Algorithmen für Probleme auf großen Graphen

Das Forschungsgebiet 'sublineare Algorithmen' ist noch relativ jung. Das ist vermutlich ein Grund, warum es nur wenig Resultate gibt, die Klassen von Problemen benennen, für die ein sublinearer Algorithmus existiert. Im Bereich der sublinearen Approximationsalgorithmen ist uns kein einziges Resultat dieser Form bekannt. Die Algorithmen basieren auf Methoden, die speziell auf das untersuchte Problem zugeschnitten wurden und nur schwer auf andere Probleme zu übertragen sind. Daher halten wir die Entwicklung allgemeiner Methoden für sublineare Algorithmen für ein zentrales Forschungsziel in diesem Gebiet. Um uns diesem Ziel zu nähern, werden wir uns wie auch schon in der zweiten Antragsphase einzelne ausgewählte Probleme untersuchen. Unser Schwerpunkt wird hierbei auf klassischen Clustering Problemen wie k-Median, k-Means und Min-Sum-k-Clustering liegen.

Datenstrukturen und Algorithmen für sich bewegende Objekte

Ein wichtiges Ziel unseres Projektes ist die Modellierung und Entwicklung von Algorithmen für sich bewegende Objekte. Dabei interessieren uns insbesondere Anwendungen mit großer Dynamik. Um mit dieser großen Dynamik umzugehen, wollen wir unter anderem Techniken aus dem Gebiet der sublinearen Algorithmen einsetzen.

Ziel der dritten Antragsphase ist die Entwicklung von Clustering Algorithmen für sich bewegende Objekte. Solche Algorithmen finden z.B. Anwendung in mobilen ad-hoc Netzwerken und in der Computer Grafik. Wir werden uns auf die beiden theoretischen Modelle kinetische und soft kinetische Datenstrukturen sowie auf Anwendungen in der Computergrafik konzentrieren. Dabei wollen wir auch die in diesem Projekt entwickelte geglättete Bewegungskomplexität als Komplexitätsmaß berücksichtigen.

Das Projekt wird seit dem 1.1.2002 von der DFG im Rahmen des Schwerpunktprogramms 'Algorithmik großer und komplexer Netzwerke' gefördert. Ein Antrag auf Förderung der dritten Projektphase wurde bei der DFG eingereicht.