Combinatorial Geometry


Graduate Course in Mathematics and Computer Science
Wednesday, 4:15-6:15pm, room 6417
Offered by János Pach
Spring Term, 2003


Can one plant n trees in an orchard, not all along the same line, so that every line determined by two trees will pass through a third? This question raised by Sylvester in the last century, has generated a lot of interest among professional and amateur mathematicians. It led to the birth of a new mathematical discipline, which even Euclid would appreciate and which has close ties to convexity, number theory, and applications to computational geometry, computer graphics, robotics, etc. This course offers an introduction to this rapidly developing field, where combinatorial and probabilistic (counting) methods play a crucial role. We will learn how to apply combinatorial methods to geometric problems and algorithms.
Some familiarity with elementary combinatorics and probability theory is required. However, we will not build heavily on the material covered in my course given in the Fall semester.

Topics: Extremal graph theory, Repeated distances in space, Arrangements of lines and curves, Geometric graphs, Epsilon nets, Discrepancy theory, Applications in computational geometry.

Textbook: J. Pach and P. Agarwal: Combinatorial Geometry, Wiley, New York, 1995.