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, May 21, 2007

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

Lecture - 14:15

Nina Amenta - UC Davis

Delaunay triangulations of points on manifolds

Like most spatial data structures, the Delaunay triangulation suffers from the ``curse of dimensionality". A classic theorem of McMullen says that the worst-case complexity of the Delaunay triangulation of a set of n points in dimension d is Theta(n^(ceiling(d/2))). The point sets constructed to realize this exponential bound are distributed on one-dimensional curves, while for points distributed uniformly in space the complexity is O(n). What about distributions of points on manifolds of dimension 1 < p < d? We consider sets of points distributed nearly uniformly on a polyhedral surfaces of dimension p, and find that their Delaunay triangulations have complexity O(n^((d-1)/p)).

Colloquium - 16:00

Ulrich Bauer - FU Berlin

Tube reconstruction & Gate stabbing

Parametric reconstruction of complex shapes from noisy data is a difficult task. We present the results of an industry cooperation aiming at reconstruction of bent tubes for reverse engineering.
We propose a moving least squares technique to find the spine curve of a pipe surface, and show a heurisic approach to approximating a curve by a G1 arc and line segment spline curve with minimum number of segments.
As an outlook, we show how circles and lines approximating a set of points can be represented by convex polyhedra. This could be a building block of an exact algorithm for finding an optimal arc spline approximation.

Letzte Aktualisierung: 08.05.2007