*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 12
Freitag, 22.09.2000, 14.30–14.50 Uhr, WIL C 103

Über gleichlange Diagonalen in konvexen Polygonen

Peter Braß, FU Berlin, Institut für Informatik

Die Frage nach der maximalen Anzahl gleichlanger Diagonalen in einem konvexen n-Eck ist ein bekanntes offenes Problem der kombinatorische Geometrie. Anders als die ‘duale’ Frage nach der minimalen Anzahl verschiedener Diagonalenlängen, die bereits 1972 von Altman beantwortet wurde, und für die regelmäßige n-Ecke extremal sind, ist dieses Problem unerwartet schwierig. Wir kennen nur eine untere Schranke von 2n - 7, eine Konstruktion von Edelsbrunner und Hajnal, die aber sicherlich nicht extremal ist, und eine obere Schranke von O(n log n) von Füredi, die durch eine Reduktion auf ein kombinatorisches Extremalproblem für 0-1-Matrizen entstand. In einem anderen kombinatorische Modell erhielt ich gemeinsam mit Gy. Karolyi einen weiteren Beweis für dieselbe O(n log n)-Schranke, der jedoch ebenfalls nicht einfach war. In diesem Vortrag möchte ich nun einen gemeinsam mit J. Pach gefundenen, sehr einfachen und rein geometrischen Beweis dieser Schranke vorstellen.