

Geometric Data Structures
Winter term 2018/19
Content:
We have a look at asymptotically efficient data structures, especially
data structures for geometric problems.
Among other structures,
we discuss heaps, augmented balanced binary search trees,
range trees, interval trees, priority search trees,
segment trees, and point location data structures.
Furthermore, we will discuss data structuring techniques like
making data structures (partially) persistent and
making data structures dynamic.
Slides:
Lecture 1
01 Sample Problems, Literature
02 Abstract Data Types
03 Basics
04 Dynamic Array, Amortized Analysis
Lecture 2
05 Binary Heap
06 Unordered Linked List as a Priority Queue
07 Leftist Heap
08 Binomial Heap
Lecture 3
08 Binary Heap Amortized Analysis
09 Fibonacci Heap

Exercises:
A SelfAdjusting Search Tree by Jorge Stolfi
Prerequisites :
Basic knowledge in algorithms and data structures (such as sorting algorithms,
balanced binary search trees, lists, and stacks), asymptotic analysis using
the BigOh notation, and basic knowledge in computational geometry.
Literature:
