BA-INF 051 PG Computational Geometry

In dieser Projektgruppe sollen vorrangig geometrische Algorithmen animiert dargestellt werden. Konkret wird in der Regel nach einem oder mehreren wissenschaftlichen Artikeln oder anderen Quellen gearbeitet, in denen eine algorithmische Lösung einer zumeist geometrische Fragestellung behandelt wird. Der entsprechende Algorithmus muss zunächst im Detail verstanden und soll anschließend implementiert und ggf. animiert dargestellt werden. Wir verwenden eine Bibliothek mit grundlegenden geometrischen Objekten und vielen bereits implementierten Methoden. Auf diese kann zurückgegriffen werden.

Die Themenvergabe verläuft individuell. Interessenten wenden sich bitte einfach jederzeit per E-Mail an Herman Haverkort oder Elmar Langetepe. Wir vergeben Einzelthemen oder Themen für kleine Gruppen (2-3 Studierende).

1. Sortieralgorithmen: „Sound des Speicherzugriffs“

• Wenn Algorithmen größere Datenmengen verarbeiten, werden die Daten während der Berechnungen blockweise zwischen Festplatte, Hauptspeicher und Zwischenspeicher übertragen. Damit geht am wenigsten Zeit verloren, wenn in jedem beschränkten Zeitraum meistens nur auf Speicherzellen zugegriffen wird, die im Speicher mehr oder weniger gebündelt sind. Oft haben verschiedene Algorithmen für ein Problem, z.B. Sortieren, die gleiche theoretische Zeitkomplexität aber sehr unterschiedliche Speicherzugriffstrukturen und somit praktische Effizienz. In diesem Projekt wollen wir die Struktur der Speicherzugriffe von Sortieralgorithmen (und vielleicht auch von anderen einfachen Algorithmen) nicht nur anschaulich machen, sondern auch hörbar. Etwas ähnliches hat Timo Bingmann gemacht: er hat die Datenwerte die verglichen werden sonifiziert—wir wollen aber ihre Adressen im Speicher sonifizieren. Dazu sollen die Algorithmen so implementiert werden, dass sie nur ein Array als Speicher benutzen, wobei wir die Operation auf dem Array so modifizieren, dass dabei auch Klang erzeugt wird. Das kann z.B. mit Java oder C++ gemacht werden, oder mit Supercollider: eine Programmiersprache die speziell für Klangerzeugung entworfen wurde.

2. Underground Maps: Platzierung der Labels

• U-Bahnpläne werden so gezeichnet, dass man gut sehen kann, wie die U-Bahnlinien miteinander verbunden sind. So kann man z.B. schnell und einfach erkennen, wo man umsteigen muss. Dazu werden die Haltestellen üblicherweise nicht nach einer kartografischen Projektion platziert; stattdessen werden sie so verschoben, dass die U-Bahnlinien und ihre Verbindungen möglichst klar dargestellt werden. Algorithmen für den Entwurf von U-Bahnplänen versuchen oft, zuerst die Darstellung des Liniennetzes zu optimieren und versuchen dann die Beschriftung (die Namen der Haltestellen) einzupassen. Das letzte ist dann aber oft kaum noch möglich. In diesem Projekt fangen wir mal vom anderen Ende her an: wir versuchen zuerst die Haltestellennamen ordentlich auf den Plan zu verteilen, so dass die Beschriftung jedenfalls passt, und nachher die Bahnlinien an den Haltestellennamen entlang gezeichnet werden können. Dazu formulieren wir die Bedingungen für eine gute Verteilung von Haltenstellennamen als ein Programm von, teilweise ganzzahligen, linearen oder konvexen Ungleichungen, das wir dann mit einem allgemeinen Solver lösen. Danach muss die Lösung auch gezeichnet werden, damit wir sie beurteilen können.

3. Nearest Neighbor Queries durch Space Filling Curves

