#
The Upcoming Monday Lecture and Colloquium

**November 6, 2006**

Freie Universität Berlin

Institut für Informatik

Takustr. 9,

room 005

** Lecture - 14:15**

###
Emo Welzl - ETH Zürich

###
Lattice Triangulations

*Abstract:*

Given a finite point set, we consider the family of all
of its triangulations, i.e. the set of maximal crossing-free
geometric graphs on this point set. In particular, we
are interested in the cardinality of this family and in
the structure of the flip graph which has the triangulations as its
vertices, and two triangulations are adjacent if they
can be obtained from each other by a so-called edge flip.
We first provide a brief account of some results known and then
concentrate on triangulations of the n x n lattice {0,1,...,n}^2.

**Colloquium - 16:00**

###
Christian Knauer - FU Berlin

###
A Fixed-Parameter Algorithm for the Minimum Weight Triangulation
Problem Based on Small Graph Separators

*Abstract:*

In this talk we outline how small graph separators help to reduce the
running time of fixed-parameter algorithms for certain hard geometric
problems. We focus on the Minimum Weight Triangulation problem (MWT)
and present a fixed-parameter algorithm which computes for a set $P$
of $n$ points in the plane in $O(2^{O(\sqrt{k} log k)} * k\sqrt{k}n^3)
$ time a minimum weight triangulation. The parameter $k$ is the
number of points in $P$ that lie in the interior of the convex hull
of $P$. We will briefly sketch how the same idea can be used for
other hard geometric problems such as TSP.
(This is joint work with Andreas Spillner)