16.07.2012

Informatik-Kolloquium

Im Sommersemester 2012 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Montag, 16. Juli 2012, 17:00 Uhr, Turing-Hörsaal

Prof. Sergey Bereg (University of Texas at Dallas)

Art Gallery Problems

In 1973, Victor Klee posed the following question: How many guards are necessary, and how many are sufficient to patrol the paintings in an art gallery? Fisk's proof of the Art Gallery Theorem is a nice result in Combinatorial Geometry that initiated a new research direction in Computational Geometry.

We review some "old" and new results in this area concerning different types of guards (stationary vs. mobile) and different types of polygons (simple polygons, polygons with holes, orthogonal polygons etc.). Some open problems will be discussed, too.