Monday, January 3, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Lecture - 14:15
The frequency allocation problem is motivated by a study of wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells and edges representing conflicts between the cells. In each vertex we have a certain number of requests, each active for some time period. Each of the requests must be assigned a frequency so that no two requests in the same or adjacent vertices can share a frequency if they overlap in time. The objective is to minimize the total number of used frequencies. In this talk we present some of the results focusing on the case of line and bipartite graphs. Even in these simple cases the problem is surprisingly difficult and leads to interesting combinatorial questions. (Joint work with Marek Chrobak and Lukasz Jez.)
Colloquium - 16:00
We show that Delaunay triangulations and compressed quadtrees are equivalent structures. More precisely, we give two algorithms: the first computes a compressed quadtree for a planar point set, given the Delaunay triangulation; the second finds the Delaunay triangulation, given a compressed quadtree. Both algorithms run in deterministic linear time on a pointer machine. Our work builds on and extends previous results by Krznaric-Levcopolous Buchin-Mulzer.
As a corollary, we obtain deterministic versions of many previous algorithms related to Delaunay triangulations, such as splitting planar Delaunay triangulations, preprocessing imprecise points for faster Delaunay computation, and transdichotomous Delaunay triangulations.