Algorithms for Geometric Problems

Abstract

We discuss a selection of simple combinatorial algorithms for geometric problems. Such algorithms and problems are characterized by the fact that they deal with geometric primitives such as points and lines, for example in the Euclidean plane.

Objective

To get an overview over some of the fundamental problems in computational geometry. To get a taste of the relevant techniques and the challenges that arise when designing algorithms for geometric problems. To get some experience in giving a clear, accurate, and hopefully exciting presentation in front of a live audience.

Content

In this seminar, we will give an overview over some of the basic problems and techniques that are relevant to the field of computational geometry. That is, we will study combinatorial algorithms for problems where either the input or the output (or both) consists of geometric objects such as points, line segments, triangles, circles, polygons, triangulations, convex hulls, and more. For the sake of easy visualization, we will mostly consider problems in two (or maybe three) spatial dimensions. Each participant will study one specific topic from either a scientific publication or a section/chapter of a textbook, and will give a presentation about it. The available topics will be selected in such a way that they are easy to understand and appreciate for anyone who is familiar with the basic ideas and techniques of algorithm design, as taught in the Bachelor's program.

Resources