## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, January 08, 2008, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Tobias Christ

## A Lower Bound Example for the Wireless Localization Problem

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.

Information for students and suggested topics for student talks