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:
 Basics.
Convex Hull I ([B1]: pp 15.)
Lec.1
 Convex Hull II ([B1]: pp 617. [B3]: Ch.3. [P1]:Chan's algorithm)
Lec.2
 Line segment intersection ([B1]: pp 1929)
Lec.3
 Art gallery and triangulations I ([B1]: pp 4549)
 DCEL ([B1]: pp 2933)
Triangulating a simple polygon I ([B1]: pp 4955)
Lec.5
 Triangulating a simple polygon II ([B1]: pp 5558)
 Shortest Paths in Simple Polygons I
(Notes)

Shortest Path II / Introduction to Linear Programming

LP Incremental I ([B1]: pp 7176)

LP Incremental II: Randomized ([B1]: pp 7679)
Smallest Enclosing Disk ([B1]: pp 8689)

Point location: Trapezoidal Maps I ([B1]: pp 121128)

Point location: Trapezoidal Maps II ([B1]: pp 128137)

Voronoi Diagrams I ([B1]: pp 147152)

Fortune's sweep I ([B1]: Ch. 7.2)

Fortune's sweep II ([B1]: Ch. 7.2)
Orthogonal range searching: kdtrees ([B1]: Ch. 5.2)
Exercises:
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)
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. AddisonWesley, 1997.
[B3] J. O'Rourke. Computational Geometry in C. Cambridge University Press, 1998. (2nd ed.).
[B4] H. Edelsbrunner. Algorithms in Combinatorial Geometry. SpringerVerlag. 1987.
[B5] J.D. Boissonnat, M. Yvinec. Algorithmic Geometry. Cambridge
University Press, 1998.
[B6] F.P. Preparata, M.I. Shamos. Computational Geometry: An Introduction. SpringerVerlag New York, 1985.

[P1] T. Chan, Optimal outputsensitive convex hull algorithms in two and three dimensions.
Discrete & Computational Geometry, Volume 16, Issue 4, pp 361368.
(http://link.springer.com/content/pdf/10.1007%2FBF02712873)