Geometric Data Structures

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

• point location data structures
• (partially) persistent search trees
• searching in similar lists (fractional cascading)
• (augmented) binary search trees
• range trees
• interval trees
• priority search trees
• segment trees
• binary space partitions
• quadtrees
• dynamic convex hull in the plane

Exercises:
Exercise 1
Exercise 2

Audience:
computer science (Hauptstudium and master), computational visualistics (Hauptstudium and master)

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:
Recommended further readings.