#
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

*Abstract:*

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

*Abstract:*

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