#
Monday Lecture and Colloquium

**Monday, December 14, 2015 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

###
Benjamin Nill - Otto-von-Guericke-Universität Magdeburg

### Ehrhart theory - quo vadis?

*Abstract:*

A lattice polytope is a polytope whose vertices all lie in the integer lattice. Over 50 years ago, it was shown by Ehrhart that counting integer points in dilates of a lattice polytope leads to a polynomial function. The study of these Ehrhart polynomials of lattice polytopes is nowadays sometimes referred to as Ehrhart theory. In this talk I will try to give a (very incomplete) survey of recent research in Ehrhart theory and present some challenging open questions.

** Colloquium - 16:00**

### Tillmann Miltzow - Hungarian Academy of Science, Budapest

### Peeling the Cactus or how to count Triangulations in subexponential time

*Abstract:*

Joint with Daniel Marx.

Given a set of n points S in the plane, a triangulation T of S
is a maximal set of non-crossing segments with endpoints in S.
Let t(S) denote the number of all triangulations of S.
We present an algorithm that computes t(S) in
n^{O(√n)} time.
This improves over the previous best
algorithm of Alvarez and Seidel
with a running time O(2^{n} • n^{2}) [SoCG 2013].

Given a triangulation T, we define a decomposition of
T into disjoint nested cactus-graphs.
Our main tool is to use this decomposition to identify small
separators in an unique way.

Using techniques developed in previous papers,
we will demonstrate, how our algorithm can be adopted
to solve also 'decomposable' problems.
We will also argue that our algorithm can be adopted
to count other geometric structures as
cycle-decompositions, perfect matchings, etc.

If time permits, we will argue that a considerable improvement
on the running time requires different techniques to
the ones used so far in the literature.

Letzte Aktualisierung:
08.12.2015