Das Problem der Museumswächter Antje Gottschalk 04.01.2012 Proseminar Das Buch der Beweise

Das Problem der Das Problem der MuseumswächterMuseumswächter

Antje Gottschalk04.01.2012

Proseminar „Das Buch der Beweise“

Einleitung

Das Problem der Museumswächter

Einleitung

• Fragestellung der Algorithmischen Geometrie• tritt auf:

- in der Robotik- in der digitalen Bildbearbeitung- bei Beleuchtungsproblemen- Beobachtung von Tierpopulationen- Aufstellung der Infrastruktur für Wetterbeobachtung/ Warnung vor Naturkatastrophen

• APX-Problem• aber es gibt scharfe obere Schranken für das Problem und seine Varianten• Im folgenden:

- Museumswächterproblem von V. Klee und dessen Beweis von S. Fisk- drei Varianten

„Wie viele Wächter braucht man zur Überwachung eines Museums ?“

Bedingungen: • die Wächter haben einen festen Standpunkt haben,• jeder Punkt ist im Sichtfeld eines Wächters,• die Wächter können sich um 360° drehen.

Victor Klee, August 1973, Konferenz in Stanford:

Die Fragestellung


WENN das Polygon konvex ist. Ein Wächter reicht aus.

ABER i.A. ist es ein beliebiges geschlossenes ebenes

UND…

Die Fragestellung


Grundriss des Museums = ein Polygon mit n Seiten

Abb.1: Eine konvexe Ausstellungshalle [1]

Abb.2: Weisman Art Museum, Minneapolis, USA [1] [2]

… es gibt ziemlich verwinkelte Museen!

Die Fragestellung


Beobachtung:

Die Vermutung


Die Vermutung

Geg.: Museum mit n = 3m Wänden.

Vermutung: • Für jedes n gibt es ein Museum mit n Wänden, für das man n/3 Wächter braucht.• Diese obere Schranke ist scharf.

• Punkt 1 kann nur von einem Wächter beobachtet werden, der im schattierten Dreieck steht (analog die Punkte 2,3,…,m) • alle Dreiecke sind disjunkt man braucht mind. m Wächter.• Wächter an den oberen Kanten der Dreiecke postieren m Wächter reichen aus

Satz. Für jedes Museum mit n Wänden reichen n/3 Wächter aus.

Der Museumswächtersatz


Beweis von S.Fisk (1978):

Schritt 1. Triangulierung des Polygons (Museumsgrundriss)

Schritt 2. 3-Färbung der Triangulierung

Schritt 3. Schlussfolgerung auf die obere Schranke

Der Museumswächtersatz/ Art Gallery Theorem(Aufgestellt und bewiesen von Vašek Chvátal, 1975)

Fisk‘s Beweis

Schritt 1. Triangulierung des Polygons P.

Definition. Die Triangulierung T eines einfachen Polygons P ist ein planarer Graph, der dadurch gebildet wird, dass man die Ecken von P mit soviel wie möglich sich nicht-kreuzenden, in P liegenden Diagonalen verbindet, bis der Innenraum in Dreiecke aufgeteilt ist.

Abb.3: Ein Museum mit n = 12 Wänden. [1] Abb.4: Triangulierung eines Museums mit n = 12 Wänden. [1]

Fisk‘s Beweis; Schritt 1; Triangulierung des Polygons; Definition


Satz. Für ein ebenes nicht-konvexes Polygon P existiert immer eine Triangulierung.

Beweis.

Fisk‘s Beweis; Schritt 1; Triangulierung des Polygons; Beweis


Induktionsanfang.

Induktionsvorraussetzung.

mittels Induktion über die Anzahl n der Ecken

n = 3 P ist ein Dreieck = P ist ein Triangulierung.

Der o.g. Satz gilt für ein n-Eck und alle Polygone mit weniger als n Ecken.

Induktionsschritt.

1. Irgendeine Diagonale d finden, die das n+1-Eck P in zwei Teile P1 und P2 zerlegt

2. Existiert d, dann haben t1 und t2 jeweils weniger als n+1-Ecken P1 und P2 können nach IV in Dreiecke zerlegt werden

P besteht aus allen diesen Dreiecken. P ist triangulierbar.



Für den Induktionsschritt, Teil 1: Irgendeine Diagonale d finden, die dieses n+1-Eck P in zwei Teile t1 und t2 zerlegt

