Prof. Dr. Jochen Rethmann
Hochschule Niederrhein
Fachbereich Elektrotechnik und Informatik
Reinarzstraße 49
47805 Krefeld

Fon: 0 21 51 / 8 22 - 46 33
Fax: 0 21 51 / 8 22 - 46 66
E-Mail: jochen.rethmann(at)hsnr.de

Letzte Änderung: --.--.----

Algorithmische Geometrie

Bachelor Technische Informatik
4. Semester

Inhalt

Scan-Line-Prinzip
Geometrisches Divide&Conquer
Segmentbäume
Intervallbäume
Prioritätssuchbäume
Hidden-Line-Elimination
Range-Bäume
Dynamische Bereichssuche
Konvexe Hülle
Fractional Cascading
Distanzprobleme/Voronoi-Diagramme

Literatur

Algorithmische Geometrie

Klein: Algorithmische Geometrie. Springer Verlag.
de Berg, van Kreveld, Overmars, Schwarzkopf: Computational Geometry. Springer Verlag.
Preparata, Shamos: Computational Geometry. Springer Verlag, 1985.
Edelsbrunner: Algorithms in Computational Geometry. Springer Verlag, 1987.
Mehlhorn: Datastructures and Algorithms (3) - Multidimensional Searching and Computational Geometry. Springer Verlag, 1984.

Bücher, die Kapitel über Algorithmische Geometrie enthalten

Ottmann, Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag.
Sedgewick: Algorithms. Addison-Wesley.

Implementierungen

dichtestes Punktepaar in der Ebene

Folien

to be continued ...

Übungen

to be continued ...

zurück zur Startseite