(Geometric) Data Structures

Stefan Schirra Lectures: Friday 9-11, G22A-218 Exercises (Ivo Rössling): Thuesday 7:30 -9:00, G22A-211 Exercises start October 19 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

Please return evaluation questionnaires to ISG office or ISG mailbox on second floor in building 29. Thanks!

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.

Supplements::
figures on insert and delete restructuring in AVL trees
figures on insert and delete restructuring in red-black trees
figures on making data structures semi-dynamic with worst case bounds

Literature:

Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf Computational Geometry: Algorithms and Applications Springer-Verlag, second edition, 2000.