





|
|
Geometrische Datenstrukturen
Wintersemester 2011/2012
Hinweis:
In der ersten Woche findet statt der
Übung eine zweite Vorlesung statt.
Die Vorlesung beginnt also am 12.10.!
Ebenso findet in der Vorweihnachtswoche und der ersten Woche des neuen Jahres
mittwochs statt Übung Vorlesung statt.
Am 17. Februar findet um 11:00 Uhr in Raum G29-335 eine Fragestunde
zu den Vorlesungen Topics in Algorithmics und Geometrische Datenstrukturen
statt.
Ziel und Inhalt:
Wir werden uns in der Vorlesung asymptotisch
effiziente Datenstrukturen anschauen, insbesondere solche für
geometrische Probleme.
Vorlesungsfolien:
Übungen:
A Self-Adjusting Search Tree by Jorge Stolfi
Voraussetzungen:
Grundwissen über Algorithmen und Datenstrukturen und in Algorithmischer
Geometrie.
Literaturhinweise:
 |
| |
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
Computational Geometry: Algorithms and Applications
Springer-Verlag, third revised edition, 2008.
Eine exzellente Einführung in die Algorithmische Geometrie.
Deckt die meisten Datenstrukturen ab, die wir behandeln werden.
|
 |
| |
Hanan Samet
Foundations of Multidimensional and Metric Data Structures
Morgan Kaufmann, 2006.
Ein umfassendes Werk zu geometrischen Datenstrukturen zu
einem angemessenen Preis.
|

|
| |
Elmar Langetepe, Gabriel Zachmann
Geometric Data Structures for Computer Graphics
A K Peters Ltd., 2006.
Deckt die meisten Datenstrukturen ab, die wir behandeln werden.
Enthält auch einen Abschnitt über Robustheitsprobleme beim
Implementieren geometrischer Algorithmen!
|
|