Kunst! - Exakte Algorithmen für Kunstgalerieprobleme

• Antragsteller: Professor Dr. Alexander Kröller
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 206924222

Kunst! betrachtet ein klassisches Problem aus der Algorithmischen Geometrie mit neuen Augen: Das Kunstgalerieproblem (AGP). Dabei ist ein Polygon (die „Galerie“) gegeben, und eine minimale Menge von Punkten (die „Wächter“) gesucht, so dass die Galerie vollständig bewacht ist. Wir kombinieren Methoden des Algorithm Engineering mit Algorithmischer Geometrie und Optimierung, um AGP optimal zu lösen. Das geht weit darüber hinaus, was in diesem Bereich bisher üblich war. Das Problem wird als doppelt unendliches ganzzahliges Programm formuliert, und mit geometrischen Verfahren und Lösungstechniken linearer Programmierung gelöst. Wir evaluieren die entwickelten Verfahren anhand von Probleminstanzen aus der Praxis. Dabei erzeugen und veröffentlichen wir eine umfassende Instanzbibliothek. Des weiteren implementieren wir Algorithmen zur Berechnung von Sichtbarkeitspolygonen und steuern sie dem CGAL-Projekt bei. Varianten von AGP haben praktische Anwendungen, beispielsweise bei der Vermessung von Gebäuden oder Industrieanlagen mit Laserscannern. Diese untersuchen wir ebenfalls im Sinne des Algorithm Engineering.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering