Kunstgalerie-Problem: n/3 Wächter genügen – Fisk 1978

Einleitung: Das Eureka-Gefühl der Mathematik

Es gibt Momente in der Mathematik, in denen sich eine scheinbar undurchdringliche Aufgabe in Luft auflöst und einer verblüffend einfachen Erkenntnis weicht. Genau dieses Staunen stellt sich ein, wenn man sich mit dem Kunstgalerie-Problem beschäftigt, einer der schönsten Fragen der Geometrie. Es geht darum: Wie viele Wächter braucht eine Kunstgalerie, damit wirklich jeder Winkel überwacht wird?

Die Antwort ist so überraschend wie bestechend. Für eine Galerie in Form eines einfachen Polygons mit n Ecken genügen niemals mehr als n/3 Wächter, unabhängig davon, wie verschachtelt und unregelmäßig der Grundriss auch sein mag. Ein neuneckiger Raum lässt sich also mit nur drei Wächtern vollständig im Blick behalten. Diese Erkenntnis ist kein bloßer Zufall, sondern das Ergebnis einer faszinierenden Beweiskette, die Sie in den folgenden Abschnitten Schritt für Schritt nachvollziehen können.

Das Kunstgalerie-Problem wurde 1973 von dem Mathematiker Victor Klee formuliert. Rund fünf Jahre später präsentierte Steve Fisk einen Beweis, der durch seine Schlichtheit besticht und bis heute als Musterbeispiel für kreatives Denken in der Mathematik gilt. Diese Idee zeigt, wie aus einer alltäglichen Frage eine kleine Offenbarung werden kann.

Was ist das Kunstgalerie-Problem?

Stellen Sie sich eine Ausstellungshalle vor, deren Grundriss an ein unregelmäßiges Polygon erinnert, mit Nischen, Winkeln und verwinkelten Gängen. Die zentrale Frage des Kunstgalerie-Problems lautet: Wie viele Wächter müssen Sie positionieren, damit jeder einzelne Punkt dieser Fläche von mindestens einer Person eingesehen werden kann? Gesucht ist stets die Mindestanzahl an Aufsichtspersonen, die für eine vollständige Überwachung ausreicht.

Der Mathematiker Victor Klee formulierte diese Fragestellung im Jahr 1973. Er schuf damit ein klassisches Problem der geometrischen Kombinatorik, das bis heute in der Computergrafik, der Robotik und der Algorithmik Anwendung findet. Die Frage ist so bestechend einfach formuliert, dass sie Laien sofort fasziniert, und doch so tiefgründig, dass sie Fachleute seit Jahrzehnten beschäftigt.

Damit das Problem überhaupt mathematisch fassbar wird, müssen Sie einige Vereinfachungen akzeptieren. Die Galerie wird als einfaches Polygon modelliert. Das bedeutet: Die Wände sind gerade Linien, die sich nicht gegenseitig kreuzen, und der Raum enthält keine Löcher oder Innenhöfe. In der Realität sind die meisten Gebäude schlichte Rechtecke, aber Kunstgalerien zeichnen sich ja gerade durch außergewöhnliche Architektur aus. Genau diese ungewöhnlichen Formen machen das Problem interessant.

Zwei weitere Annahmen sind entscheidend. Die Wächter stehen stationär an den Ecken des Polygons und bewegen sich nicht durch den Raum. Sie verfügen über einen uneingeschränkten Rundumblick, sofern keine Wand ihre Sichtlinie unterbricht. Diese Idealisierung mag zunächst unrealistisch wirken, doch sie erlaubt es, das Problem auf seine mathematische Essenz zu reduzieren.

Bevor wir uns der Lösung zuwenden, lohnt ein kurzer Blick auf die Vorgeschichte. Obwohl Victor Klee das Problem 1973 aufwarf, bewies der tschechische Mathematiker Václav Chvátal bereits 1975 einen zentralen Satz dazu. Etwa fünf Jahre nach Klees Formulierung präsentierte dann Steve Fisk einen bemerkenswert klugen Beweis, der bis heute als Musterbeispiel für intuitive mathematische Argumentation gilt.

Der clevere Beweis von Steve Fisk

Im Jahr 1978, etwa fünf Jahre nachdem Victor Klee das Kunstgalerie-Problem erstmals formuliert hatte, gelang dem Mathematiker Steve Fisk etwas Bemerkenswertes: Er fand einen Beweis, der so anschaulich ist, dass man ihn fast spielerisch nachvollziehen kann. Dabei war das Problem zu diesem Zeitpunkt keineswegs mehr ungelöst. Václav Chvátal, ein tschechisch-kanadischer Mathematiker, hatte bereits 1975 einen ersten Beweis vorgelegt. Doch Fisks Ansatz stach durch seine Klarheit und Intuition hervor.

