Department of Computer Science | Institute of Theoretical Computer Science | CADMO
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.
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