Computational Geometry

Winter 2015/2016

General

  • 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

  1. Team 5 (Michael, Fotiso, Matthias: Pacman - Ghosts activate on smell)
  2. Team 4 (Mao, Wang, Sebastian G., Pacman - Ghosts activate on sight)
  3. Team 1 (Sebastian, Michael, Zhijia Song, Pacman - Collision Detection)

03.02.2016

  1. Team 3 (Niklas, Samuel, Secret Agent - Save the robot)
  2. Team 2 (Jerome, Tobias, Puzzle - Keep Away)

Lecture

Date Topic Slides Print version Literature Lecturer
19.10 Introduction, Convex hulls pdf pdf [BCKO08, Ch. 1], [CH96] DS
26.10 Line segment intersection pdf pdf [BCKO08, Ch. 2] DS
02.11 Polygon triangulation pdf pdf [BCKO08, Ch.3] TM
09.11 Linear programming pdf pdf [BCKO08, Ch.4.2-4.5] TM
18.11 Orthogonal range searching pdf pdf [BCKO08, Ch. 5] DS
23.11 Range searching II: Windowing queries pdf pdf [BCKO08, Ch. 10] DS
30.11 Voronoi diagrams pdf pdf [BCKO08, Ch. 7] TM
07.12 Delaunay triangulations pdf pdf [BCKO08, Ch.9.1-9.2] TM
14.12 Quadtrees pdf pdf [BCKO08, Ch. 14] DS
21.12 Class cancelled
28.12 Holiday
04.01 Holiday
11.01 Arrangements and duality pdf pdf [BCKO09, Ch.8.(2-3)], [M12, Lec.8,14,15] TM
13.01 Class cancelled
18.01 Well-separated pair decomposition (WSPD) pdf pdf [M12, Lec. 18+19]; More details on QTs and WSPD: [HP08] TM
25.01 Applications of WSPD, Visibility graphs pdf pdf [M12, Lec. 19; BCKO08, Ch. 15] DS
27.01 Point location pdf pdf [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 PDF
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