Institut für Betriebssysteme und Rechnerverbund
- News
- Mikroprozessorlabor
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- - IST.hub

Einführung in Algorithmische Geometrie

Semester	Sommersemester 2025
Studiengang	Informatik Bachelor
IBR Gruppe	ALG (Prof. Fekete)
Art	Vorlesung & Übung
Dozent	Dr. Arne Schmidt Wissenschaftlicher Mitarbeiter aschmidt[[at]]ibr.cs.tu-bs.de +49 531 3913115 Raum 333
LP	5
SWS	2+1+1
Ort & Zeit	Vorlesung und Übung: Donnerstags, 13:15 Uhr - 16:30 Uhr (SN 19.2)
Beginn	Erste Vorlesung / große Übung: 10.04.25 Erste kleine Übung: TBA
Voraussetzungen	Die Inhalte von Algorithmen und Datenstrukturen werden vorausgesetzt.
Sprache	Deutsch
Scheinerwerb	Studienleistung: Erfolgreiche Bearbeitung der Hausaufgaben Prüfungsleistung: Klausur am Ende des Semesters
Anmeldung
Inhalt	Die Vorlesung deckt folgende Inhalte ab. Range Queries Lokalisierungsprobleme Arrangements Motion Planning Kunstgallerie-Problem Sweepline-Algorithmen Geometrische Datenstrukturen
Material	Vorlesungen Intro (10.04): [slides] Range Queries 1 - Quadtrees (17.04.): [slides] Range Queries 2 - kD-Trees (24.04.): [slides], [notizen] Sweep-Line (08.05.): [slides], [notizen] Overlays (15.05.): [slides], [notizen] Punktlokalisierung (22.05.): [slides] Große Übungen Range Queries, Range Trees: [notizen] Sweep-Line-Algorithmen: [notizen] DCEL, Point-Line-Duality: [notizen], [Demo zu Point-Line-Duality] Hausaufgaben Blatt 1 (Abgabe 15.05.): [pdf], [quadtree], [kdTree] Blatt 2 (Abgabe 30.05.): [pdf], [Segmente] Die zu den Hausaufgabenblättern existierenden pdfs zu den Instanzen können auch digital mit IPE bearbeitet werden.
Literatur/Links	Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry - Algorithms and Applications. Springer Science Business Media, 2000.
Klausur Die Klausur findet am 31.07.25 um 13:00 Uhr im Raum ZI 24.2 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. Mailingliste Es gibt eine Mailingliste zur Veranstaltung. Bitte registriert euch dort. Wir versenden darüber Informationen. Es werden nur tubs-Adressen freigegeben. Bei Problemen wendet euch per Mail an Arne Schmidt. Hier geht es zur [Mailingliste].