Seminar Computational Geometry and Graph Drawing HS12
(263-4203-00L)

Contents

This seminar is held once a year and complements the courses Computational Geometry, Discrete Geometry, and Graph Drawing. 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 some of the abovementioned courses (or similar courses) is strongly encouraged. It is also possible to take this seminar in parallel to the lecture Computational Geometry.

Dates

First meeting: Friday Sep 21st 2012, 13:15, CAB G15.2.

Schedule

• Nov 9, 13:15-14:15: Enrico Kravina
  Stefan Langerman and William Steiger, The Complexity of Hyperplane Depth in the Plane, Discr. Comput. Geom. 30(2), 299-309, 2002. [DOI]
• Nov 16, 13:15-14:15: Felix Weissenberger
  Nabil Mustafa, Hans Raj Tiwary and Daniel Werner, A Proof of the Oja-depth Conjecture in the Plane, EuroCG 2011. [Preprint]
• Nov 30, 13:15-15:15: Patrick Schnider/Lucas Dahinden
  Marc van Kreveld et al., Efficient Algorithms for Maximum Regression Depth, Discr. Comput. Geom. 39(4), 656-677, 2008. [DOI]

Conditions

The seminar is held in English. Each talk is 45min. plus 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.