Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 02, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Tobias Christ
Given a simple polygon P on n vertices and a number k the Natural Wireless Localization Problem asks to describe P as unions and intersections of k natural guards. A natural guard is either a plane angle defined by a vertex of P or a halfplane defined by an edge of P. As shown in MiSe-talks earlier this year, there is always a natural guarding for P using only n-2 guards and this bound is tight. In this talk we will sketch a polynomial reduction of the Vertex Cover Problem on graphs to a variant of the Natural Localization Problem where we not only consider one polygon but a finite union of polygons.
Automatic MiSe System Software Version 1.4803M | admin login