[Arbeitsgruppen | Forschung | Studium & Lehre | Allgemeines | Home | Suche | English]

Arbeitsgruppen und Lehrstühle

Forschung

Studium und Lehre

Allgemeines

Home

Suche

Fakultät für Informatik

 

Geometric Data Structures

Winter term 2018/19


Stefan Schirra


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:
Set 1


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), asymptotic analysis using the Big-Oh notation, and basic knowledge in computational geometry.

Literature:

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
Computational Geometry: Algorithms and Applications
Springer-Verlag, third revised edition, 2008.

Hanan Samet
Foundations of Multidimensional and Metric Data Structures
Morgan Kaufmann, 2006.


Elmar Langetepe, Gabriel Zachmann
Geometric Data Structures for Computer Graphics
A K Peters Ltd., 2006.




Pat Morin
Open Data Structures
AU Press, 2013.



Webmaster  -