Monday, July 14, 2008
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
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
Abstract:
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.