November 6, 2006
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005
Lecture - 14:15
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
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)