TUM – TUM – Menü

 

 
Algorithmische Geometrie

Vorlesung

 

Dozent: Dr. Nico Düvelmeyer
Übungsleitung: Dr. Nico Düvelmeyer

Aktuelles Termine und Sprechstunden Inhalt Voraussetzungen Skript Übungsblätter Literatur Links FAQ

Aktuelles

  • Die gestellte Aufgabe 51, d.h. die darin zu zeigende Behauptung, war falsch! Die korrigierte Version ist online!

Termine und Sprechstunden

Veranstaltung Tag Uhrzeit Raum Dozent/TutorIn
Vorlesung Dienstag 8:30-10:00 Uhr MI 02.04.011 Düvelmeyer
         
Übung (1. Gruppe) Dienstag (alle 2 Wochen) 10:15-11:45 Uhr MI 02.06.020 Düvelmeyer
Übung (2. Gruppe) Montag (alle 2 Wochen) 12:30-14:00 Uhr MI 02.06.022B Düvelmeyer

Person Sprechstunde (im Semester)
Nico Düvelmeyer nach Vereinbarung

Inhalt

Einige Grundtechniken zum Aufbau und zur Analyse von geometrischen Datenstrukturen zur algorithmischen effizienten Beantwortung geometrischer Fragestellungen werden an Standardbeispielen erarbeitet.

Insbesondere werden die Prinzipien
  • Teile und herrsche,
  • Gleitebenenverfahren (``plane sweep''), sowie
  • (randomisierte) inkrementelle Algorithmen
auf die Probleme
  • des geometrischen Suchens,
  • der Bestimmung der konvexen Hülle,
  • der Triangulation,
  • das Poststellenproblem (Voronoi Diagramme) und
  • der Überlagerung von ebenen geometrischen Informationen (GIS)
angwandt.

Voraussetzungen

  • Grundverständnis für Algorithmen und Komplexitätsaussagen
  • Grundlagen der analytischen Geometrie (Vektorrechnung) und der Wahrscheinlichkeitsrechnung

Skript

Vorlesung Skript Folien(orig) Folien Korrektur
20.10.2009 Kap1(pdf) V1(pdf) V1(pdf)
27.10.2009 Kap2(pdf) V2(pdf) V2(pdf)
3.11.2009 Kap3(pdf) V3(pdf) V3(pdf) Beweis Satz 3.5: "log" fehlt in Analyse von Programmzeile 15
10.11.2009 Kap4(pdf) V4(pdf) V4(pdf)
17.11.2009 Kap5(pdf) V5(pdf) V5(pdf)
24.11.2009 Kap5 (s.o.) V6(pdf) V6(pdf) Alg. 5.15, Zeile 2: Behandlung c=0 (siehe Folien)
8.12.2009 Kap6(pdf) V7(pdf) V7(pdf) Terminverschiebung wegen Ausfall am 1.12.
15.12.2009 Kap7(pdf) V8(pdf) V8(pdf) (nur bis Folie auf Seite 29)
22.12.2009 Kap8(pdf) und Kap7 s.o. V9(pdf) V8(pdf),V9(pdf)  
12.1.2010 Kap8 (s.o.) V10(pdf) V10(pdf)  
19.1.2010 Kap9(pdf) V11(pdf) V11(pdf)  
26.1.2010 Kap10 Teil 1(pdf) V12(pdf) V12(pdf) (bereits gekürzt)
2.2.2010 Kap 10 Teil 1 (s.o.) und Teil 2(pdf) V13(pdf) V13(pdf)  
9.2.2010   Auswahl von externen Folien (INRIA, pdf)  V14(pdf)  

Hinweise zur Klausur

Übungsblätter

Übungsblatt Korrektur
Aufgaben zu Kapitel 2  
Aufgaben zu Kapitel 3  
Aufgaben zu Kapitel 4  
Aufgaben zu Kapitel 5  
Aufgaben zu Kapitel 6  
Aufgaben zu Kapitel 7  
Aufgaben zu Kapitel 8  
Aufgaben zu Kapitel 9 Aufgabe 51 korrigiert
Aufgaben zu Kapitel 10  

Literatur

FAQ

question Ich möchte die Vorlesung besuchen, kann aber zu den angegebenen Zeiten nicht. Kann sich da noch was ändern
info Ja, möglicherweise. Nachfrage per Email und in der ersten Vorlesung.

question Warum werden die Folien doppelt zum Download angeboten?
info Die erste Version (orig) wurde mittels pdflatex erzeugt und kann Verweise ins WWW enthalten. Die zweite Version wurde daraus mit jarnal erzeugt und enthält zusätzlich die Ergänzungen der Vorlesung, aber keine Verweise mehr.

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.