Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 08, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Tobias Christ
We consider a variant of the classic art gallery problems, which is referred to as wireless localization problem, guard placement for point-in-polygon proofs or sculpture garden problem (GWOP07, problem 37). Let P be a simple polygon in the plane with n vertices. We are asked to place stations or guards in the plane, that broadcast a unique key within a fixed angular range. The edges of P do not block the broadcasts. We want to place the guards and fix their angles such that every point inside P can prove to be inside by giving the keys it receives and each point outside P cannot. This means that the interior of the polygon must be described by a monotone boolean formula composed from the broadcasts. Guards that are placed on a vertex of P are called vertex guards. If a vertex guard exactly covers the interior angle of polygon vertex, it is called natural. A guard placed anywhere on the line given by an edge of P and broadcasting within an angle of Pi to the inner side of the edge is called a natural edge guard.
We will give examples of polygons that cannot be covered by less than n-2 natural edge- and vertex guards and still need roughly (3/5)n guards in the general setting, where we allow all kind of guards.
Joint work with Michael Hoffmann and other GWOP07-participants.
Automatic MiSe System Software Version 1.4803M | admin login