Computational Geometry
Winter 2015/2016
General
- Lecturer: Dr. Tamara Mchedlidze Dr. Darren Strash
- Assistant: Dr. Benjamin Niedermann
- Lecture: Monday 15:45 - 17:15 in room SR301 (Informatikgebäude 50.34)
- Exercise: Wednesday 15:45 - 17:15 in room SR301,
- Modules: Algorithmische Geometrie, Algorithm Engineering und Anwendungen, Design und Analyse von Algorithmen, Algorithmen der Computergrafik
- Credits: Master: 5 LP (Exception: 3 LP for module Algorithmen der Computergrafik), Diplom: 2 SWS
- Oral Exam: 30 minutes
- Dates: Feb. 23,24,25; Apr. 12,13,14;
- Timeslots: 9,9:30,10,10:30,11.
- Sign up: Enter available dates at doodle.com. See class e-mail for link.
News
- 19/10/2015: First lecture.
- 19/10/2015: Lecture topics are announced.
- 28/10/2015: First exercises.
- 02/11/2015: Projects announced.
- 16/11/2015: Nov. 16 class moved to Nov. 18.
- 18/11/2015: Project proposals are due (moved from 16/11/2015).
- 23/11/2015: Range Searching II moved to Nov. 23 lecture.
- 07/12/2015: Schedule shuffle:
- Quadtree lecture moved to Dec. 14
- Dec. 21 lecture cancelled
- Extra lecture to be given on Wednesday, Jan. 13
- Jan. 13 exercise moved to Jan. 20
- 12/01/2016: The lecture on Jan. 13 is canceled. The new schedule will be announced soon.
- 20/01/2016: Presentation schedule announced, see schedule below.
- 25/01/2016: Exam dates posted.
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.
Schedule
Presentations
The presentation order is as follows:
01.02.2016
- Team 5 (Michael, Fotiso, Matthias: Pacman - Ghosts activate on smell)
- Team 4 (Mao, Wang, Sebastian G., Pacman - Ghosts activate on sight)
- Team 1 (Sebastian, Michael, Zhijia Song, Pacman - Collision Detection)
03.02.2016
- Team 3 (Niklas, Samuel, Secret Agent - Save the robot)
- Team 2 (Jerome, Tobias, Puzzle - Keep Away)
Lecture
| Date | Topic | Slides | Print version | Literature | Lecturer |
|---|---|---|---|---|---|
| 19.10 | Introduction, Convex hulls | [BCKO08, Ch. 1], [CH96] | DS | ||
| 26.10 | Line segment intersection | [BCKO08, Ch. 2] | DS | ||
| 02.11 | Polygon triangulation | [BCKO08, Ch.3] | TM | ||
| 09.11 | Linear programming | [BCKO08, Ch.4.2-4.5] | TM | ||
| 18.11 | Orthogonal range searching | [BCKO08, Ch. 5] | DS | ||
| 23.11 | Range searching II: Windowing queries | [BCKO08, Ch. 10] | DS | ||
| 30.11 | Voronoi diagrams | [BCKO08, Ch. 7] | TM | ||
| 07.12 | Delaunay triangulations | [BCKO08, Ch.9.1-9.2] | TM | ||
| 14.12 | Quadtrees | [BCKO08, Ch. 14] | DS | ||
| 21.12 | Class cancelled | ||||
| 28.12 | Holiday | ||||
| 04.01 | Holiday | ||||
| 11.01 | Arrangements and duality | [BCKO09, Ch.8.(2-3)], [M12, Lec.8,14,15] | TM | ||
| 13.01 | Class cancelled | ||||
| 18.01 | Well-separated pair decomposition (WSPD) | [M12, Lec. 18+19]; More details on QTs and WSPD: [HP08] | TM | ||
| 25.01 | Applications of WSPD, Visibility graphs | [M12, Lec. 19; BCKO08, Ch. 15] | DS | ||
| 27.01 | Point location | [BCKO08, Ch. 6] | DS | ||
| 01.02 | Project Presentations | DS,TM,BN | |||
| 03.02 | Project Presentations | DS,TM,BN |
Exercise Starting on October 28th, the exercise sessions take place every second week on Wednesday. Exception: There is no exercise session on December 23rd but on December 16th.
| Date | Topic | Slides |
|---|---|---|
| 28.10 | Convex Hull & Line Segment Intersection | – |
| 11.11 | Polygon Triangulation & Linear Programming | – |
| 25.11 | Range Searching | – |
| 09.12 | Voronoi & Delaunay Triangulation | – |
| 16.12 | Quadtrees | – |
| 20.01 | Duality & WSPD | – |
| 10.02 | Point Location | – |
Changes are possible.
Exercise Sheets
| Date | Discussion | Topic | |
|---|---|---|---|
| 19.10 | 28.10 | Convex Hulls & Line Segment Intersection | – |
| 02.11 | 11.11 | Triangulation of Polygons & Linear Programming | – |
| 16.11 | 25.11 | Range Queries | – |
| 30.11 | 09.12 | Voronoi Diagrams & Delaunay Triangulation | – |
| 14.12 | 16.12 | Quadtrees | – |
| 11.01 | 20.01 | Duality & WSPD | – |
| 26.01 | 10.02 | Point Location | – |
Solving the exercise sheets is voluntary but highly recommended. The solutions of the exercise are discussed in the exercise sessions.
Projects
| Team | Topic | Supervisor |
|---|---|---|
| Team 1 | Pacman - Collision Detection | Benjamin |
| Team 2 | Puzzle - Keep Away | Darren |
| Team 3 | Secret Agent - Save the robot | Tamara |
| Team 4 | Pacman - Ghosts activate on sight | Benjamin |
| Team 5 | Pacman - Ghosts activate on smell | Tamara |
- Project proposals are due to 16.11.2015
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 |