[Arbeitsgruppen | Forschung | Studium & Lehre | Allgemeines | Home | Suche | English]

Arbeitsgruppen und Lehrstühle

Forschung

Studium und Lehre

Allgemeines

Home

Suche

Fakultät für Informatik

 

Grundzüge der
Algorithmischen Geometrie

Sommersemester 2019


Dozent:
Stefan Schirra

Inhalt:
Grundzüge der Algorithmischen Geometrie ist eine Pflichtveranstaltung im Bachelor Studiengang Computervisualistik (nach Studienplan im 4. Semester) und eine Wahlpflichtveranstaltung für die übrigen Bachelorstudiengänge der FIN.
Wie der Name schon sagt, gibt sie eine Einführung in die Algorithmische Geometrie. Insbesondere werden grundlegende geometrische Strukturen, z.B. Voronoi-Diagramme, und Grundprinzipien des Entwurfs geometrischer Algorithmen behandelt. Grundzüge der Algorithmischen Geometrie ist eine 3V + 1Ü Veranstaltung mit 5 Creditpoints.
Weitere Informationen zu Vorlesung, Übungen, Zulassungsbedingungen usw. finden Sie auf der Seite zu Grundzüge der Algorithmischen Geometrie im Sommersemester 2019 im E-Learning Portal der OVGU.



Vorlesungsmaterialien:


Vorlesungsfolien    

Vorlesung   1
Geometrie, Algorithmik,
Algorithmische Geometrie, Beispiele


Vorlesung   2
Geometrische Graphen, Euler Formel,
Triangulationen, Voronoidiagramme


Vorlesung   3
Delaunaydiagramme und -triangulationen,
minimale aufspannende Bäume,
2D konvexe Hülle


Vorlesung   4
3D konvexe Hülle, Arrangements,
inkrementelle Konstruktion, inkrementelle
Konstruktion von Arrangements von Geraden,
Zonensatz, inkrementelle Konstruktion der
konvexen Hülle einer Punktmenge in der Ebene

Vorlesung   5
Inkrementelle Konstruktion der konvexen
Hülle einer Punktmenge in 3D,
Teile-und-Herrsche,
maximale Punkte via Teile-und-Herrsche

Vorlesung   6
2D konvexe Hülle via Teile-und-Herrsche

Vorlesung   7
Closest Pair via Teile-und-Herrsche,
Voronoidiagramm via Teile-und-Herrsche

Vorlesung   8
Plane-Sweep, minimale Punkte via
Plane-Sweep

Vorlesung   9
Südwestpaare via Plane-Sweep,
2D konvexe Hülle via Plane-Sweep
Schnittpunkte achsenparalleler Strecken
via Plane-Sweep

Vorlesung 10
Schnittpunkte von Strecken via Plane-Sweep

Vorlesung 11
Schnitttest via Plane-Sweep,
Voronoidiagramm via Plane-Sweep


Vorlesung 12
Rotationg Calipers,
Durchmesser einer Punktmenge in 2D


Vorlesung 13
Minimales einschließendes Rechteck,
Polare Dualität, Schnitt von Halbräumen in 2D


Vorlesung 14
Schnitt von Halbräumen in 2D,
Parabolische Dualität,
flächenkleinstes Dreieck einer Punktmenge


Vorlesung 15
Ham-Sandwich Cut, Medianabstand
minimierende Regressionsgerade,
Lifting Map


Vorlesung 16
Lifting Map, Voronoi Delaunay in 2D und
untere konvexe Hülle in 3D, Vereinigung von
Kreisscheiben via Lifting Map und Dualität,
randomisierte inkrementelle Konstruktion
(RIC)


Vorlesung 17
Lineares Programmieren in 2D via RIC,
konvexe Hülle in 2D via RIC


Vorlesung 18
Konvexe Hülle in 3D via RIC,
Delaunaytriangulation der Eckpunktmenge
eines konvexen Polygons


Vorlesung 19
Prune & Search, Lineares Programmieren
in 2D via Prune & Search,
k-t kleinstes Element


Vorlesung 20
Quickhull, Fasthull

Vorlesung 21
Parallele Algorithmen,
maximale Punkte parallel,
Parametrische Suche


Vorlesung 22
Minimaler Durchmesser sich bewegender
Punkte mit Parametrischer Suche,
Vierteilen einer 2D Punktmenge
mit Prune & Search


 


Übungsblätter

   1. Übung
   2. Übung
   3. Übung
   4. Übung
   5. Übung
   6. Übung
   7. Übung
 



Literaturhinweise:


 

 

de Berg, Cheong, van Kreveld, Overmars.
Computational Geometry, Algorithms and Applications (3rd edition).
Springer-Verlag, 2008.
 
Rolf Klein.
Algorithmische Geometrie (2. Auflage).
Springer-Verlag, 2005.
 
Satyan Devadoss, Joseph O'Rourke.
Discrete and Computational Geometry.
Princeton University Press, 2011.
 

Alte Klausuren:



Prüfungsklausur GAG WiSe1819
Prüfungsklausur GAG SoSe2019
Prüfungsklausur GAG WiSe1718
Prüfungsklausur GAG SoSe2017
Prüfungsklausur GAG WiSe1617
Prüfungsklausur GAG SoSe2016
Prüfungsklausur GAG WiSe1516
Prüfungsklausur GAG SoSe2015
Prüfungsklausur GAG WiSe1415
Prüfungsklausur GAG SoSe2014
Prüfungsklausur GAG WiSe1314
Prüfungsklausur GAG SoSe2013

 


Prüfungsklausur GAG WiSe1213
Prüfungsklausur GAG SoSe2012
Prüfungsklausur GAG WiSe1112
Prüfungsklausur GAG SoSe2011
Prüfungsklausur GAG WiSe1011
Prüfungsklausur GAG SoSe2010
Prüfungsklausur GAG WiSe0910
Prüfungsklausur GAG SoSe2009
Prüfungsklausur GAG WiSe0809
Prüfungsklausur GAG SoSe2008
Prüfungsklausur GAG WiSe0708
Prüfungsklausur GAG SoSe2007

 
 



Webmaster  -