Geometrische Datenstrukturen

Stefan Schirra Stundenplan 2V + 2Ü Die Vorlesung findet donnerstags statt, die Übung mittwochs.

Ziel und Inhalt:
Ziel der Vorlesung ist es, eine Einführung in effiziente Datenstrukturen zu geben, insbesondere solche für geometrische Probleme. Wir werden zunächst das bereits vorhandene Wissen über binäre Suchbäume auffrischen und erweitern und uns dann klassischen geometrischen Datenstrukturen wie

• range trees
• interval trees
• priority search trees
• segment trees
• binary space partitions
• quad- and octrees
• point location data structures

Prüfung:
mündlich; Termine: 23.7., 10.8., 29.9. Liste liegt im ISG-Sekr. aus.

Vorlesungsfolien:

Vorlesung 1 Vorlesung 2 Vorlesung 3 Vorlesung 4

Vorlesung 5 Vorlesung 6 Vorlesung 7 Vorlesung 8

Vorlesung   9 Vorlesung 10 Vorlesung 11 Vorlesung 12

Vorlesung   13 Vorlesung   14

Übungen:

Übung 1 Übung 2 Übung 3 Übung 4

Übung 5   Übung 6   Übung 7   Übung 8

Übung   9   Übung 10   Übung 11   Übung 12

Übung 13

A Self-Adjusting Search Tree by Jorge Stolfi

Voraussetzungen:
Grundwissen über Algorithmen und Datenstrukturen und über Algorithmische Geometrie.