Tibor Szabó

FU Berlin

Mathias Schacht

University of Hamburg

Emo 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.

Gü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."