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

• Antragsteller: Professor Dr. Wolfgang Mulzer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 216333926

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 worst-case Algorithmen. Zum anderen haben die Eingaben oft mehr Struktur, und wir wissen oft mehr über die Daten, als von den bisherigen Verfahren ausgenutzt wird.Wir wollen genauer beleuchten, wie sich verschiedene Strukturen der Eingabedaten charakterisieren lassen, und verstehen, welche Eigenschaften daraus folgen. Das Ziel soll es sein, effizientere und auch einfachere Algorithmen zu finden, die sich diese Struktur zunutze machen. Dabei werden wir uns auf Probleme aus der algorithmischen Geometrie konzentrieren.

• DFG-Verfahren: Sachbeihilfen