Einführung in Algorithmische Geometrie

• Range Queries
• Lokalisierungsprobleme
• Arrangements
• Motion Planning
• Kunstgallerie-Problem
• Sweepline-Algorithmen
• Geometrische Datenstrukturen

• Intro (15.04): [slides]
• Range Queries 1 - Quadtrees (22.04.): [slides]
• Range Queries 2 - kD-Trees (29.04.): [slides], [notizen]
• Sweep-Line (06.05.): [slides], [notizen]
• Overlays (13.05.): [slides], [notizen]
• Punktlokalisierung (20.05.): [slides]
• Trapezoidal Maps (03.06.): [slides]
• Minkowski Summen (10.06.): [slides]
• (Exkurs) Multi-Robot-Motion-Planning (17.06.): [slides]
  Spannende weitere Videos: [Moving Sofa Problem (english)], [Moving Sofa Problem (deutsch)], [Coordinated Motion Planning]
• Art-Gallery-Problem (24.06.): [slides]
• Visibility Polygone (01.07.): [slides]
• Zusammenfassung (08.07.): [slides]

• Range Queries, Range Trees: [notizen]
• Sweep Line, Kolineare Punkte: [notizen]
• Angular-Sweep: [notizen]
• Roadmap, Minkowski-Summe: [notizen]
• Art Gallery: [notizen]

(Hinweis: Das Votierungssystem wurde gestrichen; die Aufgaben werden nur in den Übungen besprochen.)

• Blatt 1 (Besprechung 06.05.): [pdf], [quadtree], [kdTree]
• Blatt 2 (Besprechung 20.05.): [pdf], [Segmente]
• Blatt 3 (Besprechung 10.06.): [pdf], [Arrangement], [Trapezoidal Map]
• Blatt 4 (Besprechung 24.06.): [pdf], [Configuration Space], [Roadmap]
• Blatt 5 (Besprechung 08.07.): [pdf], [Visibility Polygon], [Art Gallery Polygon], [Turm Guards]

Die zu den Hausaufgabenblättern existierenden pdfs zu den Instanzen können auch digital mit IPE bearbeitet werden.

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry - Algorithms and Applications. Springer Science Business Media, 2000.

Neuigkeiten

• Die Evaluation ist da und kann HIER heruntergeladen werden. Die Ergebnisse werden voraussichtlich in der letzten Vorlesungswoche besprochen.
• Am 3.6. geht eine Liste für die Studienleistung rum. Wer die Studienleistung haben möchte, muss sich hier eintragen. An dem Tag findet außerdem die Lehrevaluation statt.

Klausur

Die Klausur findet am 28.08. um 09:00 Uhr im Raum SN 19.1 statt. Bitte seid 15 Minuten vorher anwesend. Mitzubringen sind:

• Studierendenausweis
• Dokumentenechter Stift (kein Bleistift, Füller oder Rotstifte)
• Geo-Dreieck oder Lineal
• Wörterbuch (falls nötig) auf Papier ohne Notizen

Andere Hilfmittel sind nicht zugelassen. Papier wird von uns gestellt.

Klausur aus dem Sommer 25: [pdf]

Mailingliste

Es gibt eine Mailingliste zur Veranstaltung. Bitte registriert euch dort. Wir versenden darüber Informationen zur Klausur, Ausfällen, Korrekturen, etc. Es werden nur tubs-Adressen freigegeben. Bei Problemen wendet euch per Mail an Arne Schmidt. Hier geht es zur [Mailingliste].