Computational Geometry

Summer 2018

General

The lecture on 13th of June is canceled and will take place on 13th of July(Friday) instead.
The dates posted in the „Vorlesungszeichnis“ may be incorrect. Please refer to this webpage instead.

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 CHL
04.07 Range searching II CHL
11.07 Quadtrees CHL
13.07 Arrangements and duality
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
01.06 Well-Separated Pair Decomposition Problem Set #3
15.06 Voronoi & Delaunay Triangulation Problem Set #4
29.06 Point Location
16.07 Range Searching
20.07 Quadtrees

Solving the exercise sheets is voluntary but highly recommended. The solutions of the exercise are discussed in the exercise sessions.*/

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.