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: CAB G51
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).
Automatic MiSe System Software Version 1.4803M | admin login