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!

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.