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
partners


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

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

Eyal Ackerman - Technicon-Israel Institute of Technology, Haifa


Improved upper bounds on the reflexivity of point sets

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.