Computational Geometry/Algorithmische Geometrie (SS 2013)

Description, Time Schedule, Location: kvv

News:
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)
Lectures:
  1. Basics.
    Convex Hull I ([B1]: pp 1-5.)
    Lec.1
  2. Convex Hull II ([B1]: pp 6-17. [B3]: Ch.3. [P1]:Chan's algorithm)
    Lec.2
  3. Line segment intersection ([B1]: pp 19-29)
    Lec.3
  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)
    Lec.5
  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)
Exercises:
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)

Literature:

[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.
(http://link.springer.com/content/pdf/10.1007%2FBF02712873)