1. Suche eine konvexe Ecke A des Polygonskonvex = der innere Winkel an A ist kleiner als 180°Innenwinkelsumme(P) = (n-2)*180° es ex. mind. eine konvexe Ecke ANach Schubfachprinzip ex. sogar mind. drei konvexe Ecken !

2. Betrachte Nachbarecken B und C von A1. Wenn Strecke BC innerhalb von P liegt Strecke BC ist Diagonale d.2. Wenn nicht

Dreieck ABC enthält weitere Ecken von P Verschiebung der Strecke BC Richtung A bis es die

letzte Ecke Z trifft, die in ABC liegt. Strecke AZ liegt im Inneren von P Strecke AZ ist Diagonale d.

Abb.5:Diagonale d finden[1]

Kann man dies auf den 3-dimensionalen Fall verallgemeinern ??

Fisk‘s Beweis; Schritt 1; Triangulierung des Polygons; 3D


Zerlegung in Tetraeder ohne zusätzliche Ecken

Antwort: NEIN, denn es gibt ein Gegenbeispiel, das Schönhard-Polyeder.

Das Schönhardt-Polyeder:

• entsteht aus einem Dreiecksprisma und Drehung des Deckels• Triangulierung ≙ Tetraeder muss das Bodendreieck und eine weitere Ecke im Deckel enthalten• solch ein Tetraeder existiert nicht

Abb.6:

[1]

Schritt 2. 3-Färbung der Triangulierung T.

Definition. Mit der 3-Färbung einer Triangulierung T ist die Zuordnung von Farben zu den Ecken von T gemeint, so dass zwei benachbarte Ecken niemals die gleiche Farbe haben.

Fisk‘s Beweis; Schritt 2; Färbung der Triangulierung; Definition


Abb.7: Triangulierung eines Museums[1] Abb. 8: 3-gefärbte Triangulierung eines Museums

Farbe AFarbe BFarbe C


Fisk‘s Beweis; Schritt 2; Färbung der Triangulierung ; Beweis

Satz. Jede Triangulierung T eines Polygons P ist 3-färbbar.

Beweis (mittels Induktion).

Induktionsanfang.

Induktionsvorraussetzung.

Induktionsschritt.

n = 3 P ist ein Dreieck = P ist 3-färbbar.

Der o.g. Satz gilt für ein n-Eck und alle Polygone mit weniger als n Ecken.

1. P wird trianguliert, P hat n+1 Ecken2. Wahl zweier beliebiger Ecken u,v von P, die durch eine Diagonale uv

verbunden sind3. Die Diagonale uv teilt P in zwei kleinere triangulierte Graphen P1 und P2

4. P1 und P2 enthalten jeweils weniger als n+1 Ecken5. Nach IV sind P1 und P2 3-färbbar

1. In beiden Färbungen hat u Farbe A und v Farbe B6. „Zusammenkleben“ von P 7. P ist 3-färbbar

Fisk‘s Beweis; Schritt 3; Schlussfolgerung auf die obere Schranke

Schritt 3. Schlussfolgerung auf die obere Schranke

Bisher gezeigt:


Ein geschlossenes, ebenes Polygon mit n Wänden

ist triangulisierbar 3-färbbar.Schritt 1 Schritt 2

Fisk‘s Beweis; Schritt 3; Schlussfolgerung auf die obere Schranke


Abb.8: 3-gefärbte Triangulierung eines Museums[1]

Farbe AFarbe BFarbe C

a, b, c entsprechen der Anzahl der Ecken pro Farbe (A, B, C), a, b, c n = die Gesamtzahl der Ecken, n n = a + b + c und a ≤ b ≤ c 3a ≤ n a ≤ n/3

Jedes Dreieck enthält eine Ecke der Farbe A Volle Überwachung jeder Dreiecksfläche Volle Überwachung der Grundfläche des gesamten Museums

Fazit: Die Anzahl der auf jeden Fall ausreichenden Wächter für einMuseum mit n Ecken ist n/3 .

Variationen und Erweiterungen1. Die Wandwächter (G. Toussaint)

Definition. Ein Wandwächter ist ein Wächter, der an einer Wand des Museums entlang läuft, und alles überwacht, was von irgendeinem Punkt der Wand aus zu sehen ist.

Antwort. • I.A. können n/4 Wächter nötig sein (siehe Abb.)• Vermutung: Diese Anzahl reicht auch aus (außer für einige kleine Werte von n). Ein Beweis ist nicht in Sicht.