• Man kann auf verschiedene Weise eine Reihenfolge für alle Punkte in einem Einheitsquadrat in der Ebene definieren, indem man, z.B., ein Quadrat rekursiv in kleinere Quadrate aufteilt und nach einem einfachen Algorithmus zu jedem Aufteilungsschritt bestimmt, in welcher Reihenfolge die Teilquadrate angeordnet werden. Eine solche Reihenfolge für alle Punkte in dem Einheitsquadrat kann man auch als raumfüllende Kurve bezeichnen; bekannte Beispiele sind die Z-Kurve und die Hilbert-Kurve. Man kann solche Kurven benutzen für Datenstrukturen für Nächster-Nachbar-Suche: man wählt eine kleine Menge von k raumfüllenden Kurven, und speichert die Datenpunkte k mal, nach jeder der k Sortierungen die von den raumfüllenden Kurven beschrieben werden. Wenn man zu einem Abfragepunkt den nächsten Punkt der gespeicherten Datenmenge wissen will, sucht man in jeder der k Sortierungen den Vorgänger und den Nachfolger des Abfragepunkts. So bekommen wir 2k Kandidaten für den nächsten Nachbar. Die richtige Antwort ist hoffentlich dabei; das kann aber nicht immer garantiert werden. In diesem Projekt wollen wir verschiedene Kombinationen von raumfüllenden Kurven probieren um festzustellen, wie oft man den echten nächsten Nachbar findet; wenn nicht, wie groß die Fehler sind; und wie sich die Ergebnisse verhalten zu theoretischen Schranken und Qualitätsmaßen für die Nachbar-bewahrenden Eigenschaften von raumfüllenden Kurven. Interessante Alternativen zu den üblichen Kurven sind z.B. Kurven mit kleinen Arrwwid-Zahlen.

4. Multiple Robot Routing mit Nebenbedingungen

• Eine effiziente Bewegung modularer Angenten auf engstem Raum ist eine wichtige Aufgabe. In einer Gitterwelt sollen einzelne aus Gitterzellen bestehende Agenten von einer Startkonfiguration zu einer Endkonfiguration effizient kollisionsfrei bewegt werden. Dazu soll eine interaktive Applikation programmiert werden. Ausgangspunkt ist dabei eine Arbeit, bei der die Aufgabe für ein komplett gefülltes Grid mit einzelnen Agenten algorithmisch quasi optimal gelöst wird. Dieser Algorithmus besteht aus kleinen Bewegungsblöcken und soll zunächst in 2D umgesetzt und animiert dargestellt werden und dann ggf. mit Nebenbedingungen (z.B. Ruheplätze oder ausgedehnte Agenten) erweitert werden. Ein effizienter 2D-Algorithmus wird in folgender Arbeit beschrieben: https://arxiv.org/abs/1801.10465

5. Terrain Guarding in Dimension 1.5 (oder 2.5)

• Die Platzierung von Wächtern zur Beobachtung eines Gebietes kommt in vielen Anwendungen vor. Gegeben ist hier ein 1.5 dimensionales Terrain als Polygonzug und es soll eine minimale Anzahl an Agenten gefunden werden, die das ganze Gebiet sehen. Dieses Problem ist NP-schwer im allgemeinen, es gibt aber Algorithmen mit guten Laufzeiten für Spezialfälle und zur Approximation der Anzahl der minimal notwendigen Agenten. Hierfür soll eine interaktive Applikation programmiert werden, bei der das Terrain editiert werden kann und verschiedene Algorithmen animiert dargestellt werden. Als Ausgangspunkt und Anhalt dienen die u.a. Arbeiten. Bei erweitertem Interesse kann auch das Hochschießen eines Satellitens in einem 2.5 dimensionalen Terrain betrachtet werden. Dabei soll ein Online-Algorithmus zur Kernsuche erweitert werden. Literatur dazu wird dann bei Interesse angefügt.
• http://drops.dagstuhl.de/opus/volltexte/2017/7197/pdf/LIPIcs-SoCG-2017-11.pdf
• https://www.sciencedirect.com/science/article/pii/S0925772107000259
• https://arxiv.org/abs/1605.03271Alternativ
• http://www.cs.umanitoba.ca/~durocher/research/pubs/durocherCCCG2015b.pdf

• FireFightíng in Graphen
• Zählen von Triangulationen
• Zielsuche nach mehreren Objekten in Bäumen
• Interferenzprobleme in Netzwerken
• Continous Dijkstra auf Polyedern

Online Routing in Triangulationen mit einem Shortcut

* onlrouttrianggen.pdf

• Diameter improvements by shortcuts
• Photographers path around a polygon
• Majority of elements
• Escape paths in geometric environments
• Two-Watchman and Guarding
• Illuminating of polygons