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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Seminar zur Algorithmischen Geometrie FS08
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Seminar zur Algorithmischen Geometrie (251-0429-00L / 252-4201-00L) FS08

Upon request, this seminar will be held in English.

Bernd Gärtner, CAB G32.2, Tel: 01-632 70 26, lastname@inf.ethz.ch.
Michael Hoffmann, CAB G33.1, Tel: 01-632 73 90, lastname@inf.ethz.ch.
Emo Welzl, CAB G15.2, Tel: 01-632 73 70, lastname@inf.ethz.ch.

Contents

This seminar is held once a year and complements the course ``Algorithmische Geometrie''. Participation (exam passed) in one of the courses ``Algorithmische Geometrie'' or ``Approximate Methods in Geometry'' is necessary as a prerequisite. Students of the seminar will present original research papers on computational geometry, most of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area of computational geometry. This seminar is geared towards topics that are typically covered in a course like ``Algorithmische Geometrie''. In the Autum semester, we offer a similar seminar geared towards topics around the course ``Approximate Methods in Geometry''.

Dates

First meeting: Friday 22. 2. 2008 14:15-16:00, CAB G59.
The seminar is held as a block seminar on Fri Apr 18th 2008, 14:15-16:00, and Fri Apr 25th 2008, 14:15-16:00.

Program Apr 18th 2008

  • 14:15-15:00 : Line-segment intersection made in-place (Christoph Huber)
  • 15:15-16:00 : How to play a coloring game against a color-blind adversary (Zygmunt Malecki)

Program Apr 25th 2008

  • 14:15-15:00 : A Simple Streaming Algorithm for Minimum Enclosing Balls (Marcel Mueller)
  • 15:15-16:00 : Three problems about simple polygons (Christian Haene)

Proposed papers (list to be completed)

  1. C.-Y. Lo, J. Matousek, W. Steiger, Algorithms for ham-sandwich cuts, Discrete and Computational Geometry 11/1, 433-452, 1994. [DOI]
  2. J. Vahrenhold, Line-segment intersection made in-place, Computational Geometry: Theory and Applications 38, 213-230, 2007. [DOI]
  3. T. Chan, Three problems about simple polygons, Computational Geometry: Theory and Applications 35, 209-217, 2006. [DOI]
  4. K. Chen, How to play a coloring game against a color-blind adversary, Proc. 22nd Annual Symposium on Computational Geometry, 44-51, 2006. [DOI]
  5. H. Zarrabi-Zadeh, T. Chan, A Simple Streaming Algorithm for Minimum Enclosing Balls, Online Proc. 18th Canadian Conference on Computational Geometry, 2006 [PDF]
  6. N. Amenta, G. M. Ziegler, Shadows and Slices of Polytopes, Proc. of the twelfth annual symposium on Computational Geometry, 10-19, 1996 [DOI]

Conditions

A successful participation in the seminar requires the following:
  1. previous participation (exam passed) in one of the courses ``Algorithmische Geometrie'' or ``Approximate Methods in Geometry'';
  2. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  3. a satisfactory plenary talk;
  4. attendance at all other talks.
Last modified: $Date: 2008/03/31 10:31:49 $ by Michael Hoffmann. Valid HTML 4.0! Valid CSS!