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 Website!!
10th Assignment is out!
11th Assignment is out!
12th Assignment is out! This is the last assignment.
On Monday, 24 June, we will have a lecture instead of the tutorial. On Friday, 28 June, we will have a tutorial instead of the lecture.

The exam will be on Wednesday, 17th July 2013, from 10–12 in room SR 006.
You can have one sheet of paper with notes with you during the exam.

There will be an additional tutorial session on Monday, 15th July 2013, from 12–14 in room SR 055.
The results of the exam are online. You can only access them through the department network. You can have a look at your exam on Friday, 19th July 2013, from 14–15 in room 114. If you would like to take the make-up exam to improve your grade, please write us an e-mail until August 1st.

The make-up exam will be an oral exam on Friday, 11th October 2013. If you signed up for the exam, you should receive an e-mail with your time slot. If not, please contact us by September 20th.
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)
  16. Orthogonal range searching: kd-trees query time , range trees ([B1]: Ch. 5.2, 5.3)
  17. Orthogonal range searching: range trees, improved query time ([B1]: Ch. 5.6)
    k-sets, Clarkson's theorem
  18. k-sets, Clarkson's theorem (Notes)
    Convex hulls in 3D: polytopes and convex hulls
  19. Convex hulls in 3D: randomized incremental construction (Notes)
  20. Convex hulls in 3D: analysis (Notes)
  21. Delaunay triangulations ([B1]: Ch. 9.1)
  22. Delaunay triangulations, Voronoi diagrams, and convex hulls ([B1]: Ch. 9.2, 11.5)
  23. Kirkpatrick's data structure for planar point location
  24. Motion Planning I: point robots ([B1]: Ch. 13.1, 13.2)
  25. Motion Planning II: Minkowski sums and polygonal robots ([B1]: Ch. 13.3, 13.4)
  26. Arrangements and Duality ([B1]: Ch. 8.2, 8.3)
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)
  11. Ex.10 (due 17/06)
  12. Ex.11 (due 24/06)
  13. Ex.12 (due 01/07)
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)