Discrete and Computational Geometry (DCG)

3VO MAT.414UF + 1UE MAT.415UF, winter term 19/20

The course will be held in English.

For further information (for example course times) see also the official TUGOnline pages of the lecture and the exercises part.

Course material

Here will be an overview/schedule of the content of the course, including some slides. More information to come during the term.

• October 3: Introduction and overview; Convex Hulls: Part 1

• October 10: Convex Hulls: Part 2; Basic Theorems for (Point) Sets: Part 1

• October 17: Basic Theorems for (Point) Sets, including exercises.

• October 24/31: Triangulations Part 1 (Homework on last page)

• November 7: Triangulations Part 2: Delaunay Triangulations (Exercises on last two pages)

• November 14: Delaunay Triangulations, Voronoi Diagrams

• November 28: Order Types: Part 1

• December 5: Order Types: Part 2

• December 12: Finish Order Types; Line Arrangements

• January 09: Chromatic Number of the Plane

• January 16: Simple Drawings and Rotation Systems Part I.

• January 23: Simple Drawings and Rotation Systems Part II.

• January 30: Simple Drawings and Rotation Systems Part III.

Exams

Attention: First exam for the VO changed to February 5 2020, see TUGOnline.

Literature and Links

Here are some literature references.

• M. de Berg, O. Cheong, M. van Kreveld , and M. Overmars. Computational Geometry. Algorithms and Applications (third edition). Springer, Berlin, 2008.

• S.L. Devados and J. O’Rourke. Discrete and Computational Geometry. Princeton University Press, Princeton, 2011.

• P. Brass, W.O.J. Moser, and J. Pach. Research Problems in Discrete Geometry. Springer, New York, 2005.

• O. Aichholzer, B.Jüttler. Einführung in die angewandte Geometrie. Birkhäuser, Reihe Mathematik Kompakt, Springer Basel, 2014.

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms (third edition). The MIT Press, Cambridge, 2009.

• F. Aurenhammer, R. Klein, and D.T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Co. Pte. Ltd., 2013.

• J. Matoušek. Lectures on Discrete Geometry, Springer Graduate Texts in Mathematics