Monday, January 3, 2011
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett
Lecture - 14:15
Abstract:
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
Abstract:
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.