Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Strukturierte Eingaben für geometrische Probleme charakterisieren, verstehen und ausnutzen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2012 bis 2020
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 216333926
 
Erstellungsjahr 2019

Zusammenfassung der Projektergebnisse

Der traditionelle Ansatz beim Entwurf und der Analyse von Algorithmen beruht auf der worst-case Sichtweise. Dabei ist das Ziel, Algorithmen so zu entwerfen, dass sie das bestmögliche Verhalten für die schlimmstmögliche Eingabe zeitigen. Es wird nicht versucht, den Algorithmus für die jeweilige Anwendung zu optimieren. Dieser worst-case Ansatz hat sich als sehr erfolgreich erwiesen. Er erlaubt es, sich zunächst auf das Wesentliche zu konzentrieren und die Struktur der zugrundeliegenden Probleme zu erfassen, ohne dass zusätzliche Annahmen über das Anwendungsszenario zu Ablenkungen führen. Gleichzeitig hat es schon immer Ansätze gegeben, dieses Modell zu verfeinern, um bessere Ergebnisse zu erzielen. Gerade in letzter Zeit hat diese Richtung an Interesse gewonnen. Zum einen werden die zu verarbeitenden Datenmengen zu groß und komplex für worstcase Algorithmen. Zum anderen haben die Eingaben oft mehr Struktur, und wir wissen oft mehr über die Daten, als von den bisherigen Verfahren ausgenutzt wird. Das Ziel des Projektes war es, genauer zu beleuchten, wie sich verschiedene Strukturen der Eingabedaten charakterisieren lassen, und zu verstehen, welche Eigenschaften daraus folgen. Die Hoffnung war, effizientere und auch einfachere Algorithmen zu finden, die sich diese Struktur zunutze machen. Dabei haben wir uns auf Probleme aus der algorithmischen Geometrie konzentriert, da Eingang aus der Geometrie oft zusätzliche Eigenschaften besitzen, als es bei rein kombinatorischen Problemen der Fall ist. Im Laufe des Projekts ist es uns gelungen, diesem Ziel ein wenig näher zu kommen. So haben wir uns beispielsweise mit einer Klasse von geometrisch definierten Graphen beschäftigt, bei der die Knoten und Kanten geometrischen Objekten in der Ebene und den Beziehungen zwischen diesen Objekten entsprechen. Es hat sich herausgestellt, dass diese Graphen eine reichhaltige Struktur besitzen, die es uns erlaubt, algorithmische Aufgaben wie Breitensuche, die dynamische Aufrechterhaltung eines aufspannenden Baumes oder die verteilte Wegfindung effizienter zu lösen als mit herkömmlichen Methoden. Diese Untersuchungen haben uns auch auf einige interessante Nebenschauplätze geführt, wie zum Beispiel der Fragestellung, welcher Aufwand nötig ist, um eine attraktorbasierte Wegfindung in dreidimensionalen Polytopen zu ermöglichen. Wir konnten auch eine neue dynamische Datentruktur für Nächste-Nachbar-Suche in der Ebene bezüglich allgemeiner Metriken finden, welche sich bereits in anderen Zusammenhängen als nützlich erwiesen hat. Ein unerwarteter Nebeneffekt unseres Projekts war, dass wir neue Erkenntnisse zur algorithmischen Komplexität des klassischen Fréchet Abstandes erzielen konnten. Dies ergab sich aus der Feststellung, dass einige der Sichtweisen, die wir im Rahmen des Projektes entwickelt haben, sich für dieses Problem als nützlich erweisen. Dadurch konnten nach fast 20 Jahren den ersten verbesserten Algorithmus für das Problem finden und zu einem neuen Ansatz beitragen, der erklären soll, worin die algorithmische Schwierigkeit des Problems besteht.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung