Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Seminar Geometry: Combinatorics and Algorithms FS16 (263-4203-00L)

Bernd Gärtner, CAB G32.2, Tel: 044-632 70 26,
Michael Hoffmann, CAB G33.1, Tel: 044-632 73 90,
Alexander Pilz, CAB G38, Tel: 044-632 04 34,
Emo Welzl, CAB G39.2, Tel: 044-632 73 70,


This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some basic knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" or a comparable course is strongly encouraged.


First meeting: Friday Feb 26th 2016, 13:15, CAB G15.2.


All talks in CAB G15.2.

Topic and Papers

The seminar focuses on Combinatorial Representations of Point Sets: How can the structure of point sets be captured using a discrete representation rather than a representation by coordinates from a continuous domain?

A nice overview is provided by Goodman and Pollack in Allowable Sequences and Order Types in Discrete and Computational Geometry.


The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes
  1. getting an overview of the related literature;
  2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
  3. understanding the contents of the paper in all details;
  4. selecting parts suitable for the presentation;
  5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

  1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  2. a satisfactory plenary talk;
  3. attendance at all other talks.

Last modified: Wed Apr 27 09:55:55 CEST 2016 by Michael Hoffmann. Valid HTML 4.0!