Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 29, 2010

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005

Lecture - 14:15

Helmut Alt - FU Berlin

Parallel Algorithms for Geometric Problems

Considerable work has been done by the algorithms community during the 1980s concerning the design and analysis of parallel algorithms. Later, this effort has declined since efficient parallel algorithms for many standard problems had been found and computer industry found it more attractive to invest into accelerating sequential computers than to design novel parallel architectures. Meanwhile, the situation has changed again since speeding up sequential computers is getting close to its physical limits. Most computers nowadays have a multicore architecture and, especially, graphical processing units (GPU) allow for implementing highly parallel algorithms. The lecture will give a survey on the theory of parallel algorithms and elaborate on an efficient parallel algorithm for computing the depth of an arrangement of rectangles in the plane which was found recently by Torben Hagerup, Ludmila Scharf, and the speaker.

Colloquium - 16:00

Milos Stojakovic - University of Novi Sad

Consistent digital line segments

We will introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we will show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments. Joint work with Tobias Christ and Domotor Palvolgyi.