Art gallery problem

rdf:langString Problem der Museumswächter

rdf:langString Das Problem der Museumswächter (en: Art gallery problem) ist eine Fragestellung der algorithmischen Geometrie. Dabei wird folgende Situation untersucht: „Gegeben sei eine polygonale Fläche mit Rand , interpretiert als Grundriss eines Museums. Wähle nun möglichst wenige Punkte (‚Wächter‘) im Innern des Polygons, sodass jeder Punkt im Innern des Polygons durch eine Gerade, die ganz in einschließlich Rand liegt, mit einem Wächter verbunden werden kann.“ Das ist äquivalent dazu, ein Polygon minimal sternförmig zu überdecken. In der Praxis tritt das Problem in der Robotik auf, wenn „künstliche Intelligenzen“ Bewegungsmuster in Abhängigkeit von ihren Umgebungen ausführen sollen. Manche Fragestellungen der digitalen Bildbearbeitung lassen sich auf Wächterprobleme zurückführen. Auch Beleuchtungsprobleme einer Bühne und das Problem bei der Beobachtung von Tierpopulationen in großen Gebieten können als Wächterproblem modelliert werden. Eine weitere Anwendung ist die Aufstellung der Infrastruktur für die Wetterbeobachtung oder zur Warnung vor Naturkatastrophen. Das Problem fällt komplexitätstheoretisch in die Klasse der APX-Probleme, das heißt, dass wahrscheinlich kein Algorithmus existiert, der es für allgemeine Polygone effizient und korrekt löst. Andererseits hat man für das Problem und seine Varianten obere Schranken für die Zahl der Wächter gefunden und beweisen können, dass diese auch scharf sind. Das heißt, sie können nicht weiter verbessert werden, ohne dass man sich auf spezielle Polygonklassen einschränkt. Die wahrscheinlich erste systematische Betrachtung von Sichtbarkeitsfragen regte Victor Klee im August 1973 auf einer Konferenz in Stanford an, indem er das Museumsproblem für Punktwächter und eine sich als korrekt herausgestellte Vermutung formulierte. Zwei Jahre später präsentierte Chvátal eine bewiesene Lösung des Problems.