Geometric computation and the art of sampling

Jiri Matousek
Department of Applied Mathematics
Charles University


In computer graphics, in numerical integration, and in many other applications, one needs uniformly distributed point sets to approximate continuous distributions. Random sets are not bad but there are better ways, at least if the dimension is not too large. For derandomizing algorithms in computational geometry efficiently, pseudo-random samples with suitable approximation properties have to be computed fast. For geometric range searching, uniformly distributed point sets are needed as a bad example in lower bound proofs. All of these topics have a common underlying theme: geometric discrepancy. Geometric discrepancy theory studies the question ``How uniformly can an n-point set be distributed in a given region of space?''. I plan to discuss some of the classical mathematical results and techniques, more recent combinatorial connections of geometric discrepancy, and relations to various subfields of computer science, such as indicated by the examples above.

Most of the material is covered by an excellent book by Chazelle just finished, and a book by the speaker, soon to be published by Springer-Verlag.