(Geometric) Data Structures

Stefan Schirra Stundenplan

Announcements:
From now on the regular course takes place Wednesday, 11:05 - 12:35 in room G22A-208!
The additional exercises take place Wednesday, 9 am - 11 am, in G22A-004!
Additional exercises (replacing a Thursday exercises) will take place Friday June 8, 9 - 11, G22A-208!
Exam dates are Jul 19, Jul 31, Aug 1, and Sep 27. Please sign in at ISG office.

Slides:

Lecture 1 (white bg) Lecture 2 (white bg) Lecture 3 (white bg) Lecture 4 (white bg)

Lecture 5 (white bg)   Lecture 6 (white bg)   Lecture 7 (white bg)   Lecture 8 (white bg)

Lecture 9 (white bg)   Lecture 10 (white bg)   Lecture 11 (white bg)   Lecture 12 (white bg)

Lecture 13 (white bg)   Lecture 14 (white bg)   Lecture 15 (white bg)   All lectures (white bg)

Exercises:

Homework exercises 1 Homework exercises 2 Homework exercises 3 Homework exercises 4

Homework exercises 5   Homework exercises 6   Homework exercises 7   Homework exercises 8

Homework exercises 9   Homework exercises 10   Homework exercises 11   Homework exercises 12

Homework exercises 13   note: exercise 13.4   moved to 14.2   Homework exercises 14

Purpose:
The purpose of this course is to introduce students to efficient data structures, especially for geometric problems.

Content:
First we will have a closer look at binary search trees (including splay trees, i.e., self-adjusting trees) and then move on to classical geometric data structures like range trees, interval trees, priority search trees, segment trees, binary space partitions, quad- and octrees, and point location data structures. Furthermore, we will discuss data structuring techniques like making data structures (partially) persistent, making data structures dynamic, and fractional cascading.

A Self-Adjusting Search Tree by Jorge Stolfi

Prerequisites:
Basic knowledge in algorithms and data structures (such as sorting algorithms, balanced binary search trees, lists, and stacks), and in asymptotic analysis using the Big-Oh notation.

Literature:

			Elmar Langetepe, Gabriel Zachmann Geometric Data Structures for Computer Graphics A K Peters Ltd., 2006.
			Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf Computational Geometry: Algorithms and Applications Springer-Verlag, second edition, 2000.