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

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

How to describe an orthogonal polyhedron by cones.

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:   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