Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Übersicht
  - Team
  - Lehre
  - Arbeiten & Jobs
  - Forschung
  - Publikationen
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- Forschungsverbünde
  - IST.hub

Einführung in Algorithmische Geometrie

Semester	Sommersemester 2026 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: Mittwochs, 13:15 Uhr - 16:30 Uhr (SN 19.3)
Beginn	Erste Vorlesung / große Übung: 15.04.26 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 (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] Multi-Robot-Motion-Planning (17.06.): [slides] Art-Gallery-Problem (24.06.): [slides] Visibility Polygone (01.07.): [slides] Zusammenfassung (08.07.): [slides] Große Übungen Range Queries, Range Trees: [notizen] Hausaufgaben (Hinweis: Das Votierungssystem wurde gestrichen; die Aufgaben werden nur in den Übungen besprochen.) Blatt 1 (Besprechung 06.05.): [pdf], [quadtree], [kdTree] 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.
Neuigkeiten 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].