Geometric Algorithms (2IMA15)

The course page for this course is on canvas.

Some general information about the course can be found below. (All of this information is also on canvas.) If you are considering taking the course, please in particular check the prerequisites.

Course Information:

In many areas of computer science such as robotics, computer graphics, virtual reality, and geographic information systems, it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study techniques and concepts needed for the design and analysis of geometric algorithms and data structures. Each technique and concept will be illustrated on the basis of a problem arising in one of the application areas mentioned above.

Goals:

At the end of this course participants should be able

• to decide which algorithm or data structure to use in order to solve a given basic geometric problem,
• to analyze new problems and come up with their own efficient solutions using concepts and techniques from the course.

Prerequisites:

In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know:

• O-notation, Ω-notation, Θ-notation; how to analyze algorithms
• Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc.
• Basic probability theory: events, probability distributions, random variables, expected values etc.
• Basic data structures: linked lists, stacks, queues, heaps
• (Balanced) binary search trees
• Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort
• Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths)

Assessment:

Regular homework assignments (60%) and a course project (40%). More details can be found on canvas. To give an impression of what is expected per week, an example of an assignment can be found here.

Literature:

Most of the lectures are based on material from the book:

[BKOS] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.Computational Geometry: Algorithms and Applications (3rd edition). Springer-Verlag, 2008.