Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login