Seminar
Ausgewählte Kapitel der Graphentheorie: Wächterprobleme

Sommersemester 2006
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 0230 L 316


Zeichnung

Thema:

Wir stellen uns ein Museum als Polygon vor. Wächter sollen so in Ecken des Museums gesetzt werden, dass jeder Punkt im Museum von einem Wächter überblickt wird. Wie viele Wächter sind nötig? Für das Museum in der Abbildung z.B. sind die sechs roten Punkte eine legale Wächtermenge. Ist sechs für dieses Museum optimal?

Bei diesem und verwandten Problemen ist man an Schranken für die minimale Anzahl von Wächtern in Abhängigkeit von der Kompliziertheit des Polygons und an Algorithmen für die Plazierung der Wächter interessiert. Die Probleme sind auch dadurch reizvoll, dass ihre Analyse und Lösung in vielen Fällen aus einer Kombination von Geometrischen und Graphentheoretischen Methoden besteht.

Literatur:

Die Vorträge:

ThemaVortragende
Polygon Zerlegungen (O'R. Kap 1) Bastian Schilling
Schnelle und einfache Polygon Triangulierung (Seidel) Robert Luce
Gallerien mit inneren Wänden (Kündgen) und (Hlineny) Verena Richter
Orthogonale Polygone (O'R. Kap 2) Steffen Melang
Graphen Färbungen mit Anwendungen auf Wächterprobleme
(Hoffmann/Kriegel) und (Zhang/He) 		Mike Schülken
-entfällt-
Sichtbarkeitsgraphen (O'R. Kap 7) und (Assano/Ghosh/Shermer) und (?) Mareike Massow
Cornelia Dangelmayr
Äussere Sichtbarkeit (O'R. Kap 6) Stefanie Brose
Bewegliche Wächter (O'R. Kap 3) Gesine Koch

Termine

4. Mai Aufwärmtreffen, Thema die Probleme aus Art Gallery Theorems von Norman Do.

Termin für das Blockseminar 30.Juni-2.Juli, Ort: Berlin

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik im Hauptstudium.
       Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.

Zuletzt bearbeitet Mai 2006