Monday, December 14, 2015
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.