A scientific celebration of the
80th birthday of Martin Aigner
Zuse Institute Berlin
arrival and refreshments
A Mathematical Journey Lined with BooksTibor Szabó
On a few Random Extremal and Ramsey-Type ProblemsMathias Schacht
University of Hamburg
break with coffee and cake
Random Order Types of Point SetsEmo Welzl
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.
Proofs from THE BOOK - an adventureGünter M. Ziegler
Günter M. Ziegler
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."
Christoph Spiegel and Tibor Szabó