Monday, May 21, 2007
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.