Geometric Arrangements and their Applications

Micha Sharir

Topics

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)

Book

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.