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 makeup exam
to improve your grade, please write us an email until August 1st.
The makeup exam will be an oral exam on Friday, 11th October 2013. If you
signed up for the exam, you should receive an email with your time slot.
If not, please contact us by September 20th.
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)

Orthogonal range searching: kdtrees query time , range trees ([B1]: Ch. 5.2, 5.3)

Orthogonal range searching: range trees, improved query time ([B1]: Ch. 5.6)
ksets, Clarkson's theorem

ksets, Clarkson's theorem
(Notes)
Convex hulls in 3D: polytopes and convex hulls

Convex hulls in 3D: randomized incremental construction
(Notes)

Convex hulls in 3D: analysis
(Notes)

Delaunay triangulations ([B1]: Ch. 9.1)

Delaunay triangulations, Voronoi diagrams, and convex hulls ([B1]: Ch. 9.2, 11.5)

Kirkpatrick's data structure for planar point location

Motion Planning I: point robots ([B1]: Ch. 13.1, 13.2)

Motion Planning II: Minkowski sums and polygonal robots ([B1]: Ch. 13.3, 13.4)

Arrangements and Duality ([B1]: Ch. 8.2, 8.3)
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)
 Ex.10 (due 17/06)
 Ex.11 (due 24/06)
 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. 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)