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
partners


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)

Abstract:
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

Abstract:
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