Seine Strategie lässt sich in drei Schritten denken. Stellen Sie sich ein beliebiges einfaches Polygon vor, also eine Grundrissform ohne sich kreuzende Kanten und ohne Löcher. Der erste Schritt besteht darin, dieses Polygon in Dreiecke zu zerlegen. Diese Technik, die sogenannte Triangulierung, verbindet die Ecken des Polygons mit geraden Linien, bis die gesamte Fläche in lauter einzelne Dreiecke aufgeteilt ist.

Nun kommt der zweite Schritt, und hier zeigt sich Fisks Genialität. Er betrachtete die entstandene Dreiecksstruktur nicht als Fläche, sondern als einen Graphen, also als eine Sammlung von Punkten und Verbindungslinien. Auf diesen Graphen wandte er eine klassische Idee aus der Graphentheorie an: die Färbung. Er färbte jede Ecke des Polygons mit einer von drei Farben, zum Beispiel Rot, Blau und Grün. Die entscheidende Bedingung lautete: Jedes Dreieck muss an seinen drei Ecken alle drei verschiedenen Farben tragen. Kein Dreieck darf also zwei Ecken derselben Farbe besitzen.

Der dritte Schritt ist dann fast schon die Pointe. Fisk wählte eine der drei Farbklassen aus, etwa die blaue, und platzierte an jeder blau gefärbten Ecke einen Wächter. Weil jedes Dreieck genau eine blaue Ecke besitzt, wird folglich jedes einzelne Dreieck von mindestens einem Wächter überblickt. Da die Dreiecke zusammen das gesamte Polygon ausfüllen, ist damit die ganze Galerie abgedeckt.

Wie viele Wächter braucht man nun konkret? Die Färbung teilt die Ecken in drei Gruppen auf. Da Sie die kleinste dieser Gruppen wählen können, liegt die Anzahl der benötigten Wächter bei höchstens einem Drittel der Gesamtzahl der Ecken. Bei einem Polygon mit neun Ecken sind das also maximal drei Wächter, ganz gleich, wie verschachtelt der Grundriss aussieht. Diese Obergrenze von n/3 ist nicht nur eine theoretische Spielerei, sondern das Herzstück von Fisks Lösung für das Kunstgalerie-Problem.

Fazit: Offene Fragen und Erweiterungen

Das Kunstgalerie-Problem ist weit mehr als eine hübsche Denksportaufgabe. Es öffnet die Tür zu einem ganzen Kosmos verwandter Fragen, die Mathematikerinnen und Mathematiker bis heute beschäftigen. Die ursprüngliche Fragestellung war bewusst einfach gehalten: unbewegliche Wachen, gerade Wände, ein zweidimensionaler Grundriss ohne Hindernisse. Doch die Realität ist selten so aufgeräumt.

Was passiert beispielsweise, wenn sich die Wächter bewegen dürfen? Oder wenn Säulen und Hindernisse die Sicht versperren? Wie verändert sich die Lösung bei gekrümmten Wänden, die keine geraden Linien mehr aufweisen? Und was geschieht, wenn Sie statt einer flachen Grundfläche einen dreidimensionalen Raum bewachen müssen? Diese Variationen sind keine akademischen Spielereien. Sie haben praktische Bedeutung für die Überwachung moderner Gebäude, die selten den idealisierten Formen der Theorie entsprechen.

Einige dieser erweiterten Fragestellungen haben Mathematiker inzwischen gelöst. Andere erweisen sich als bemerkenswert hartnäckig und widerstehen bis heute klaren Beweisen. Gerade diese Mischung aus Gelöstem und Ungelöstem macht das Forschungsfeld so lebendig. Für Sie als Leser bedeutet das: Das Kunstgalerie-Problem ist kein abgeschlossenes Kapitel der Mathematik, sondern ein offenes Buch. Wer Freude an geometrischem Denken hat, findet hier weiterhin Raum für eigene Überlegungen und vielleicht sogar für eine neue, überraschende Idee. Die Geschichte dieses Problems zeigt, dass manchmal ein ungewöhnlicher Blickwinkel genügt, um ein scheinbar schwieriges Rätsel in ein helles Licht zu tauchen.