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