imported>Christian1985: /* Satz von Chvátal */

2026-02-26T20:45:40Z

Satz von Chvátal

Neue Seite

Das '''Problem der Museumswächter''' ({{enS|Art gallery problem}}) ist eine Fragestellung der [[Algorithmische Geometrie|algorithmischen Geometrie]]. Dabei wird folgende Situation untersucht:

{{Zitat
|Text=Gegeben sei eine [[polygon]]ale Fläche <math>G</math> mit Rand <math>\partial G</math>, interpretiert als Grundriss eines Museums. Wähle nun möglichst wenige Punkte <math>p_1,p_2\dots p_k</math> (‚Wächter‘) im Innern des Polygons, sodass jeder Punkt im Innern des Polygons durch eine Gerade, die ganz in <math>G</math> einschließlich Rand liegt, mit einem Wächter verbunden werden kann.}}
Das ist äquivalent dazu, ein Polygon minimal [[sternförmig]] zu [[Überdeckung (Mathematik)|überdecken]].

In der Praxis tritt das Problem in der [[Robotik]] auf, wenn „[[künstliche Intelligenz]]en“ Bewegungsmuster in Abhängigkeit von ihren Umgebungen ausführen sollen.<ref>{{Literatur |Autor=N. J. Nilsson |Titel=A mobile automaton: An application of artificial intelligence techniques |Verlag=Storming Media |Datum=1969}}</ref> Manche Fragestellungen der digitalen [[Bildbearbeitung]] lassen sich auf Wächterprobleme zurückführen.<ref>{{Literatur |Autor=L. S. Davis, M. L. Benedikt |Titel=Computational models of space: Isovists and isovist fields |Datum=1979}}</ref> 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ätstheorie|komplexitätstheoretisch]] in die Klasse der [[Approximationsalgorithmus|APX]]-Probleme, das heißt, dass wahrscheinlich<ref group="A">Bewiesen wurde die Zugehörigkeit unter der Voraussetzung <math>\mathcal{P}\neq\mathcal{NP}</math>. Viele Mathematiker gehen davon aus, der Beweis hat sich in den jüngeren Jahrzehnten jedoch als genuin schwierig herausgestellt. (Siehe [[P-NP-Problem]])</ref> kein [[Algorithmus]] existiert, der es für allgemeine Polygone [[Effizienter Algorithmus|effizient]] und korrekt löst. Andererseits hat man für das Problem und seine Varianten [[obere Schranke]]n 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.<ref>{{Literatur |Autor=R. Honsberger |Titel=Mathematical Gems II: The Dolciani Mathematical Expositions |Sammelwerk=Mathematical Association of America |Band=84 |Datum=1976}}</ref> Zwei Jahre später präsentierte [[Vašek Chvátal|Chvátal]] eine bewiesene Lösung des Problems.<ref name="chvátal" />

== Elementare Beispiele ==
Wir betrachten zunächst die „einfache“ Version des Problems mit stationären Wächtern. Man überlege sich für eine vorgegebene kleine Kantenzahl <math>n</math> ein Polygon, das möglichst viele Wächter benötigt. Bei einem Dreieck und einem Viereck hat man wenig Möglichkeiten, weil offensichtlich stets ein Wächter ausreicht. Bei einem Fünfeck ist das weiterhin richtig, wobei diese Einsicht nicht mehr ganz so offensichtlich ist:
<gallery class="float centered" perrow="4" caption="Spezialfall 5-seitiger Polygone">
art-gallery-51.svg|Abbildung 1
art-gallery-52.svg|Abbildung 2
art-gallery-53.svg|Abbildung 3
art-gallery-54.svg|Abbildung 4
</gallery>
Die ersten drei Abbildungen zeigen Stereotype aller möglichen Fünfecke: Jedes Fünfeck kann entweder keine, eine oder zwei [[Konvexe und konkave Funktionen|konkave]] Ecken besitzen, also Ecken die einen [[Innenwinkel]] von mehr als 180° beziehungsweise im [[Bogenmaß]] <math>\pi</math> haben. Das folgt aus der Tatsache, dass in jedem <math>n</math>-Eck die Summe der Innenwinkel gleich <math>\pi(n-2)</math> ist, im Fall <math>n=5</math> ist diese Summe <math>3\pi</math>. Sie lässt also höchstens zwei konkave Ecken zu.

