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, March 15, 2011, 12:15 pm

**Duration**: This information is not available in the database

**Location**: OAT S15/S16/S17

**Speaker**: Tobias Christ

Given an Internetcafe modeled by a 3D orthogonal polyhedron P, place guards at some of its vertices. A guard at a vertex v is a device which broadcasts a unique key within the cone locally defined by P at v. At any point in space one must be able to tell whether or not one is inside P only looking at the keys received. If one can prove to be inside the cafe, one is granted internet access, if one can not provide a valid set of keys, the access gets blocked. In other words, P must be described as a monotone Boolean formula composed from the guards. More abstractly, we want to describe P by a monotone formula over cones defined by polygon vertices. We are going to show that it is enough to put a guard on every second vertex of P, provided P is 3-regular (the graph defined by the edges and vertices of P is 3-regular). For this to make sense, we show first that the graphs of 3-regular polyhedra are always bipartite, so it is clear what is meant by "every second vertex". This is well-known for (topologically) simple polyhedra. (Then, the graph of P is planar and every cycle bounding a face is even. So it follows that the graph is bipartite.) But it is not so obvious for general 3-regular polyhedra, allowing handles (genus different from 0) and cavities (disconnected boundary).

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