Projekt: Algorithmik großer, dynamischer, geometrischer Graphen

im Schwerpunkt Nr.1126 : Algorithmik großer und komplexer Netzwerke

Inhaltsübersicht:

Zusammensetzung der Arbeitsgruppe:

Universität-GH Paderborn, Heinz Nixdorf Institut und FB 17 Mathematik-Informatik ,Theoretische Informatik: Algorithmen, Komplexitätstheorie, Parallelität

Prof. Dr. Friedhelm Meyer auf der Heide
Jun-Prof. Dr. Christian Sohler
Dipl. Math. Valentina Damerow
Dipl. Inf. Jens Krokowski

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.

Liste der aus dem Projekt hervorgegangenen Publikationen und eigene Vorarbeiten:

(Update coming soon)

2003:

A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, C. Sohler
Sublinear Approximation of Euclidean Minimum Spanning Tree
Accepted at the 14th ACM-SIAM Symposium on Discrete Algorithm (SODA'03).

Christian Sohler
Property Testing and Geometry
Dissertation, to appear in: HNI-Verlagsschriftenreihe, Vol. 119, Heinz-Nixdorf Institut and University of Paderborn, 2003.

2002:

Ingo Höckenschnieder, Achim Koberstein, Jörn Mühlencord, Stefan Rührup, Olaf Sielemann, Tatjana Voth
Projektgruppe: Datenstrukturen zur Verwaltung geometrischer Objekte.
Abschlußbericht der Projektgruppe, 2002.

Artur Czumaj,Christian Sohler
Abstract Combinatorial Programs and Efficient Property Testers
Accepted at the 43th Symposium on Foundations of Computer Science (FOCS'02).

J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, F. Meyer auf der Heide.
The Randomized Sample Tree: A Data Structure for Externally Stored Virtual Environments.
Proceedings of ACM Symposium on Virtual Reality Software and Technology (VRST 2002), Hong Kong, China, S. 137-146, November, 2002.

B. Mueck, W. Dangelmaier, M. Fischer, W. Klemisch.
Bi-directional Coupling of Simulation Tools with a Walkthrough System.
Proceedings of the Simulation und Visualisierung 2002, S. 71--84, 2002.

2001:

W. Klemisch.
3D-Visualisierung hochkomplexer dynamischer Szenen im Anwendungsbereich von industriellen Simulationswerkzeugen.
Diplomarbeit, Universität Paderborn, 2001.

I. Höckenschnieder, Jörn M"uhlencord, Stefan Rührup.
Anwendung dynamischer Datenstrukturen in einem verteilten Walkthrough-System.
Studienarbeit, Universität Paderborn, 2001.

Artur Czumaj, Christian Sohler
Testing Hypergraph Coloring
In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP'01), pages 493-505.

Artur Czumaj, Christian Sohler
Property Testing with Geometric Queries
In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA'01), pages 266-277.

Michael Wand, Matthias Fischer, Ingmar Peter, Friedhelm Meyer auf der Heide, Wolfgang Straßer
The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes
In: Computer Graphics (SIGGRAPH 01 Conference Proceedings); pages 361-370; 2001.

Artur Czumaj, Christian Sohler
Soft Kinetic Data Structures
In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA'01), pages 865-872.

2000:

Artur Czumaj, Christian Sohler, Martin Ziegler
Property Testing in Computational Geometry
In: Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00), Saarbrücken, pages 155-166, 2000.