Computational Geometry/Algorithmische Geometrie (SS 2013)

Description, Time Schedule, Location: kvv

Webpage is up! 1st Assignment is out! 2nd Assignment is out! 3rd Assignment is out!
Turotial room change: 055 SR Informatik!
4th Assignment and Programming exercise are out!
5th Assignment is out!
6th Assignment is out!

Next Tutorial: Tue. 21.5, 12:40 (055 SR)

7th Assignment is out!
8th Assignment is out! (with correction!)
9th Assignment is out!

New webpage link !!! (The old link will not be maintained)
  1. Basics.
    Convex Hull I ([B1]: pp 1-5.)
  2. Convex Hull II ([B1]: pp 6-17. [B3]: Ch.3. [P1]:Chan's algorithm)
  3. Line segment intersection ([B1]: pp 19-29)
  4. Art gallery and triangulations I ([B1]: pp 45-49)
  5. DCEL ([B1]: pp 29-33)
    Triangulating a simple polygon I ([B1]: pp 49-55)
  6. Triangulating a simple polygon II ([B1]: pp 55-58)
  7. Shortest Paths in Simple Polygons I (Notes)
  8. Shortest Path II / Introduction to Linear Programming
  9. LP Incremental I ([B1]: pp 71-76)
  10. LP Incremental II: Randomized ([B1]: pp 76-79)
    Smallest Enclosing Disk ([B1]: pp 86-89)
  11. Point location: Trapezoidal Maps I ([B1]: pp 121-128)
  12. Point location: Trapezoidal Maps II ([B1]: pp 128-137)
  13. Voronoi Diagrams I ([B1]: pp 147-152)
  14. Fortune's sweep I ([B1]: Ch. 7.2)
  15. Fortune's sweep II ([B1]: Ch. 7.2)
    Orthogonal range searching: kd-trees ([B1]: Ch. 5.2)
You may solve the exercises in groups of two.
  1. Ex.1 (due: 15/04. You should be able to solve these if you want to take this course.)
  2. Ex.2 (due: 22/04.)
  3. Ex.3 (due: 29/04.)
  4. Ex.4 (due 06/05)
  5. Programming exercise (due 13/05)
  6. Ex.5 (due 13/05)
  7. Ex.6 (due 20/05)
  8. Ex.7 (due 27/05)
  9. Ex.8 (with correction in 3(c); due 03/06)
  10. Ex.9 (due 10/06)


[B1] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 2008. (3rd ed.).
[B2] R. Klein. Algorithmische Geometrie. Addison-Wesley, 1997.
[B3] J. O'Rourke. Computational Geometry in C. Cambridge University Press, 1998. (2nd ed.).
[B4] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag. 1987.
[B5] J.-D. Boissonnat, M. Yvinec. Algorithmic Geometry. Cambridge University Press, 1998.
[B6] F.P. Preparata, M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag New York, 1985.
[P1] T. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, Volume 16, Issue 4, pp 361-368.