Discrete Mathematics and Optimization Seminar
April 14th, 2009
Counting Crossing-free Configurations
MC 103, 4:00 PM
Emo Welzl
ETH Zurich.
Given a set P of n points in the plane, a triangulation of P is a maximal straight-line embedded crossing-free graph on P. We are interested in the number of such triangulations. If the points are in convex position, the question asks for the number of triangulations of a convex n-gon, first raised by Euler some 250 years ago. This was settled 80 years later by Lame. For general point sets, four points suffice to see that the number of triangulations varies with the actual positioning of the points. David Avis was the first to ask about the maximum possible number of triangulations for n points. This number was then shown to be bounded by c^n, c a constant, by Ajtai, Chvatal, Newborn, and Szemeredi. Later research (also triggered by interest in efficient encodings of triangulations) tried to get a better grasp of the constant c in this bound.

The talk first reflects on some of the early historical background and then presents some of the more recent results on triangulations (via random triangulations) of general point sets (joint work with Micha Sharir) and of the n by n lattice (joint work with Jiri Matousek and Pavel Valtr).