## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

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

 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

## 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).

Information for students and suggested topics for student talks