# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# The Upcoming Monday Lecture and Colloquium

November 6, 2006

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

### 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

### 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)