Vorlesung: Graphisch geometrische Algorithmen

In der Vorlesung werden Algorithmen zur Lösung graphisch-geometrischer Fragestellungen hauptsächlich im 2D aber auch im 3D behandelt. Wir beschränken uns dabei auf die wichtigsten Ergebnisse und Verfahren und stellen Techniken vor, die gelegentlich in der Praxis sehr nützlich sein können. Im Vordergrund stehen Probleme mit stückweise linearen Strukturen, wie etwa Punkten, Dreiecken, Polygonen sowie Punkt- und Streckenansammlungen. Ist die Anzahl der beteiligten Punkte, Strecken, usw. ausreichend groß, so kann bei ungünstiger Wahl eines Algorithmus die von der Objektanzahl n abhängende Rechenzeit Tmax(n) stark steigen. Wir zeigen, mit welchen algorithmischen Techniken und Datenstrukturen man solche Probleme effizient lösen kann.

Der Inhalt der Vorlesung ist wie folgt gegliedert:

1. Analyse graphisch-geometrischer Probleme und Algorithmen

Problemspezifikation, Problemklassifikation, Algorithmenmodell, lgorithmenkomplexität, untere Schranken für elementare Algorithmen, die Rundungsoperation, geometrische Definitionen

2. Punktlokalisation

Punktlokalisation in konvexen Polygonen, Punktlokalisation in Sternpolygonen, in allgemeinen Polygonen: mit Halbstrahlverfahren, mit monotonen Ketten, Algorithmus von Kirkpatrick

3. Schnittbestimmung

Schnitt isoorientierter und beliebiger Strecken, Schnitt einer Geraden mit einem Polygon, Clipping, Verbindungsgraphen, Mengenoperationen mit zwei Polygonen, Schnitt konvexer Polygone, Bestimmung aller Polygonschnittpaare, Schnitt von Rechteckmengen, Schnitt von Halbebenen

4. Hüllenbildung

Allgemeine Formulierung, Hüllobjekte von Punktmengen im R² und R³, konvexe Hülle eines einfachen Polygons, Durchmesser

5. Distanzbestimmung

Metrik, Voronoi-Diagramme, nächster Nachbar, minimale Punktpaare, minimaler spannender Baum

6. Triangulationsaufgaben

Triangulation von Polygonen: mit Algorithmus von Kong, Triangulation monotoner Polygone, mit Sweep-Verfahren und Sacktechnik, zeitoptimale Triangulation einfacher Polygone;
Triangulation von Punktmengen

7. Zellrastertechniken

rastergünstige Szenen, Punktlokalisation in Polygonen, Schnitt isoorientierter und beliebiger Strecken

Notice: Undefined index: show_script in /export/home/www/i31www/lehre/vorlesung_details.php on line 2

nach oben

Literatur:	A. Schmitt, O. Deussen und M. Kreeb: Einführung in graphisch-geometrische Algorithmen. Teubner, Stuttgart, 1996 F.P. Preparata und M.I. Shamos: Computational Geometry - An Introduction. Springer, New York 1985 Rolf Klein: Algorithmische Geometrie. Addison-Wesley, 1997
Hörerkreis:	Informatiker und Hörer anderer Fachrichtungen nach dem Vordiplom
Skript:	Folienkopien werden hier bereitgestellt