Kopf
Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en

 

Algorithmische Geometrie

Die Vorlesung Algorithmische Geometrie (4V+2Ü) wird im Wintersemester 2008/2009 von Prof. Dr. Jan Vahrenhold angeboten. Die Übungen zur Vorlesung werden ebenfalls durch den Dozenten betreut.

Das Vorlesungsverzeichnis enthält die Belegnummern und offiziellen Kommentare zu Vorlesung und Übungen.

 


Zeit und Ort

  • Vorlesung: Montag/Dienstag, 10:15-11:50 Uhr (mit 5 min. Pause).
  • Ort: Seminarraum 304, OH-14.
  • Beginn: Montag, 13. Oktober 2008, 10:15 Uhr.
  • Übungen: Donnerstag, 14:14-15:45 Uhr (s.u.).
  • Ort: Seminarraum 304, OH-14.

 


Zuordnung

Die Veranstaltung ist im Hauptstudium des Diplomstudiengangs "Informatik" sowie im Masterstudiengang "Informatik" anrechenbar.

  • Diplomstudiengang "Informatik" (DPO'01), Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle).
  • Masterstudiengang "Informatik" (MPO'07), Forschungebiet D (Algorithmen und Komplexität), Modul INF-MA-602 (Vertiefungsmodul mit 3V+1Ü nach Absprache).

Studierende, die nach anderen Studien- bzw. Prüfungsordnungen studieren, mögen sich bei Zuordnungsfragen bitte persönlich bei mir melden. Danke!

 


Aktuelle Informationen

Bitte beachten Sie, dass die nachfolgenden Informationen noch vorläufig sind und ggfs. in der ersten Vorlesungswoche aktualisiert werden können.

  • (01.02.2009) Das Buch "Art Gallery Theorems and Algorithms" von Joseph O'Rourke ist on-line verfügbar.
  • (28.01.2009) Lesestoff zur Vorbereitung auf die letzte Vorlesung...
  • (04.11.2008) Der Übungstermin am Donnerstag, 13. November 2008, muss leider ersatzlos ausfallen.
  • (03.07.2008) Die Vorlesung beginnt am Montag, 13. Oktober 2008.

 


Inhalt

Die algorithmische Geometrie beschäftigt sich mit der Entwicklung und Realisierung effizienter Algorithmen für die Lösung geometrischer Probleme. Diese Probleme, die sich mit geometrischen Objekten wie Punkten, Linien oder Polygonen (bzw. deren höherdimensionalen Entsprechungen) beschäftigen, sind für viele Anwendungsgebiete von Bedeutung, z.B. für Geographische Informationssysteme, Computer Aided Design oder (vektor-orientierte) Computergraphik.

In dieser Vorlesung werden wir uns mit verschiedenen Klassen von Aufgabenstellungen befassen, z.B. mit der Berechnung von Nachbarschaftsbeziehungen, Triangulierungen und der Beantwortung von Lokalisierungsanfragen. Hierbei werden wir verschiedene Entwurfs- und Analysetechniken kennen lernen, die zur Behandlung geometrischer Problemstellungen verwendet werden können.

 


Vorlesungsunterlagen

Die in der Vorlesung vorgestellten Folien werden hier im Laufe des Semesters veröffentlicht. Das für den Zugriff auf die Folien notwendige Passwort wird in der Vorlesung bekannt gegeben.

Folien

Beispielkonfigurationen

An dieser Stelle werden Beispielkonfigurationen zum Mitschreiben in der Vorlesung bzw. zur eigenen Nachbereitung bereit gestellt.

  • Kapitel 02: Konvexe Hülle mittels RIC (.pdf), Stand: 14.11.2008.
  • Kapitel 02: Konvexe Hülle mittels Algorithmus von Chan (.pdf), Stand: 17.11.2008.

Errata/Nachträge/OAQs

An dieser Stelle werden Errata (jedoch keine Korrekturen von Tippfehlern) und/oder Nachträge veröffentlicht. Bei Bedarf werden über den Vorlesungsstoff hinaus gehende (also nicht prüfungsrelevante!) Fragen (so genannte occasionally asked questions) diskutiert.

  • (20.01.2009) Auf Folie 7.24 wird der erweiterte Katalog A(u) für ein Blatt u mit C(u) (und nicht: C(v)) initialisiert.
  • (04.01.2009) Auf Folie 5.15 wird der Winkel α als Minimum der Winkel α'i (und nicht: αi) gebildet.
  • (08.12.2008) Auf Folie 4.35 wird der Winkel α durch die Punkte p, p1 und r gebildet.
  • (08.12.2008) Der Beweis zu Lemma 4.11 (Folie 4.31) wurde vervollständigt. Die ergänzten Folien sind hier zu finden.
  • (29.11.2008) Soll Algorithmus 3.9 auch zur Verarbeitung einer Multimenge genutzt werden können, so ist in der while-Schleife in Zeile 9 die zusätzliche Bedingung "i<tail" einzufügen.

 


Übungen

Die Übungen finden Donnerstag, 14:15-15:45 Uhr, in Raum 304, OH-14 statt, es wird eine Übungsgruppe eingerichtet. Bei Terminkollisionen mit anderen Veranstaltungen besteht eine gewisse Flexibilität; sprechen Sie mich gerne bei Bedarf deswegen an. Der erste Übungstermin ist Donnerstag, 23.10.2008.

Nachfolgend stehen die jeweils aktuellen Übungszettel im PDF-Format bereit.

  • Blatt 01 (.pdf), Abgabe am 20.10.2008, Besprechung am 23.10.2008.
  • Blatt 02 (.pdf), Abgabe am 27.10.2008, Besprechung am 30.10.2008.
  • Blatt 03 (.pdf), Abgabe am 03.11.2008, Besprechung am 06.11.2008.
  • Blatt 04 (.pdf), Abgabe am 18.11.2008, Besprechung am 20.11.2008.
  • Blatt 05 (.pdf), Abgabe am 25.11.2008, Besprechung am 27.11.2008.
  • Blatt 06 (.pdf), Abgabe am 02.12.2008, Besprechung am 04.12.2008.
  • Blatt 07 (.pdf), Abgabe am 09.12.2008, Besprechung am 11.12.2008.
  • Blatt 08 (.pdf), Abgabe am 16.12.2008, Besprechung am 18.12.2008.
  • Blatt 09 (.pdf), Abgabe am 06.01.2009, Besprechung am 08.01.2009.
  • Blatt 10 (.pdf), Abgabe am 13.01.2009, Besprechung am 15.01.2009.
  • Blatt 11 (.pdf), Abgabe am 20.01.2009, Besprechung am 22.01.2009.
  • Blatt 12 (.pdf), Abgabe am 27.01.2009, Besprechung am 29.01.2009.
  • Blatt 13 (.pdf), Abgabe am 03.02.2009, Besprechung am 05.02.2009.

Errata/Nachträge

  • (Noch keine Informationen vorhanden.)

 


Literatur

Die Vorlesung basiert im Wesentlichen auf dem nachfolgend angegebenen (englischsprachigen) Lehrbüchern:

  • M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: "Computational Geometry: Algorithms and Applications", 3. Auflage, Springer, Berlin, 2008.
  • F. P. Preparata, M. I. Shamos "Computational Geometry: An Introduction", 2. Auflage, Springer, Berlin, 1988.

Für den erfolgreichen Besuch der Vorlesung ist es jedoch nicht zwingend notwendig, diese (sehr guten) Bücher zu erwerben.

Weitere Literaturhinweise sind im Kapitel "Organisatorisches" zu finden.

 


Fachprüfung/Leistungsnachweis/Studiennachweis

  • Studierende nach DPO'01: Für die erfolgreiche Teilnahme an der Vorlesung und an den Übungen wird ein Leistungsnachweis ausgestellt. Bedingung hierfür ist (neben der Teilnahme) die Bearbeitung von 50% der Aufgaben (jeweils 50% der Aufgaben von Blatt 2-7 und 50% der Aufgaben von Blatt 8-13) sowie das Vorrechnen von zwei Aufgaben in der Übung.
    Eine Fachprüfung kann in Form einer mündlichen Prüfung im Umfang von 30 min. Dauer abgelegt werden.
  • Studierende nach anderen Prüfungsordnungen: Bitte halten Sie mit mir Rücksprache.

 


RSS-Feed

  • Änderungen an dieser Seite sind über einen RSS-Feed nachvollziehbar Feed.

 

 
Sitemap Imprint
<www  ls11.cs.uni-dortmund.de>
The university does not accept liability for the contents of linked external internet sites