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, April 23, 2007

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

Lecture - 14:15

Gert Vegter - University of Groningen

Envelope surfaces (joint work with Nico Kruithof)

Objects in CAGD are sometimes approximated by or modeled as the union of a finite set of balls in space. In general, the surface formed by the boundary is not smooth on the transition between spheres. We introduce envelope surfaces, which are tangent continuous and wrap tightly around the union of the balls. This class of surfaces is an extension of Edelsbrunner's skin surfaces, which have been used for modeling and visualisation of molecules.
The surface is the boundary of the union of an infinite set of balls, obtained by interpolating the radii of the input balls. We show that, under certain conditions on this radius function, the approximating surface is tangent continuoous. By a special choice of this radius function we obtain a piecewise quadratic envelope surface, the patches of which are defined by a polyhedral subdivision of space.

Colloquium - 16:00

Disputation Maike Buchin - Freie Universität Berlin

All Pairs Shortest Paths in O(n^3/log n) Time

The all-pairs-shortest-paths problem is a well-studied problem in algorithm design. Given a weighted directed graph one wants to find the lengths of shortest paths between all pairs of vertices of the graph. A well known algorithm for this problem is the Floyd-Warshall-algorithm which solves the problem in O(n^3) time where n is the number of vertices of the graph. The Floyd-Warshall-algorithm uses dynamic programming. Several subcubic algorithms are also known. In this talk I will present a recent algorithm of Timothy Chan which runs in O(n^3/log n) time. This algorithm is interesting not only because it has the lowest known run time. In contrast to previously known subcubic algorithms it uses neither table-lookups nor word-RAM operations. Instead it relies on a simple geometric idea.

Letzte Aktualisierung: 17.04.2007