Monday, November 29, 2010
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.