Monday, April 23, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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.