Computational Geometry
Summer 2018
General
- Lecturers: Dr. Tamara Mchedlidze, Dr. Chih-Hung Liu
- Assistant: Guido Brückner
- Lecture: Wednesday 14:00 - 15:30 in room SR301 (Informatikgebäude 50.34)
- Exercise: Monday 15:45 - 17:15 room SR236 and Friday 09:45 - 11:15 room SR301 (for exact dates look at the schedule below)
- Oral Exam: 30 minutes
- Examination Dates: August 14 (fully booked), October 16: 9:00-13:00. Please request a slot by email to: sekr-wagner@ira.uka.de.
Examination dates have been anounced.
Topic
Spatial data is processed in different areas of computer science, e.g., in computer graphics and visualization, in geographic information systems, in robotic, etc. Computational geometry is about the design and analysis of geometric algorithms and data structures. In this lecture frequently applied techniques and concepts of computational geometry are discussed.
Lecture
| Date | Topic | Slides | Literature | Lecturer |
|---|---|---|---|---|
| 18.04 | Introduction, Convex hulls | slides | Chapter 1[BCKO08], [CH96] | TM |
| 25.04 | Line segment intersection | slides | Chapter 2.1-2.2[BCKO08] | TM |
| 02.05 | Polygon triangulation | slides | Chapter 3[BCKO08] | TM |
| 09.05 | Linear programming | slides | Chapter 4.2-4.5[BCKO08] | TM |
| 16.05 | Well-separated pair decomposition (WSPD) | slides | Chapter 18-19[M12] | TM |
| 25.05 | Applications of WSPD, Visibility graphs | slides | Chapter 15[BCKO08] | TM |
| 30.05 | Voronoi diagrams & Delaunay triangulations I | slides | Chapter 7.1, 9.1-9.2 [BCKO08] | CHL |
| 06.06 | Voronoi diagrams & Delaunay triangulations II | same | Chapter 3 [AKL13] | CHL |
| 13.06 | Arrangements and duality | Moved to 13th of July | TM | |
| 20.06 | Point location | slides | Chapter 6.1-6.3 [BCKO08] | CHL |
| 27.06 | Range searching I | slides | Chapter 5 [BCKO08] | CHL |
| 04.07 | Range searching II | slides | Chapter 10 [BCK008] | CHL |
| 11.07 | Quadtrees | slides | Chapter 14 [BCK008] | CHL |
| 13.07 | Arrangements and duality | slides | Chapters 8.2-8.3[BCKO08], Chapters 14,15 [M12] | TM |
| 18.07 | Conclusion | TM&CHL |
Exercise sessions
Exercise sessions take place roughly every other week on Friday, but remember that changes are possible! We will regularly publish problem sets that are discussed in the exercise sessions.
To register for the oral exam we expect you to present an original solution for at least one problem in the exercise session.
| Date | Topic | Problem Set |
|---|---|---|
| 04.05 | Convex Hull & Line Segment Intersection | Problem Set #1 |
| 23.05 | Polygon Triangulation & Linear Programming | Problem Set #2 |
| 15.06 | Voronoi & Delaunay Triangulation | Problem Set #4 |
| 06.07 | Well-Separated Pair Decomposition & Range Searching I | Problem Set #3 & #5 |
| 20.07 | Range Searching II & Duality | Problem Set #6 |
Additional material
Java applet - Visual implementation of Fortune's Voronoi algorithm
Literature and Scripts
| [BCKO08] | M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry, 3rd ed., Springer-Verlag, 2008. |
| [HP08] | S. Har-Peled: Geometric Approximation Algorithms, Preprint, 2008. |
| [K05] | R. Klein: Algorithmische Geometrie, 2nd ed., Springer-Verlag, 2005. |
| [M02] | D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2002. |
| [M12] | D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2012. |
| [OR87] | J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, 1987. |
| [CH96] | T. Chan: Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, vol. 16, pp. 361-368, 1996 |
| [AKL13] | F. Aurenhammer, R. Klein, D. T. Lee: Voronoi Diagrams and Delaunary Triangulations, World Scientific, 2013. |