Monday, December 14, 2015
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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
nO(√n) time.
This improves over the previous best
algorithm of Alvarez and Seidel
with a running time O(2n • n2) [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.