Geometrische Datenstrukturen

Stefan Schirra Stundenplan 2V + 2Ü

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 vertiefen 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

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

Ü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 in Algorithmischer Geometrie.