Praktikum Effiziente Algorithmen

• SWS: 3P
• Zeit: Di 16-19
• Ort: Takustraße 9, SR 046
• Vorbesprechung: Dienstag 16.4., 16 Uhr c.t.

Inhalt

Ablauf

Themen

• Auseinanderfalten von Polygonen

Zwei ebene Polygone mit derselben Folge von Seitenlängen können immer stetig ohne Selbstüberlappung ineinander transformiert werden, wenn man die Kanten als Stäbe fester Länge betrachtet, die an den Ecken beweglich miteinander verbunden sind. Für diesen Vorgang gibt es verschiedene Algorithmen, die implementiert werden können. (Für einige Beispiele gibt es Animationen, die aus einer vorläufigen Implementierung entstanden sind.) Ich werde Anfang Juni auf dem ACM Symposium on Computational Geometry in Barcelona über dieses Thema vortragen, und wenn die Programme bis dahin laufen, würde ich sie gerne dort zeigen.
Literatur: Robert Connelly, Erik D. Demaine, and Günter Rote: Straightening polygonal arcs and convexifying polygonal cycles.
Robert Connelly, Erik D. Demaine, and Günter Rote: Infinitesimally locked self-touching linkages with applications to locked trees.
• Kanonische Pseudotriangulierungen

Eine Pseudotriangulierung einer ebenen Punktmenge ist etwas ähnliches wie eine Triangulierung, d.h. eine Zerlegung der Ebene in Gebiete. Die Menge aller Pseudotriangulierungen lässt sich auf eine gewisse indirekte Art durch lineare Ungleichungen beschreiben. Indem man ein lineares Programm löst, kann man gewisse Pseudotriangulierungen auszeichnen. Welche Pseudotriangulierungen dabei herauskommen, ist noch nicht untersucht.
Literatur: Günter Rote, Francisco Santos, and Ileana Streinu: Expansive motions and the polytope of pointed pseudo-triangulations.
• Realisierung orientierbarer Matroide
• Das Assoziaeder

Das Assoziaeder ist ein schönes kombinatorisches und geometrisches Objekt. Es ist ein Polytop, dessen Ecken die Triangulierungen eines konvexen Polygons repräsentieren, und dessen Kanten den Triangulierungen entsprechen, die durch Kippen einer Kante auseinander hervorgehen. Auch viele andere sogenannte Catalan-Strukturen werden dadurch dargestellt, wie zum Beispiel binäre Bäume oder die Möglichkeiten, ein nichtassoziatives Produkt  a*b*c*d*e  zu klammern (daher der Name Assoziaeder). Es gibt verschiedene geometrische Realisierungen des Assoziaeders, unter anderem eine neue. Diese Polytope sollen dargestellt (zum Beispiel mit polymake) und miteinander verglichen werden.
Literatur: Günter Rote, Francisco Santos, and Ileana Streinu: Expansive motions and the polytope of pointed pseudo-triangulations.
• Wege in Chirotopen

Ein Chirotop gibt die Orientierung aller Dreiecke einer ebenen Punktmenge an (und analog für Punktmengen in höheren Dimensionen). (In Wirklichkeit sind Chirotope noch etwas allgemeiner.) Wenn man die Punkte bewegt, ändert sich das Chirotop nur lokal. Für kleine Punktmengen und kleine Dimensionen gibt es eine Liste aller Chirotope. Es soll untersucht werden, mit wievielen lokalen Änderungen man von einem Chirotop zu einem anderen kommen kann.
• Optimale Zufallsstrategien für Suchprobleme

Gewisse Optimierungsaufgaben lassen sich als Suchprobleme auf einem Würfel darstellen, dessen Kanten orientiert sind, sodass gewisse Eigenschaften gelten (z.B. dass der Würfel und jede Seite des Würfels eine eindeutige Senke (Ecke ohne ausgehende Kanten) hat. Das Bestimmen einer optimalen randomisierten Strategie zum Finden der Senke kann man mit Hilfe der Spieltheorie als (riesiges) lineares Programm formulieren. Für gewisse Varianten wurde dieses Problem bereits gelöst. Andere Fragen, zum Beispiel die Bestimmung aller optimalen Strategien, sind noch offen.
Literatur: Beschreibung des Algorithmus (Manuskript im Entwurfsstadium)
Emo Welzl: Unique sink orientations of cubes (Zusammenfassung, eine Seite)
Bernd Gärtner: Combinatorial structure in convex programs
• Der Expansionskegel in höheren Dimensionen

Der Expansionskegel beschreibt alle (Richtungen von) Bewegungen einer Punktmenge, bei denen sich alle Punkte voneinander entfernen. In der Ebene kennt man die Struktur dieses Kegels genau, nicht jedoch bei räumlichen Punktmengen.
• Realisierung von dreidimensionalen Polytopen mit kleinen Koordinaten

Es gibt ein Verfahren, das jeden gegebenen kombinatorischen Typ eines Polytops mit n Seiten so realisiert, dass die Koordinaten der Ecken ganze Zahlen mit höchstens O(n²) Bits sind. Hier soll man versuchen verschiedene Polyeder (zum Beispiel das Pentagondodekaeder) mit möglichst kleinen Koordinaten darzustellen.
• Optimierung von Roboterbahnen

Voraussetzungen

Perspektiven: