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]