#
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

*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**

### Milos Stojakovic -
University of Novi Sad

### Consistent digital line segments

*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.