November 7, 2022

A scientific celebration of the

80th birthday of Martin Aigner

Zuse Institute Berlin

Lecture Hall

14.00

arrival and refreshments

15.00

On a few Random Extremal and Ramsey-Type Problems

Mathias SchachtMathias Schacht

University of Hamburg

15.40

break with coffee and cake

16.20

Random Order Types of Point Sets

Emo WelzlEmo Welzl

ETH Zürich

The investigation of properties of random point sets has a long history, dating back to at least 1865 when J. J. Silvester posed his famous Four Point Problem. Clearly, properties depend on the underlying distribution, most prominently represented in the literature are sets obtained by sampling points uniformly from a convex region. Recently, with Xavier Goaoc, we looked at a more combinatorial distribution, namely point sets chosen uniformly from all simple order types of a given size. Roughly speaking, an order type is a class of point sets that cannot be discriminated by a typical convex hull algorithm (based on sidedness queries: "Does point p lie to the left of the oriented line through points q and r"). That is, the distribution is uniform on all possible inherently different inputs of convex hull algorithms. Among others, it can be shown that when sampling e.g. points uniformly from a disk in the plane, then the resulting order types are concentrated among all order types. In other words, one encounters only a vanishingly small part of all possible inputs to convex hull algorithms. In the course of the proofs one meets projective geometry, Felix Klein's characterization of subgroups of SO(3) (3-d rotation group), the Hairy Ball Theorem from topology, and Hadwiger's Transversal Theorem.

17.00

Proofs from THE BOOK - an adventure

Günter M. ZieglerGünter M. Ziegler

FU Berlin

In the summer of 1994, Martin returned from a Graph Theory meeting in Oberwolfach, where he had met Paul Erdős, and confronted me with the idea to write up our modest version of "Proofs from THE BOOK."

17.40

Sekt

Sabrina Nordt,
Olaf Parczyk,

Christoph Spiegel and
Tibor Szabó