Für das 4. Beispiel bräuchte man zwei Wächter: einen auf einem der Berührungspunkte der Dreiecke und einen weiteren im jeweils verbleibenden Dreieck. Allerdings würde man dort monieren, dass das Polygon „eigentlich“ neun Seiten hat, wenn man Überschneidungen verbieten möchte. Für gewöhnlich tut man das auch. Von nun an werden nur noch solche ''schneidungsfreien'' Polygone betrachtet.
<gallery class="float centered" perrow="4" caption="Weitere „kritische Graphen“ für kleine Kantenzahlen">
art-gallery-60.svg|Abbildung 5
art-gallery-61.svg|Abbildung 6
art-gallery-90.svg|Abbildung 7
art-gallery-12.svg|Abbildung 8
</gallery>Im Fall <math>n=6</math> (Abbildungen 5 und 6) tritt der Fall ein, dass Polygone existieren, die nicht von einem Wächter allein bewacht werden können, allerdings reichen stets zwei Wächter aus. Führt man solche Überlegungen weiter fort, kann man beobachten, dass nach jeweils drei weiteren Kanten ein weiterer Wächter nötig werden kann. Ein Polygon, das zu einer Kantenzahl eine maximale Wächterzahl benötigt, nennt man in dem Zusammenhang des Problems ein ''kritisches Polygon''.

== Satz von Chvátal ==
Der Beweis dafür, dass die oberen Beispiele tatsächlich kritische Polygone sind, also dass für neun- beziehungsweise zwölfkantige Polygone stets drei respektive vier Wächter ausreichen, ist ein Spezialfall folgenden Satzes:

{{Zitat
|Text=Zur Bewachung eines jeden überschneidungsfreien, geschlossenen und planaren Polygons mit <math>n</math> Seiten sind <math>\left\lfloor\tfrac{n}{3}\right\rfloor</math><ref group="A">Die Symbole <math>\lfloor\dots\rfloor</math> sind die [[Gaußklammer]]n. Sie runden den eingeschlossenen Ausdruck ab. Beispiel: <math>\lfloor\tfrac{11}{3}\rfloor=\lfloor\pi\rfloor=3</math></ref> Wächterpunkte stets ausreichend und manchmal notwendig.
|Autor=[[Vašek Chvátal]] (1975)
|ref=<ref name="chvátal">{{Literatur |Autor=V. Chvatal |Titel=A combinatorial theorem in plane geometry |Sammelwerk=J. Combin. Theory Ser. B |Band=18 |Nummer=39–41 |Datum=1975 |Seiten=32}}</ref>}}
Als Beweis gibt es im Wesentlichen zwei Versionen: Eine geometrische Variante, wie sie Chvátal zunächst angab, und eine [[graphentheoretisch]]e, die von S. Fisk angegeben wurde.<ref>{{Literatur |Autor=S. Fisk |Titel=A short proof of Chvátals watchman theorem |Sammelwerk=J. Combin. Theory Ser. B |Band=24 |Nummer=3 |Datum=1978 |Seiten=374}}</ref> Fisks Beweis benutzt einige wohlbekannte Resultate aus der [[Graphentheorie]], sodass der Beweis vergleichsweise kurz ist und als etwas ästhetischer gilt. Andererseits lässt er im Gegensatz zu Chvátal einige Verallgemeinerungen nicht zu.

