Geometric Data Structures

Wintersemester 2023/24

Mo 17-19,   Tu 17-19   G29-335

Dozent: 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.

There is a moodle for this course. Please register for the course in

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.