Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 08, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Tobias Christ
We consider a special class of art gallery problems inspired by wireless localization. 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 boundary 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. The goal is to use as few guards as possible. We sketch a NP-hardness proof of the vertex guard variant of the problem where guards must be located on vertices of P.
Joint work with Michael Hoffmann.
Automatic MiSe System Software Version 1.4803M | admin login