Computational Geometry

Summer 2018

General

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 TM
02.05 Polygon triangulation TM
09.05 Linear programming TM
16.05 Arrangements and duality TM
25.05 Well-separated pair decomposition (WSPD) TM
30.05 Voronoi diagrams & Delaunay triangulations I CHL
06.06 Voronoi diagrams & Delaunay triangulations II CHL
13.06 Applications of WSPD, Visibility graphs TM
20.06 Point location CHL
27.06 Range searching I CHL
04.07 Range searching II CHL
11.07 Quadtrees CHL
18.07 Conclusion TM&CHL

Exercise sessions

Exercise sessions take place roughly every other week on Monday or Friday (starting on April 27th or later), 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 Slides
27.04. or 30.04. Convex Hull & Line Segment Intersection
? Polygon Triangulation & Linear Programming
? Range Searching
? Voronoi & Delaunay Triangulation
? Quadtrees
? Duality & WSPD
? Point Location

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