=== Beweis ===
: (Nach Fisk) Zu einem geschlossenen planaren und überschneidungsfreien Polygon lassen sich geeignete Sehnen zwischen seinen Ecken ziehen, sodass das Polygon in, bis auf die Sehnen, paarweise [[disjunkt]]e Dreiecke zerfällt. So eine Zerlegung heißt naheliegenderweise [[Triangulation (Punktemenge)|Triangulation]] und ihre Existenz ist unter den gegebenen Voraussetzungen allgemein bewiesen. Weiterhin ist bekannt, dass sich die Ecken eines triangulierten Polygons unter Verwendung von nur drei Farben so [[Färbungsproblem|färben]] lassen, dass benachbarte Ecken verschiedene Farben haben.<ref>Für die Existenzbeweise von Triangulationen und der Färbung kann man [[#O’Rourke|O’Rourke (1987)]] studieren</ref> Jede Farbklasse ist dann offensichtlich eine gültige Wächtermenge; Insbesondere ist das für die kleinste Farbklasse wahr, die gerade <math>\left\lfloor\tfrac{n}{3}\right\rfloor</math> Ecken enthält.

Bereits vor dem Beweis dieses Satzes war bekannt, dass diese [[obere Schranke]], falls sie sich als gültig herausstellen sollte, nicht weiter verschärft werden könnte. Dazu betrachtet man folgende Folge von Graphen <math>G_n</math> mit <math>3n</math> Kanten. Jedes solche Polygon benötigt <math>n</math> Wächter.
[[Datei:art-gallery-counterexample.svg|mini|zentriert]]

Anlehnend an Fisks Konstruktionsbeweis entwickelten [[David Avis|Avis]] und [[Godfried Toussaint|Toussaint]] einen Algorithmus, der eine Wächtermenge der Größe <math>\left\lfloor \tfrac{n}{3}\right\rfloor</math> konstruiert.<ref>{{Literatur |Autor=D. Avis, G. T. Toussaint |Titel=An efficient algorithm for decomposing a polygon into star-shaped polygons |Sammelwerk=Pattern Recognition |Band=13 |Nummer=6 |Datum=1981 |Seiten=395–398 |Online=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.8231&rep=rep1&type=pdf Online] |Format=PDF |KBytes=}}</ref> Seine Laufzeit hängt im Wesentlichen davon ab, wie effizient eine Triangulation gefunden werden kann. Einige einfache Methoden realisieren das in quadratischer Zeit. In ihrem Artikel schlagen sie eine Version in <math>\mathcal{O}(n\log n)</math> vor.<ref group="A">Zur <math>\mathcal{O}()</math>-Notation siehe [[Landau-Symbol]]</ref> 1990 hat [[Bernard Chazelle|Chazelle]] einen Algorithmus mit Laufzeit <math>\mathcal{O}(n)</math> vorgestellt.

Die Färbung ist dann relativ leicht konstruierbar, wenn man annimmt, dass die Triangulation eine [[Datenstruktur]] übergibt, die alle [[Adjazenz]]informationen enthält. Im Allgemeinen kann das nicht gesichert werden. Die Leistung von Toussaint und Avis war es, eine Färbung in Linearzeit zu finden, allein unter der Benutzung einer Liste von Sehnenkanten der Triangulation.

=== Veranschaulichung des Beweises ===
Zur Veranschaulichung des Beweises wird das unten stehende Polygon betrachtet. Der erste Schritt besteht darin, das Polygon zu triangulieren (siehe Abbildung 1). Dann wendet man eine <math>3</math>-Färbung an (Abbildung 2) und stellt fest, dass es <math>4</math> rote, <math>4</math> blaue und <math>6</math> grüne Scheitelpunkte gibt. Die Farbe mit den wenigsten Scheitelpunkten ist blau oder rot, so dass das Polygon durch <math>4</math> Wächter abgedeckt werden kann (Abbildung 3). Dies stimmt mit dem Satz von Chvátal überein, da das Polygon <math>14</math> Scheitelpunkte hat und <math>\left\lfloor \tfrac{14}{3} \right\rfloor =4</math>.

<gallery class="float center" mode="nolines">
Triangulation of polygon.png|Abbildung 1
3-coloring of the polygon.png|Abbildung 2
Least color of 3-coloration.png|Abbildung 3
</gallery>

== Varianten und Verallgemeinerungen ==
Im Satz von Chvátal wird angenommen, dass die Wächter auf den Eckpunkten stehen. Die angegebene obere Schranke bleibt jedoch gültig, wenn die Beschränkung auf Wächter an den Ecken gelockert wird, um Wächter an jedem Punkt zuzulassen, der nicht außerhalb des Polygons liegt. Darüber hinaus wurden eine Reihe weiterer Verallgemeinerungen und Spezifikationen des ursprünglichen Satz von Chvátal untersucht.

=== Orthogonale Polygone ===
Ein wesentlicher Spezialfall des Wächterproblems ist die Einschränkung auf ''orthogonale Polygone''.<ref group="A">Andere gebrauchte Bezeichnungen dafür sind ''rektilinear'', ''isothetisch'' und ''rektanguloid''.</ref> Darunter versteht man Polygone, die ausschließlich die Innenwinkel <math>\tfrac{\pi}{2}</math> und <math>\tfrac{3\pi}{2}</math>, das sind 90° beziehungsweise 270°, annehmen. Solche Polygone betrachtet man in geometrischen Anwendungen, die stark an das [[kartesische Koordinaten]]system gebunden sind: darunter fallen Designprobleme [[Integrierte Schaltung|hochintegrierter Schaltungen]], Architektur und einige Algorithmen auf [[Rastergraphik]]en.<ref>[[#O’Rourke|O’Rourke]]: S. 31</ref>

Die zunächst naheliegende Vermutung, dass man mit dieser Einschränkung eine bessere Schranke an die Zahl der nötigen Wächter würde beweisen können, wurde 1980 durch einen Satz von [[Maria Klawe|Klawe]] und [[Daniel Kleitman|Kleitman]] bestätigt.<ref>{{Literatur |Autor=J. Kahn, M. Klawe, D. Kleitman |Titel=Traditional galleries require fewer watchmen |Sammelwerk=SIAM Journal on Algebraic and Discrete Methods |Band=4 |Datum=1983 |Seiten=194 |DOI=10.1137/0604020}}</ref> Sie zeigten die Existenz so genannter „''konvexer [[Quadrilateration]]en''“:<ref group="A">[[#O’Rourke|O’Rourke]] gebraucht den Begriff ''Quadrilateralization''.</ref> Das sind, analog zur Triangulation, Zerlegungen eines Polygons in konvexe Vierecke, indem Sehnen zwischen gewissen Ecken gezogen werden, die ganz im Polygon liegen. Ihr Beweis dazu ist sehr allgemein gehalten hält auch für eine entsprechende Aussage über Polygonen mit (endlich vielen) „Löchern“ oder „Überlappungen“.<ref group="A">Um Überlappungen zu Modellieren untersucht man Polygone als orthogonale, geschlossene [[Jordan-Kurve]]n auf einer [[Riemannsche Fläche|Riemannschen Fläche]].</ref> Es lässt sich vergleichsweise leicht zeigen, dass der [[Dualer Graph|Dualgraph]] einer konvexen Quadrilateration keinen der Kuratowskiminoren, also die Graphen [[Vollständiger Graph|<math>K_5</math>]] und [[Bipartiter Graph|<math>K_{3,3}</math>]], enthalten kann. Nach dem [[Satz von Kuratowski]] ist der Graph dann [[Planarer Graph|planar]] und nach dem [[Vierfarbentheorem]] vierfärbbar. Daraus folgt der Satz:

{{Zitat
|Text=Zur Bewachung eines jeden überschneidungs- und lochfreien sowie planaren und orthogonalen Polygons mit <math>n</math> Seiten sind <math>\left\lfloor\tfrac{n}{4}\right\rfloor</math> Wächterpunkte stets ausreichend und manchmal notwendig.
|Quelle=Satz von Klawe und Kleitman (1983)}}
Dass <math>\left\lfloor\tfrac{n}{4}\right\rfloor</math> Wächter manchmal notwendig sind, zeigt in Analogie zum Beispiel des allgemeinen Falls der „orthogonale Kamm“:

[[Datei:kamm.svg|zentriert|mini]]

Um die Existenz der konvexen Quadrilaterationen zu zeigen, nutzt der Beweis folgende aufeinander aufbauende Konzepte:

Eine „rechte“ und eine „linke“ Kante <math>R</math> und <math>L</math> eines Polygons <math>G</math> heißen ''benachbart'', falls
# Das Innere von <math>G</math> „links“ von <math>R</math> und rechts von <math>L</math> liegt.
# <math>R</math> und <math>L</math> „sehen“ einander (Das heißt, es existieren Punkte <math>r\in R</math> und <math>l\in L</math>, sodass die Verbindung <math>rl</math> ganz in <math>G</math> enthalten ist.)
# Der Abstand zwischen <math> R</math> und <math>L</math> zueinander ist unter den Bedingungen (1) und (2) minimal.
Daraus folgt sofort, dass zu einer Kante keine Nachbarin existieren muss, falls aber eine existiert so kann [[o. B. d. A.]] davon ausgegangen werden, dass diese eindeutig ist.<ref group="A">Man kann zu jedem orthogonalen Polygon <math>G</math> ein „beliebig nahes“ Polygon <math>G'</math> mit zu <math>G</math> identischer Quadrilateration finden, dessen Ecken paarweise verschiedene Koordinaten haben.</ref> Sind zwei benachbarte Kanten durch eine vertikale Kante miteinander verbunden, nennt man die drei Kanten zusammen ein ''Ohr''. Für „obere“ und „untere“ Kanten definiert man die Nachbarschafts- und Ohreigenschaft ganz analog.

In gegebenen Polygonen solche Ohren zu finden, ist deshalb interessant, weil man relativ leicht beweisen kann, dass jede konvexe Quadrilateration jedes Ohr enthalten muss. Allerdings muss man, um die Aussage des Wächtertheorems zu erhalten, das Konzept etwas allgemeiner fassen, denn nicht jedes Polygon muss ein Ohr enthalten.

Außerdem gibt es solche (Ohrenthaltenden) Polygone, die es gestatten, ein Polygon durch Abspaltung eines konvexen Vierecks auf ein oder mehrere kleinere, das heißt mit wenigstens einem Loch oder einer Kante weniger, zurückzuführen, und solche, die so eine Reduktion nicht gestatten. Diese nennt man ''reduzibel'' respektive ''irreduzibel''. Klawe und Kleitmann konnten zeigen, dass orthogonale Polygone
* entweder in diesem Sinne reduzibel sind
* oder ein Ohrenpaar (zwei Ohren, sodass die Verbindungskanten der benachbarten Kanten einander sehen) enthalten,
* oder zwei benachbarte Kanten enthalten, die kein Ohr bilden,
* oder unendlich viele Ecken haben müssen.

Für den Fall des Ohrenpaars und der benachbarten Kanten konnten sie auch eine Reduktion auf ein kleineres Polygon angeben und so [[Induktionsbeweis|induktiv]] die Existenz der vorgeschlagenen Quadrilaterationen für endliche Polygone begründen.
<gallery class="float centered" perrow="2" caption="Beispiele zu konvexen Quadrilaterationen" widths="500%">
quad1.svg|Konvexe Quadrilaterationen von orthogonalen Polygonen sind im Allgemeinen nicht eindeutig. Dieses Polygon hat kein Ohr.
quad2.svg|Das Viereck <math>\{6,7,8,9\}</math> ist ein Ohr. <math>\{2,3,4,5\}</math> ist ''kein'' Ohr, weil <math>\{2,3\}</math> mit <math>\{6,7\}</math> benachbart ist. Die in diesem Fall eindeutige konvexe Quadrilateration (eingezeichnet) kann nicht aus einer allgemeinen Triangulation konstruiert werden. (könnte das Dreieck <math>\{2,6,9\}</math> enthalten)
</gallery>

==== Algorithmen ====
Einen Versuch der Umsetzung des eben vorgestellten Beweises stellt [[Jörg-Rüdiger Wolfgang Sack|Sack]] in seiner Promotionsschrift von 1984 vor.<ref>{{Internetquelle |autor=Jörg-Rüdiger Wolfgang Sack |url=http://portal.acm.org/citation.cfm?id=911535 |titel=Rectilinear computational geometry |hrsg=ACM |datum=1984 |abruf=2010-03-11}} und {{Literatur |Autor=J. R. Sack, G. Toussaint |Titel=A linear-time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals |Sammelwerk=Proceedings 19th Conference on Communications, Control, and Computing |Datum=1981 |Seiten=21–30}}</ref>

Einen anderen Beweisansatz und einen daraus abgeleiteten Algorithmus hat [[Anna Lubiw|Lubiw]] 1985 entwickelt.<ref>{{Literatur |Autor=Anna Lubiw |Titel=Decomposing polygonal regions into convex quadrilaterals |Sammelwerk=Proceedings of the first annual symposium on Computational geometry |Verlag=ACM |Ort=Baltimore, Maryland, United States |Datum=1985 |ISBN=0-89791-163-6 |Seiten=97–106 |Online=[http://portal.acm.org/citation.cfm?id=323233.323247 online] |Abruf=2010-03-13 |DOI=10.1145/323233.323247}}</ref>

=== Festungsproblem ===
[[Derick Wood]] und [[Joseph Malkelvitch]] stellten in den 1970ern unabhängig voneinander die Frage nach zwei Verallgemeinerungen des Problems der Museumswächter: Anstelle Punkte zu finden, die das Innere eines Polygons bewachen, fragten sie nach Punkten, die das Äußere bewachen oder beides leisten. Wood prägte dafür die Namen '''Festungsproblem''' (für Bewachungsprobleme von äußeren Gebieten) und '''Problem des Gefängnishofs''' (für Probleme, bei denen beides bewacht werden soll). Das Festungsproblem ist insofern zufriedenstellend gelöst, als dass scharfe Aussagen zur benötigten Wächterzahl für ein Polygon in der Eckenzahl bewiesen werden konnten.
[[Datei:Argawall.svg|mini|Dieses orthogonale Polygon nach Aggarwal benötigt für <math>n=24</math> Ecken <math>7</math> Wächter um den Außenbereich zu bewachen.]]
{{Zitat
|Text=Zur Lösung des Festungsproblems sind <math>\bigl\lceil\tfrac{n}{2}\bigr\rceil</math> Eckenwächter manchmal notwendig und immer ausreichend
|Quelle={{Literatur |Autor=Joseph O’Rourke |Titel=Galleries need fewer mobile guards: A variation on Chvátal’s theorem |Sammelwerk=Geometriae Dedicata |Band=14 |Nummer=3 |Datum=1983 |Seiten=273–283 |DOI=10.1007/BF00146907}}}}
Ein Beispiel für die Notwendigkeit ist jedes konvexe Polygon. Dass das hinreicht, folgt aus folgender Konstruktion: Zu einem allgemeinen Polygon betrachte die [[konvexe Hülle]]. Trianguliere nun den Teil der Ebene, der innerhalb der konvexen Hülle, jedoch außerhalb des Polygons liegt. Wähle einen künstlichen Knoten <math>v_\infty</math> und verbinde alle Punkte der konvexen Hülle mit ihm. An einem beliebigen Knoten <math>x</math> der konvexen Hülle wird das Polygon nun „geöffnet“: <math>x</math> wird ersetzt durch Knoten <math>x'</math> und <math>x''</math> mit bis auf je eine Kante, die sie mit ihrem Nachbarn auf der konvexen Hülle verbinden, identischen Inzidenzen wie <math>x</math>. Der resultierende Graph mit <math>n+2</math> Knoten ist ein Triangulationsgraph, also [[Dreifarbenproblem|dreifärbbar]]. Man rechnet dann elementar aus, dass eine minimale chromatische Klasse, die <math>v_\infty</math> nicht enthält, höchstens von der Ordnung <math>\bigl\lceil\tfrac{n}{2}\bigr\rceil</math> ist. Die Übertragung des Beweises auf den orthogonalen Fall hat [[#Aggarwal|Aggarwal]] durchgeführt und er kommt darin zu dem Ergebnis, dass <math>\bigl\lceil\tfrac{n}{4}\bigr\rceil+1</math> Eckenwächter stets ausreichend und manchmal notwendig sind. Beide Beweise liefern Linearzeitalgorithmen zur Konstruktion einer entsprechenden Wächtermenge.

[[Datei:Festung-freie-wächter.svg|mini|Für <math>n=13</math> braucht man hier <math>5</math> freie Wächter.]]

Wenn man die Beschränkung aufhebt, dass Wächter ausschließlich an den Ecken platziert werden dürfen, kann man zeigen, dass dafür <math>\bigl\lceil\tfrac{n}{3}\bigr\rceil</math> stets ausreichend und manchmal nötig sind. Zum Beweis hat sich eine Idee von [[Thomas C. Shermer|Shermer]] als einsichtig erwiesen. Man konstruiert einen Triangulationsgraphen: Zwei zusätzliche Punkte werden rechts und links des Polygons hinreichend weit entfernt gewählt. Mit der konvexen Hülle kann dann ein Graph mit <math>n+2</math> Knoten erklärt werden, zu dem eine Triangulation existiert. In dem Fall, dass die Knotenzahl auf der konvexen Hülle gerade ist, ist dieser Graph dann 3-färbbar, die Zusatzknoten bekommen die Farbe Eins, die Punkte auf der Hülle dann alternierend Zwei und Drei. Ist sie ungerade, kann man mit einem Trick<ref>vgl. [[#O’Rourke|O’Rourke]] S. 152 ff.</ref> einen weiteren Knoten hinzunehmen und ist im geraden Fall. Eine kleinste chromatische Klasse enthält dann <math>\left\lfloor\tfrac{n+2}{3}\right\rfloor=\left\lceil\tfrac{n}{3}\right\rceil</math> Knoten.

== Resultate der Wächtertheorie im Überblick ==
(Quelle: O’Rourke<ref>[[#O’Rourke|O’Rourke]]: S. 267</ref>)

{| class="wikitable mw-collapsible" style="text-align:center"
! gesichteter Bereich
! Polygonstruktur
! Löcher
! Wächtertyp
! untere Schranke
! obere Schranke
! Diskussion 
|-
| rowspan="15"| Innen || rowspan="4"| allgemein ||   || rowspan="3"| Ecken || colspan="2" |<math>\lfloor\frac{n}{3}\rfloor</math> ||[[#Satz von Chvátal|Satz von Chvátal]]
|-
|   || colspan="2"| <math>r</math>|| [[#Beweisbild|Untere Schranke]], obere Schranke fast trivial<ref>{{Literatur |Autor=B. M Chazelle |Titel=Computational geometry and convexity |Ort=New Haven Yale Univ. |Datum=1980}}</ref>
|-
| <math>h</math> || <math>\lfloor\frac{n+h}{3}\rfloor</math> || <math>\lfloor\frac{n+2h}{3}\rfloor</math> || [[#Beweisbild|Untere Schranke für kleine <math>h</math>]]. Obere in [[#O’Rourke|O’Rourke]] S. 125 ff.
|-
|   || Kanten || <math>\lfloor\frac{n+1}{4}\rfloor</math> ||<math>\lfloor\frac{n}{3}\rfloor</math>||
|-
| rowspan="6"| sternförmig ||  || rowspan="2"| Ecken || colspan="2"| <math>\lfloor\frac{n}{3}\rfloor</math>|| [[#Weitere kritische Beispiele|Einige untere Schranken hier]]. Obere Schranken und Rest in [[#O’Rourke|O’Rourke]] S. 116 ff.
|-
|   || colspan="2"| <math>\lfloor \frac{r}{2}\rfloor+1</math>||
|-
|   || Linie || colspan="2" |<math>1</math>||
|-
|   || Diagonale || colspan="2"| <math>2</math>||
|-
|   || rowspan="2"| Kanten||<math>\lfloor\frac{n}{5}\rfloor</math>|| <math>\lfloor\frac{n}{3}\rfloor</math> ||
|-
|   || colspan="2"| <math>\lfloor\frac{r}{2}\rfloor +1</math>||
|-
| rowspan="5"| orthogonal ||   || rowspan="2"| Ecken || colspan="2"|<math>\lfloor\frac{n}{4}\rfloor = \lfloor\frac{r}{2}\rfloor +1</math>|| [[#Orthogonale Polygone|Orthogonale Polygone]]
|-
| <math>1</math> ||colspan="2"|<math>\lfloor\frac{n}{4}\rfloor</math>|| Analog zum allgemeinen Fall mit Löchern [[#O’Rourke|O’Rourke]] S. 140 ff.
|-
| <math>2</math> || Punkt ||colspan="2"|<math>\lfloor\frac{n}{4}\rfloor</math>||
|-
| <math>h</math> || Ecken ||<math>\lfloor\frac{n}{4}\rfloor</math>||<math>\lfloor\frac{n+2h}{4}\rfloor</math>||
|-
|   || Diagonal ||colspan="2"|<math>\lfloor\frac{3n+4}{16}\rfloor</math>|| [[#O’Rourke|O’Rourke]] S. 108 ff. Nach [[#Aggarwal|Aggarwal]].
|-
| rowspan="3"| Außen || rowspan="2"| allgemein ||   || Ecken || colspan="2"| <math>\lceil\frac{n}{2}\rceil</math>|| [[#Festungsproblem|Festungsproblem]]
|-
|   || Punkt || colspan="2"| <math>\lceil\frac{n}{3}\rceil</math>||
|-
| orthogonal ||   || Ecken ||colspan="2"| <math>\lceil\frac{n}{4}\rceil+1</math>|| [[#Festungsproblem|Festungsproblem]]
|-
| rowspan="3"|Innen und außen || allgemein ||   || rowspan="3"| Ecken || colspan="2"|<math>\lceil\frac{n}{2}\rceil</math> || [[#Füredi-Kleitmann|Füredi-Keitmann]]
|-
| konvex ||   || colspan="2"|<math>\lfloor\frac{n}{2}\rfloor</math> || [[#Füredi-Kleitmann|Füredi-Keitmann]]
|-
| orthogonal ||   || <math>\lceil\frac{n}{4}\rceil+1 </math> ||<math>\lfloor\frac{5n}{12}\rfloor+2</math>|| [[#Hoffmann-Kriegel|Hoffmann-Kriegel]]
|-
|colspan="7" style="text-align:left"|
;Legende
* <math>n</math> notiert die Eckenzahl. (Ecken von Löchern werden mitgezählt, falls welche vorhanden sind)
* <math>h</math> notiert die Anzahl der Löcher, falls vorhanden. Kein Eintrag bedeutet <math>h=0</math>.
* <math>r</math> notiert die Anzahl der konkaven Ecken. Eine Ecke heißt konkav, [[Genau dann, wenn|gdw]] ihr Innenwinkel größer als <math>\pi=180^\circ</math> ist.
* <math>\lfloor\dots\rfloor</math> und <math>\lceil\dots\rceil</math> sind die [[Gaußklammer|Gauß- bzw. Entierklammern]]. Sie runden den eingeschlossenen Ausdruck ganzzahlig auf bzw. ab.
|}

== Weitere kritische Beispiele ==
<gallery widths="300px" caption="Für sternförmige Polygone">
n sternförmig.svg|Beweisidee der unteren Schranke in der Eckenzahl für sternförmige Polygone: Für <math>n=24</math> Ecken braucht man hier 8 Eckenwächter. (Einen für jeden „Zacken“. Keine Ecke bewacht 2 Zacken oder mehr.)
r sternförmig.svg|Beweis der unteren Schranke in der Zahl de konkaven Ecken für sternförmige Polygone: Für je zwei Zacken braucht man einen Wächter an deren konkaven Ecken. Keine Ecke mehr als zwei Zacken.
sternförmig kantenwächter.svg|Beweisidee der unteren Schranke in der Eckenzahl für Sternförmige Polygone: Für <math>n=25</math> braucht man hier 5 Kantenwächter. Bei der Verallgemeinerung für größere n muss man die Zacken Derart spitz wählen, dass die durch jeden Zacken induzierten Strahlen für jeden Zacken eine andere Kante des „Kreises“ schneiden.
Diagonalenwächter sternförmig.svg|Beispiel eines sternförmigen Polygons, das zwei Diagonalenwächter benötigt. Zwei der vier möglichen Diagonalen sind eingezeichnet: Keine schneidet die grau hervorgehobene Kernregion. Dieses Beispiel wurde von Shermer und Suri entdeckt.
</gallery>
{{Anker|Beweisbild}}
<gallery widths="300px" caption="Schranke in der Zahl konkaver Ecken und Polygone mit Löchern.">
konvexe ecken.svg|Es gibt Polygonklassen, die für jede konkave Ecke einen Wächter benötigen.
hole1.svg|Für <math>n=8</math> Ecken werden 3 Wächter benötigt. Das linke Polygon geht auf Julian Sidarto zurück. Die beiden Rechten auf [[Tomas Shermer]].
hole2.svg|Hier braucht man 4 Wächter für<math>n=11</math> Ecken. Das Linke geht auf Shermer zurück; das Rechte auf Arthur Delcher. Diese und die vorherigen Beispiele mit Löchern wurden in einer Hausaufgabe eines Seminars von O’Rourke gefunden.
hole1.svg|<math>n=24</math> und drei Löcher brauchen 9 Eckenwächter.
</gallery>

== Literatur ==
* {{Anker|O’Rourke}}{{Literatur |Autor=J. O’Rourke |Titel=Art gallery theorems and algorithms |Verlag=Oxford University Press Oxford |Datum=1987 |Online=https://www.science.smith.edu/~jorourke/books/ArtGalleryTheorems/Art_Gallery_Full_Book.pdf |Format=PDF |KBytes=}}
* {{Anker|Aggarwal}}{{Literatur |Autor=A. Aggarwal |Titel=The art gallery theorem: its variations, applications and algorithmic aspects |Datum=1984}}
* {{Anker|Urrutia}}{{Literatur |Autor=J. Urrutia |Titel=Art gallery and illumination problems |Sammelwerk=Handbook of computational geometry |Datum=2000 |Seiten=973–1027}}
* {{Anker|Füredi-Kleitmann}}{{Literatur |Autor=Zoltán Füredi, D. J. Kleitman |Titel=The prison yard problem |Sammelwerk=Combinatorica |Band=14 |Nummer=3 |Datum=1994 |Seiten=287–300 |DOI=10.1007/BF01212977}}
* {{Anker|Hoffmann-Kriegel}}{{Literatur |Autor=Frank Hoffmann, Klaus Kriegel |Titel=Algorithms and Computation |Datum=1993 |Kapitel=A graph coloring result and its consequences for some guarding problems |Seiten=78–87 |DOI=10.1007/3-540-57568-5_237}}

== Anmerkungen ==
<references group="A" />

== Weblinks ==
{{Commonscat|Art gallery problem|Problem der Museumswächter}}

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmische Geometrie]]

Problem der Museumswächter - Versionsgeschichte

imported>Christian1985: /* Satz von Chvátal */