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 2009/2010 von Prof. Dr. Jan Vahrenhold angeboten. Die Übungen zur Vorlesung werden durch Herrn Christian Scheffer betreut.

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

 


Zeit und Ort

  • Vorlesung: Montag, 12:15-13:50 Uhr, Dienstag, 10:15-11:50 Uhr (mit 5 min. Pause).
  • Ort: Seminarraum 304, OH-14.
  • Beginn: Montag, 12. Oktober 2009, 12: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.

  • (04.08.2010) Alle bis zu diesem Zeitpunkt bekannten inhaltlichen Korrekturen (s.u., herzlichen Dank an S. Temme für viele detaillierte Hinweise) sind eingearbeitet. Die Folien der Kapitel 2, 4, 6, 8 und 10 wurden entsprechend aktualisiert.
  • (24.11.2009) Die Vorlesung am 08.12.2009 wird mit der Übung am 10.12.2009 getauscht.
  • (16.11.2009) Die Vorlesung am 17.11.2009 muss wegen Erkrankung des Dozenten leider ausfallen.
  • (15.11.2009) Die Vorlesung am 16.11.2009 muss wegen Erkrankung des Dozenten leider ausfallen.
  • (21.10.2009) Der in der Vorlesung angesprochene Artikel zum Stand der "P/NP-Problems" ist hier (aus dem Netz der TU frei) zugänglich.
  • (11.10.2009) Die Übungen beginnen in der zweiten Vorlesungswoche.

 


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: 25.10.2009.
  • Kapitel 02: Konvexe Hülle mittels Algorithmus von Chan (.pdf), Stand: 25.10.2009.

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.

  • (04.08.2010) Auf Folie 2.5 muss es in Teil 1 des Lemmas an Stelle von heißen.
  • (04.08.2010) Auf Folie 4.23 muss es "ej,i" an Stelle von "ej,1" heißen.
  • (04.08.2010) Auf Folie 4.28 muss es "(i mod k)+1" an Stelle von "(i+1 mod k)+1" heißen.
  • (04.08.2010) Auf Folie 4.35 muss es in der letzten Zeile "an p" an Stelle von "an q" heißen.
  • (04.08.2010) Auf Folie 4.55 muss es "die Wellenfront durchstoßen" an Stelle von "die Sweep-Linie durchstoßen" heißen.
  • (04.08.2010) Auf Folie 4.67 muss es zweimal "Parabelbögen" an Stelle von "Kreisbögen" heißen.
  • (04.08.2010) Auf Folie 6.43 wurde die Formulierung zur Erhaltung der Invariante 2 korrigiert; die korrigierte Version ist im Foliensatz und hier zu finden.
  • (04.08.2010) Auf Folie 6.49 wurde der Algorithmus korrigiert; die korrigierte Version ist im Foliensatz und hier zu finden.
  • (04.08.2010) Auf Folie 8.25 muss es im zweiten Punkt "Schritte 4 und 5" an Stelle von "Schritte 5, 6 und 7" heißen.
  • (04.08.2010) Auf Folie 8.48 muss es in Fall 1.1 an Stelle von heißen.
  • (04.08.2010) Auf Folie 9.21 muss es "r-l>1" an Stelle von "l-r>1" heißen.
  • (04.08.2010) Auf Folie 10.7 muss es "pi > x2" an Stelle von "pi < x2" heißen.
  • (04.08.2010) Auf Folie 10.53 muss der mittlere gelb markierte Knoten mit "[3,6)" an Stelle von "[3,4)" beschriftet sein.
  • (04.08.2010) Auf Folie 10.63 muss es "dim(t)<d" an Stelle von "dim(S)<d" heißen.
  • (05.01.2010) Auf Folie 7.37 muss es jeweils (insgesamt an drei Stellen) L' an Stelle von L heißen.
  • (01.12.2009) Auf Folie 5.6 muss es in der letzten Zeile an Stelle von heißen.
  • (13.11.2009) In Algorithmus 3.9 muss es in Zeile 9 "tail<i" an Stelle von "i<tail" heißen (gleiche Änderung auf Folie 3.33 (oben)).
  • (13.11.2009) Auf Folie 2.100 muss ohne Beschränkung der Allgemeinheit angenommen werden, dass kein Eckpunkt auf der Strecke vom "Nordpol" zum Koordinatenursprung liegt.
  • (21.10.2009) Occasionally Asked Question (OAQ) 0: Was ist eine (Weg-)Zusammenhangskomponente? (.pdf)
  • (18.10.2009) Folie 1.64f.: Anpassung der Mengenbezeichner in Lemma 1.16 sowie Verzicht auf die Annahme, dass die Menge M' eindeutig bestimmt ist (.pdf).
  • (18.10.2009) Folie 1.45: Ausführliche und korrigierte Fassung des Beweises der unteren Schranke in Satz 1.9 (.pdf).

 


Ü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, 22.10.2009.

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

  • Blatt 01 (.pdf), Abgabe am 19.10.2009, Besprechung am 22.10.2009.
  • Blatt 02 (.pdf), Abgabe am 27.10.2009, Besprechung am 29.10.2009.
  • Blatt 03 (.pdf), Abgabe am 03.11.2009, Besprechung am 05.11.2009.
  • Blatt 04 (.pdf), Abgabe am 10.11.2009, Besprechung am 12.11.2009.
  • Blatt 05 (.pdf), Abgabe am 17.11.2009, Besprechung am 19.11.2009.
  • Blatt 06 (.pdf), Abgabe am 01.12.2009, Besprechung am 03.12.2009.
  • Blatt 07 (.pdf), Besprechung in der Präsenzübung am 08.12.2009.
  • Blatt 08 (.pdf), Abgabe am 15.12.2009, Besprechung am 17.12.2009.
  • Blatt 09 (.pdf), Abgabe am 05.01.2010, Besprechung am 07.01.2010.
  • Blatt 10 (.pdf), Abgabe am 12.01.2009, Besprechung am 14.01.2010.
  • Blatt 11 (.pdf), Abgabe am 19.01.2010, Besprechung am 21.01.2010.
  • Blatt 12 (.pdf), Abgabe am 26.01.2010, Besprechung am 28.01.2010.
  • Blatt 13 (.pdf), Abgabe am 02.02.2010, Besprechung am 04.02.2010.

Errata/Nachträge

  • (29.11.2009) Beispielkonfiguration für den Algorithmus von Fortune (.pdf).
  • (Korrigiert am 10.11.2009, 17:00 Uhr): In Aufgabe 18 muss der betrachtete Graph einfach sein.

 


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