Schema della sezione
-
Umfang:
5 ECTS, 2 SWS
Zeit & Ort:
Dienstags, 16:00–17:30 Uhr, Seminarraum III im Informatikgebäude M2 (erstmalig am 18.04.2023)
Voraussetzung:
Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen (Info., Bsc.), sowie Algorithmische Graphentheorie (Info., Bsc.) zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen. Die Vorlesung Algorithmische Geometrie (Info., Master) gehört zu haben, ist hilfreich, aber nicht erforderlich.
Zielgruppe:
Master Informatik (empfohlen), Bachelor Informatik
Dozenten:
Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 18.04.2023, um 16:00 Uhr – dieser wie auch die restlichen Termine des Seminars - wird in Präsenzform stattfinden. An diesem Termin bitten wir um vollständige Anwesenheit, da wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen. Die Liste der Themen finden Sie bereits jetzt weiter unten auf dieser Seite. Diese werden je nach Teilnehmerzahl jeweils alleine oder zu zweit bearbeitet. Machen Sie sich schon vorab Gedanken, welche Themen Sie bearbeiten möchten.
Bitte schreiben Sie sich schon jetzt in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen. Melden Sie sich dazu bei WueCampus an (das haben Sie wahrscheinlich schon getan) und klicken Sie in der "sekundären Navigationsleiste" (der Bereich unter dem Kurstitel) auf "Mich in diesen Kurs einschreiben").
Thema
Die Algorithmische Geometrie (engl. Computational Geometry) beschäftigt sich mit algorithmischen Fragestellungen, bei denen die Ein- und/oder Ausgabedaten geometrische Objekte sind, also Punkte, Strecken, Geraden, Ebenen, Kreise, Polygone, usw. Derartige Probleme spielen in vielen Bereichen der Informatik, bei denen es notwendig ist räumliche Daten zu speichern, zu analysieren, zu erzeugen oder zu manipulieren, eine Rolle; dazu gehören beispielsweise Robotik, Geografische Informationssysteme (GIS), CAD/CAM, Computergrafik und Virtual Reality. Zu diesem Thema wird an unserem Lehrstuhl auch jedes Jahr im Winter eine Vorlesung angeboten.
In diesem Seminar wollen wir uns mit aktuellen Forschungsthemen der Algorithmische Geometrie beschäftigen. Dabei werden insbesondere Themen behandelt, die erst vor Kurzem auf dem 38th International Symposium on Computational Geometry (SoCG) und dem 39th European Workshop on Computational Geometry (EuroCG) vorgestellt wurden. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen.. Die Vorlesung Algorithmische Geometrie gehört zu haben ist hilfreich, aber nicht erforderlich. Manche Themen enthalten spannende offene Forschungsfragen. Wenn in der zweiten Hälfte des Seminars Zeit bleibt, kann daran gemeinsam geforscht werden. Außerdem können sich dadurch Themen für Praktika oder Abschlussarbeiten im Anschluss an das Seminar ergeben.
Allen Themen liegt ein aktueller Artikel zu einem Beitrag einer der beiden oben genannten Konferenzen zugrunde. Diese haben wir in der Spalte Referenzen jeweils verlinkt. Da die Länge solcher Artikel strikt begrenzt ist, ist es üblich, zusätzlich eine ungekürzte Version auf einem Preprint-Server zu veröffentlichen. Diese Vollversionen sind ebenfalls verlinkt.
Titel Autor:innen Referenzen Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs Bringmann, Kisfaludi-Bak, Künnemann, Nusser, Parsaeian SoCG
VollversionLong Plane Trees Cabello, Hoffmann, Klost, Mulzer, Tkadlec SoCG
VollversionHop-Spanners for Geometric Intersection Graphs Conroy, Toth SoCG
VollversionDisjointness Graphs of Short Polygonal Chains Pach, Tardos, Tóth SoCG
VollversionFlat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles Chung, Demaine, Hendrickson, Luo SoCG
VollversionMaximum overlap area of a convex polyhedron and a convex polygon under translation Zhu, Jun Kweon EuroCG
VollversionSometimes Two Irrational Guards are Needed Meijer, Miltzow EuroCG
VollversionTowards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain de Berg, Miltzow, Staals EuroCG
VollversionPrimal-Dual Cops and Robber★ Tuan Ha, Jungeblut, Ueckerdt EuroCG
VollversionExtending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable Bhore, Ganian, Khazaliya, Montecchiani, Nöllenburg EuroCG
VollversionCrossing Minimization in Time Interval Storylines★ Dobler, Nöllenburg, Stojanovic, Villedieu, Wulms EuroCG
VollversionInsertion-Only Dynamic Connectivity in General Disk Graphs Kaplan, Klost, Knorr, Mulzer, Roditty EuroCG
VollversionOn the geometric thickness of 2-degenerate graphs Jain, Ricci, Rollin, Schulz EuroCG
Vollversion
★ Diese Artikel sind weniger umfangreich als die übrigen Themen. Dies sollte jedoch nicht fälschlicherweise mit weniger Bearbeitungsaufwand gleichgesetzt werden. Wer eines dieser Themen wählt, muss damit rechnen, etwas mehr eigene Literaturrecherche betreiben zu müssen oder einen der ersten Vortragstermine mit weniger Vorbereitungszeit zugewiesen zu bekommen.Lernziele
Ziel ist es, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmer:innen in einem Vortrag, sowie in einer schriftlichen Ausarbeitung zu vermitteln. Für jedes Thema geben wir einen Artikel bzw. ein Buchkapitel vor. Sie sollen aber auch noch selbst Literaturrecherche betreiben. Ein Ausgangspunkt dafür können beispielsweise die Referenzen in Ihrem Artikel sein. Da wir das Seminar auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Forschungsfragen ein wichtiger Bestandteil der Themen.
Sie bekommen im Seminar einen Überblick über Techniken, sowie Modellierungs- und Lösungsansätze der Algorithmischen Geometrie. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.
Ablauf
- Im ersten Treffen werden wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen.
- Im zweiten Treffen geben wir Tipps zum Anfertigen von Ausarbeitungen.
- Im dritten Treffen geben alle Teilnehmer:innen einen kurzen Überblick über ihr Thema (max. 5 Minuten, ca. 3 Folien).
- In den folgenden Treffen finden die eigentlichen Vorträge der Teilnehmer:innen statt. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für die weitere Forschung.
- Die Ausarbeitungen sind zum Ende der Vorlesungszeit anzufertigen.
Module
Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen.
Allgemeine Literatur zur Algorithmischen Geometrie
- Computational Geometry: Algorithms and Applications.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer-Verlag, 3rd edition, 2008.
[ Online verfügbar ] (Mit Uni Account)
- Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen.
Rolf Klein. Springer-Verlag, 2nd edition, 2005.
[ Online verfügbar ] (Aus dem Uni Netz)
Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Bildnachweise
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon