Algorithmische Geometrie

(Sommersemester 2009) -> KVV

Helmut Alt, Claudia Dieckmann, Sven Scholz

Aktuelles Übungszettel Skript Termine Literatur Scheinkriterien Klausurvorbereitung

Aktuelles

13.10.2009
Die Ergebnisse der Nachklausur sind hier zu finden.
21.7.2009
Einsicht in die Klausur: 4.8.2009, 10-11 Uhr, SR 005
Termin der Nachklausur: 12.10.2009, 14-16 Uhr, SR 005
17.07.2009
Die Ergebnisse der Klausur sind hier zu finden.
14.07.2009
Eine Klausur aus dem Sommersemester 2005 ist hier zu finden.
17.04.2009
Das Tutorium Di 10:00 - 12:00 entfällt. Da die Anmeldungen aller Studenten für die Dienstagstermine gelöscht wurden, ist eine Neuanmeldung erforderlich.
17.04.2009
Eine Mitschrift aus dem Sommersemester 2005 ist hier zu finden.
14.04.2009

Übungszettel

Die Übungszettel erscheinen in der Regel am Freitag und sind in der darauf folgenden Woche vor Beginn der Vorlesung abzugeben.

Nr. Ausgabe Abgabe Bemerkung
ag_01.pdf 17.04.2009 24.04.2009
ag_02.pdf 24.04.2009 30.04.2009
ag_03.pdf 30.04.2009 08.05.2009
ag_04.pdf 08.05.2009 15.05.2009
ag_05.pdf 15.05.2009 22.05.2009
ag_06.pdf 22.05.2009 29.05.2009
ag_07.pdf 29.05.2009 05.06.2009 Es gibt Code von Marco, mit dem man bequem eine Punktliste aus einer Textdatei lesen kann: AG-polylinereader.zip
ag_08.pdf 05.06.2009 12.06.2009 orte_deutschland.txt
orte_weltweit.txt
ag_09.pdf 12.06.2009 19.06.2009
ag_10.pdf 19.06.2009 26.06.2009
ag_11.pdf 26.06.2009 03.07.2009
ag_12.pdf 03.07.2009 10.07.2009 kleine Änderung in Aufgabe 1

Termine

Datum Themen
15.04.2009
  • Überblick, Motivation
  • Berechnungsmodell
  • Konvexe Hüllen
17.04.2009
  • BHD als Datenstruktur für konvexe Polygone
22.04.2009
  • Schnitt zweier konvexer Polygone
24.04.2009
  • konvexe Hülle eines einfachen Polygons
29.04.2009
  • konvexe Hülle einer endlichen Punktmenge
    • untere Schranke für die Laufzeit
    • Graham Scan
    • inkrementelle Konstruktion
  • Voronoi-Diagramm
06.05.2009
  • Voronoi-Diagramm
  • planare Graphen
08.05.2009
  • Delaunay Triangulierung
  • Konstruktion des Voronoi-Diagramms per Divide and Conquer
13.05.2009
  • Konstruktion des Voronoi-Diagramms per Divide and Conquer
15.05.2009
  • Suchen in ebenen Unterteilungen
20.05.2009
  • Anwendungen von Voronoi-Diagrammen
  • Sweepline-Verfahren
  • Schnittpunkte einer Menge von Strecken
22.05.2009
  • Triangulierung eines einfachen Polygons
27.05.2009
  • Zerlegung eines einfachen Polygons in konvexe Teile
  • Sweeplineverfahren für Konstruktion des VD
29.05.2009
  • Sweeplineverfahren für Konstruktion des VD
03.06.2009
  • orthogonale Bereichsabfragen
  • k-d-Bäume
05.06.2009
  • k-d-Bäume
  • Range-Trees
10.06.2009
  • Range-Trees
12.06.2009
  • höherdimensionale algorithmische Geometrie
  • stereographische Projektion / Polytope vs. planare Graphen
  • Dualisierung
17.06.2009
  • konvexe Hülle im R3 (Gift Wrapping)
19.06.2009
  • Schnitt von Halbräumen
  • Delaunay Triangulierung vs. konvexe Hülle
24.06.2009 ...
Vorlesung: Mi 14:00 - 16:00 Seminarraum 005

Fr 12:00 - 14:00 Seminarraum 005
Übung Claudia Dieckmann: Mo 12:00 - 14:00 Seminarraum 055
Übung Sven Scholz: Di 16:00 - 18:00 Seminarraum 005

Literatur

J.-D. Boissonnat, M. Yvinec. Algorithmic Geometry. Cambridge University Press, 1998. R. Klein. Algorithmische Geometrie. Addison-Wesley, 1997. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag Berlin, 1997. F.P. Preparata, M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag New York, 1985.

Klausurvorbereitung

Hier stehen die Algorithmen, die in der Vorlesung behandelt wurden. Für die Themenvergabe bitte eine Mail an den entsprechenden Tutor schreiben.

Tutorium Claudia
Thema Name
BHD-Baum:
Punktlokalisation 		Philipp Ledermann
BHD-Baum:
Schnitt zweier konvexer Polygone 		?
BHD-Baum:
Schnitt konv.Polygon mit Gerade 		Ella Kadas
Konvexe Hülle:
Graham-Scan
Inkrementeller Algorithmus
Untere Schranke für konvexe Hülle 		Benjamin Bartsch
Planare Graphen, Dualer Graph, Eigenschaften
 ?
Voronoi-Diagramm
Divide&Conquer
Fortune-Sweep
 Manuel Schwabe
Anwendung von Voronoi-Diagrammen
Nächstes Paar 		?
Sweepline-Algorithmen
Schnittpunkte eine Menge von Strecken
Triangulierung einfacher Polygone 		?
k-d-Baum
Range-Trees 		Benjamin Bortfeldt
Polytope/Polyeder
Stereographische Projektion		 ?

konvexe Hülle im R^3 		?

Tutorium Sven
Thema Name
BHD-Baum:
Punktlokalisation 		Marc Mashänser
BHD-Baum:
Schnitt zweier konvexer Polygone 		?
BHD-Baum:
Schnitt konv.Polygon mit Gerade 		?
Konvexe Hülle:
Graham-Scan
Inkrementeller Algorithmus
Untere Schranke für konvexe Hülle 		Christopher Keiner
Planare Graphen, Dualer Graph, Eigenschaften
 Peter Ertel
Voronoi-Diagramm
Divide&Conquer
Fortune-Sweep
 ?
Anwendung von Voronoi-Diagrammen
Nächstes Paar 		?
Sweepline-Algorithmen
Schnittpunkte eine Menge von Strecken
Triangulierung einfacher Polygone 		?
k-d-Baum
Range-Trees 		Viktoria Schwarzhaupt
Polytope/Polyeder
Stereographische Projektion		 ?

konvexe Hülle im R^3 		?

Scheinkriterien


Impressum scholz[at]inf.fu-berlin.de 13.10.2009