[home] - [up]

Lectures and Colloquia during the semester

Monday, June 28, 2004

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Jean-Daniel Boissonnat - I.N.R.I.A. Sophia Antipolis

Voronoi diagrams and surfaces

Abstract: In a first part of the talk, we will show some combinatorial and geometrical properties of Voronoi diagrams of well sampled surfaces. In particular, we will show that the medial axis of a set S can be approximated by a subset of the Voronoi diagram of a (good) sample E of S. We will also show almost linear bounds on the combinatorial complexity of the Voronoi diagram of E.

In a second part, we will introduce the concepts of Voronoi diagrams and Delaunay triangulations restricted to a surface. Given a surface S and a sufficiently dense sample E, the Delaunay triangulation of E restricted to S is a good approximation of S. It allows to approximate normals and curvatures, and, under some sampling conditions, is topologically equivalent to S.

We will show how to effectively construct such samples, which will result in a simple meshing algorithm with geometric and topological guarantees. Results on various types of surfaces will be presented.

Colloquium - 16:00

Kevin Buchin -Freie Universität Berlin

Insertion Orders for Incremental Construction of Delaunay Triangulations

Abstract: For constructing Delaunay triangulations, randomized incremental algorithms are widely used. However, randomness can be reduced without changing the asymptotic performance of the algorithm. We use this to define insertion orders which facilitate point location. Ordering points along a space-filling curve yields an expected linear-time algorithm for independent uniformly distributed points in the unit square.

[home] - [up] - [top]