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 Exercise 1
11.11 Polygon Triangulation & Linear Programming Exercise 2
25.11 Range Searching Exercise 3 Part1 Part2
09.12 Voronoi & Delaunay Triangulation Exercise 4 Part 1 Part 2
16.12 Quadtrees Exercise 5
20.01 Duality & WSPD Exercise 6 Part 1 Part 2
10.02 Point Location Exercise 7

Changes are possible.

Exercise Sheets

Date Discussion Topic PDF
19.10 28.10 Convex Hulls & Line Segment Intersection Exercises 1
02.11 11.11 Triangulation of Polygons & Linear Programming Exercises 2
16.11 25.11 Range Queries Exercises 3
30.11 09.12 Voronoi Diagrams & Delaunay Triangulation Exercises 4
14.12 16.12 Quadtrees Exercises 5
11.01 20.01 Duality & WSPD Exercises 6
26.01 10.02 Point Location Exercises 7

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