Geometric Arrangements and their Applications CGC Logo


Micha Sharir


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.

Last modified on 2001-02-01 by Sven Schönherr <>
!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!