Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 26, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Michael Hoffmann
We consider a novel class of art gallery problems inspired by wireless localization that has recently been introduced by Eppstein, Goodrich, and Sitchinava. Given a simple polygon P, place and orient guards each of which broadcasts a unique key within a fixed angular range. In contrast to the classical art gallery setting, broadcasts are not blocked by the edges of P. At any point in the plane one must be able to tell whether or not one is located inside P only by looking at the set of keys received. In other words, the interior of the polygon must be described by a monotone Boolean formula composed from the keys. I will present a new upper bound for the general problem where guards may be placed anywhere by showing that any simple polygon on n vertices can be described using at most (4/5)n guards.
Automatic MiSe System Software Version 1.4803M | admin login