Monday, July 14, 2008
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
In this survey talk I will present several extremal problems, and some solutions, concerning convex lattice polytopes. A typical example is to determine the smallest area that a convex lattice polygon can have if it has exactly n vertices.
Colloquium - 16:00
Given a set of $n$ points in the plane, its reflexivity is the minimum number of reflex vertices in a simple polygonalization of the set of points. It is conjectured that the reflexivity of any set of $n$ points is at most $n/4$. We show a $3n/7+O(1)$ upper bound, that improves the previously known $n/2$ upper bound. Using computer-aided abstract order type extension the upper bound can be further improved to $5n/12+O(1)$. We also present an algorithm to compute polygonalizations with at most this number of reflex vertices in $O(n \log n)$ time. joint work with Oswin Aichholzer and Balázs Keszegh.