Variationen und Erweiterungen 1


Frage. Wie viele solche „Wandwächter“ brauchen wir, um das gesamte Museum zu überwachen?

Abb. 9: Dieses Polygon hat n = 28 Seiten/Ecken (und 4m Seiten i.a. Fall). [1]

Variationen und Erweiterungen2. Orthogonale Polygone (Kahn, Klawe, Kleitman. 1980)



Definition. Ein orthogonales Polygon hat ausschließlich die Innenwinkel 90° und 270°.

Satz. Zur Bewachung eines jedem überschneidungs- und lochfreien sowie planaren und orthogonalenPolygons mit n Seiten sind n/4 Wächterpunkte stets ausreichend und manchmal notwendig.

Beweis des Bedarfs.• siehe Abbildung

Beweis der Notwendigkeit.• basiert darauf, dass jedes orthogonale Polygon in konvexe Quadrilaterale zerlegt werden kann• zeigt dann, dass der resultierende Graph 4-färbbar ist• Platzierung der Wächter an den Ecken mit der ‘wenigsten’ Farbe

Abb.10: Orthogonaler Kamm hat n=4m Seiten/Ecken [3]

m

Zusammenfassung



Form fest mobil

allgemein n/3 n/4

orthogonal n/4 (3n+4)/16

Tab.1: Zusammenfassung [6]

Benutzt man Wandwächter, braucht man ¼ weniger als feste Wächter.

Variationen und Erweiterungen3. Das Festungsproblem (D. Wood, J. Malkelvitch, 1970er, unabhängig voneinander)



Frage. Wie viele feste „Eckwächter“ brauchen wir, um die gesamte äußere Umgebung einer Festung zu überwachen?

Antwort.1) Einfache konvexe Polygone höchstens n/2 Wächter

2) Allgemeine Polygone P höchstens n/2 Wächter, denn1. Trianguliere die konvexe Hülle von P2. Verbinde alle äußeren Ecken mit einer neuen Ecke v∞

3. Teile einen Knoten x in x‘ und x‘‘4. Bilde Triangulierung T des gesamten Graphen5. 3-Färbung von T6. Platzierung der Wächter in den Ecken mit der ‚seltensten‘

oder ‘zweitseltensten‘ Farbe

3) Orthogonale Polygone höchstens n/4 +2 WächterAbb. 11: Das Festungsproblem [6]

Quellen

Quellen


[1] M. Aigner, G. Ziegler, Das Buch der Beweise, 3. Auflage, Springer, 2009, S. 263-266 [2] www.hs-karlsruhe.de/fileadmin/hska/GOEM/Baum_Studieninteressierte/goem_mathe10_koerner.pdf[3] http://de.wikipedia.org[4] http://eric.gruver.net/ArtGalleryProblems.html[5] D. Avis, G. T. Toussaint, An efficient algorithm for decomposing a polygon into star-shaped polygons, Pattern Recognition, 13, Nr. 6, 1981, S. 395-398. [6] http://www.cs.purdue.edu/homes/aliaga/cs635-10/lec-artgallery.pdf[7] http://www.austms.org.au/Publ/Gazette/2004/Nov04/mathellaneous.pdf

Vielen Dank für Eure Aufmerksamkeit !



Das Schubfachprinzip

Informell. Falls man n Objekte auf m Mengen (n,m > 0) verteilt, und n größer als m ist, dann gibt es mindestens eine Menge, in der mehr als ein Objekt landet. [3]

Vorstellung. Falls man eine bestimmte Anzahl von Schubfächern hat, und man mehr Objekte in die Fächer legt als Fächer vorhanden sind, dann landen in irgendeinem Schubfach mindestens zwei dieser Objekte. [3]



Das Festungsproblem: Allgemeine Polygone

1. Trianguliere die konvexe Hülle von P

2. Verbinde alle äußeren Ecken mit einer neuen Ecke v∞

3. Teile einen Knoten x in x‘ und x‘‘

4. Bilde Triangulierung T des gesamten Graphen5. 3-Färbung von T6. Platzierung der Wächter in den Ecken mit der ‚seltensten‘ oder

‘zweitseltensten‘ Farbe

Documents

Das Problem der Museumswächter Antje Gottschalk 04.01.2012 Proseminar Das Buch der Beweise