Kunst! - Exact Algorithms for Art Gallery Variants

• Applicant: Professor Dr. Alexander Kröller
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering