Computational Geometry/Algorithmische Geometrie (SS 2013)
Description, Time Schedule, Location:
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)
Convex Hull I ([B1]: pp 1-5.)
- Convex Hull II ([B1]: pp 6-17. [B3]: Ch.3. [P1]:Chan's algorithm)
- Line segment intersection ([B1]: pp 19-29)
- Art gallery and triangulations I ([B1]: pp 45-49)
- DCEL ([B1]: pp 29-33)
Triangulating a simple polygon I ([B1]: pp 49-55)
- Triangulating a simple polygon II ([B1]: pp 55-58)
- Shortest Paths in Simple Polygons I
Shortest Path II / Introduction to Linear Programming
LP Incremental I ([B1]: pp 71-76)
LP Incremental II: Randomized ([B1]: pp 76-79)
Smallest Enclosing Disk ([B1]: pp 86-89)
Point location: Trapezoidal Maps I ([B1]: pp 121-128)
Point location: Trapezoidal Maps II ([B1]: pp 128-137)
Voronoi Diagrams I ([B1]: pp 147-152)
Fortune's sweep I ([B1]: Ch. 7.2)
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.
- Ex.1 (due: 15/04. You should be able to solve these if you want to take this course.)
- Ex.2 (due: 22/04.)
- Ex.3 (due: 29/04.)
- Ex.4 (due 06/05)
- Programming exercise (due 13/05)
- Ex.5 (due 13/05)
- Ex.6 (due 20/05)
- Ex.7 (due 27/05)
- Ex.8 (with correction in 3(c); due 03/06)
- 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.