Praktische Theorie - Algorithm Engineering zur Lösung geometrischer und weiterer Probleme

Ein gegebenes Problem kann oft auf verschiedene Weise gelöst werden - mit implementierten Verfahren, belegt durch Experimente, oder mit Algorithmen mit beweisbaren Eigenschaften und Garantien. Viel zu oft wird sich dabei für genau eine dieser beiden Herangehensweisen entschieden. Im schlimmsten Fall entstehen für beide Seiten Ergebnisse unter vollständiger Ignoranz der jeweiligen Gegenseite. Beim Algorithm Engineering (AE) wird diese Separation aufgehoben, und es werden Algorithmen entwickelt, die gleichermassen theoretisch wie praktisch valide sind. Nach einem Überblick über AE werden wir beispielhaft über das Kunstgalerieproblem berichten, einem seit fast 40 Jahren untersuchten Kernproblem der Algorithmischen Geometrie: Gegeben ein zweidimensionales Polygon (die "Galerie"), finde eine minimale Anzahl Punkte ("Wächter"), von denen aus das ganze Polygon gesehen werden kann. Wir stellen einen Ansatz vor, mit dem erstmals exakte Lösungen berechnet werden können, basierend auf doppelt-unendlichen ganzzahligen Programmen. Wir zeigen Ergebnisse einer praktischen Implementierung und skizzieren Erweiterungen für praktische Anwendungsfälle aus der Gebäudevermessung mittels Laserscannern. Schliesslich zeigen wir, wie aus einer experimentellen Arbeit neue theoretische Fragestellungen und bislang unbekannte Einsichten entstehen können.