|Geometric Arrangements and their Applications|
The course presents several advanced topics in combinatorial and computational geometry, mostly related to the theory of arrangements of curves and surfaces and their applications. Some of the topics are: Davenport-Schinzel sequences, Lower envelopes, Cells and Zones, Randomization in combinatorial and computational geometry, Algorithmic applications of arrangements, k-sets, Incidences, Union of geometric objects, Vertical decompositions. (We will probably be unable to cover all these topics...)
Where and When
Fr 10-12, IFW B42 (Exercises: Mo 13-14, IFW C42)
(first course April 6, 2001)
The book ``Davenport Schinzel sequences and their geometric applications'' by M. Sharir and P. Agarwal (Cambridge University Press, 1995) covers a significant part of the material of the course.