FYI (KMRS Seminar)

Random points and lattice points in convex bodies

Imre Barany

Hungarian Academy of Sciences & University College London

Hungarian Academy of Sciences & University College London

2014/08/25-08/26 Monday & Tuesday

4:00PM – 5:00PM Room 1409

4:00PM – 5:00PM Room 1409

Assume K is a convex body in R^d and X is a (large) finite subset of K. How many convex polytopes are there whose vertices belong toX? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of X) approximate K? In this lecture I will talk about these questions mainly in two cases. The first is when X is a random sample of n uniform, independent points from K. In this case motivation comes from Sylvester’s famous four-point problem and from the theory of random polytopes. The second case is when X is the set of lattice points contained in K and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar. The methods are, however, very different.