Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

The Upcoming Monday Lecture and Colloquium

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

Imre Bárány - Budapest and London

Extremal problems for convex lattice polytopes

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

Eyal Ackerman - Technicon-Israel Institute of Technology, Haifa

Improved upper bounds on the reflexivity of point sets

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.