Bachelor-, Master- und Studienarbeiten

Allgemeinste Lage für den Graphen K_n

• zufälliger Greedy-Algorithmus auf dem Paraboloid (i,i²).
• regelmäßige (2n+1)-Ecke
• strenger geometrischer Greedy-Algorithmus auf dem Kreis, oder im Kreis.

Pseudogeradenarrangements schön zeichnen

• Verdrahtungsdiagramm (wiring diagram) glätten. Siehe Abbildung 1 für eine Ausgangslösung mittels wiring-diagram.
• Splines verwenden
• die Kurven möglichst gerade machen. Dabei die Abstände nicht zu klein werden lassen.

Dichteste Gitterpackung durch Tetraeder (und andere Polytope)

• spielerische Exploration von Lösungen

Unentscheidbares Problem über probabilistische Automaten

• Termersetzungssysteme
• Den Unentscheidbarkeitsbeweis von Matiyasevich und Sénizergues auf seine Wurzeln zurückverfolgen
• konkrete Matrizen als Beispiele konstruieren.

Berechnung der Determinante ohne Divisionen

• Anwendungsbeispiel: Intervallrechnung
• Vergleich verschiedener Dynamischer-Programmierungs-Ansätze (auch exponentielle), Algorithmus von Bird.
• Vergleich mit Gauß-Elimination
• Pivotauswahl
• Denis Zorin?

Singly-recursive de-Bruijn-cycle generation (unranking)

• Knuth Vol 4A, Algorithm S
• leads to binomial coefficients modulo a prime p. Kommentare im HTML ...
• streamlined version
• partial sums, partial double sums, etc.

Nonogramme unpopulär machen

• Endliche Körper von Charakteristik 2
• zufällige Gewichte

Polycubes auf verdrehtem Zylinder/Torus im dreidimensionalen Raum

• Untere Schranke für die Wachstumskonstante λ₃
• Große Zustandsmenge; Elimination von unwichtigen und gedoppelten Zuständen (mit gleichen Nachfolgerpaaren)
• Erkennen unwichtiger Zustände: solche die kleines Gewicht und kleinen Einfluss auf das Endergebnis haben.
• Übersicht über die Wachstumskonstante (und Zustandsanzahl) in Abhängigkeit von der Parametern des Quotientenraumes
• Python-Programm existiert; Umschreiben in C für größere Werte zwecks Speicherersparnis
• Hashtabelle der Zustände
• à la Barequet, Moffie, Ribó, Rote
• auch in 4 und mehr Dimensionen.

Polycubes mit dynamischer Programmierung

• Hashtabelle der Zwischenkonfigurationen
• à la Barequet, Moffie, Ribó, Rote

Diskreter Steinerpunkt

• Definition: die ersten Momente (Summe der Gitterpunkte im Polygon) der k-fach vergrößerten Polygone sind (in jeder Koordinate separat) ein Polynom in k vom Grad d+1, wobei d=2 die Dimension ist.
• Polynom in der Variablen k aus d+2 Werten interpolatieren.
• Der Koeffizient des linearen Terms ist der diskrete Steinerpunkt
• invariant unter unimodularen Transformationen.
• Implementierung und Eigenschaften, insbesondere in 2 Dimensionen.
• Wann liegt der diskrete Steinerpunkt außerhalb des Körpers? (in drei und höheren Dimensionen)

Make Lyndon word ("necklace") generator loopless by buffering

• (Amortized O(1) is already known.)
• (Lit: Diss. ...)

Obere Schranken für Polyominos durch verbotene Teilwörter

• Verwende einen geeigneten Code für kreuzungsfreie Spannbäume
• Indentifiziere verbotene Teilwörter (Überlappung, Verletzung von Vorrangregeln)
• Transfermatrixmethode auf dem Wortgraphen
• (Eine andere Methode im selben Geist: vgl. Klarner, D., Rivest, R. (1973). A procedure for improving the upper bound for the number of n-ominoes. Canadian Journal of Mathematics, 25(3), 585-602. doi:10.4153/CJM-1973-060-4. Siehe auch Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes, Gill Barequet, Mira Shalah) (ist inzwischen in Zeitschrift erschienen.)

Vertex-peeling and affine curvature flow on the paraboloid or the sphere (nach Eppstein, Nivasch, Har-Peled)

• Wie groß sind die auftretenden Flächen?
• In der Ebene ist das Problem weitgehend gelöst.

Die Conway-Folge 1, 11, 21, 1211, 111221, 312211, 13112221, ...

• Haskell-Programme von Watkins, Zugang von Ekhad und Zeilberger
• Beweise und Programme von Litherton?
• Unendliche Familien von Elementen an Tag 8 und Tag 7. Beschreibung durch endliche Automaten!
• Römische Ziffern (erwähnt auf Video von Conway, Polynom vom Grad 20)

Gute Gitter

• Greedy-Algorithmus für maximales 1-Netz liefert Voronoizellen mit Umkreis/Inkreis ≤ 2
• Starte mit Gitter (in verschiedenen Dimensionen); Greedy-Algorithmus (periodisch, eventuell zusätzlich symmetrisch); Wie viele Zellen kommen heraus? Welche Form haben sie? Wie "rund" werden sie?

Lineare Programme mit exakter Arithmetik in Polymake

• Lineare Programme, die beim Abzählen von minimalen dominierenden Mengen in Bäumen herauskommen.
• Konvexe Hüllen von algebraischen Zahlen

TAME GRAPHS im Flyspeck-Projekt

• Liste vorhanden
• Lineare Programme ausrechnen, nicht nur Packungsschranken. (Nipkow verwendet außerdem schwächere Konstanten.)

Zwischenschritte in OpenTheory

• anzeigen (siehe HOLIDE); Prototyp in Python vorhanden
• Clevere Typannotation (siehe HOL-Zero)
• Laufzeit und Speicher bzw. Länge der Ausgabe (Blowup) experimentell untersuchen.
• Gemeinsame Teilausdrücke?
• Datenstrukturen für beta-Reduktion etc.

Unique Sink Orientations on the 4-cube

• Lineare Programme, Spieltheorie, randomisierte Algorithmen
• Obere und untere Schranken bei vorgegebener Strategie
• Yao principle
• vgl. Stefano Tessaro, Randomized algorithms to locate the sink in low dimensional unique sink orientations of cubes, Semesterarbeit an der ETH Zürich unter Tibor Szabó und Ingo Schurr, 2004.

Überqueren der Brücke bei Nacht

Saturated simple drawings of graphs without crossing

• Modellierung durch homotope Wege
• Wenn sich Pfade paarweise höchstens k-mal kreuzen müssen, kann man sie dann auch gemeinsam so zeichnen?
• Computerprogramm
• Systematisches oder zufallsgerichtetes Erzeugen von gesättigten Beispielen mit Symmetrie

Kleinste Parkettierung eines Rechtecks mit einem einzelnen Polyomino

• Wie kann man die Ordnung ausrechnen?
• Ist ungerade Ordnung möglich? (Andrew Winslow, Bellairs 2016. S. Golomb, JCTA 1989)

Pebble motion planning on directed graphs

• Graphenalgorithmen; Komplexität, Erweiterung der Ergebnisse für gerichtete Graphen; eventuell mit mehreren Farbklassen.

Venn-Diagramme (mehrere Themen)

• Enumeration
• Geometrische Algorithmen

Physik-Simulation fallender Bausteine mit ODE

• Open Dynamics Engine (ODE)
• Fallende Bausteine mit einer anderen Animation zum Vergleich

Minkowski-Summe mittels Faltung

• Guibas, Ramshaw, Stolfi (FOCS 1983)
• Dissertation von Ron Wein; Ramkumar; Guibas and Seidel (DCG)
• Zusammenstellung aller Algorithmen; Ergänzung der Beweise (Windungszahl)
• Was bedeutet die Windungszahl (außer "0" oder "nicht 0")?
• GRS: Vielfachheit ist positive für Linksdrehung; negativ für Rechtsdrehung. Geht es auch ohne Vorzeigen?
• Guibas: Shapira (Paris) hat eine ähnliche Theorie unter dem Titel "constructible functions" entwickelt.
• Guibas+Bash (WAFR): 3d-Faltung für nichtkonvexe Polyeder

NetMeshing und Alternativen

• Miller, Phillips, Sheehy, 2011 SoCG
• Potenzdiagramm statt "diskretes additiv gewichtetes" Voronoi-Diagramm?
• Hierarchisches Clustering; dumbbell decomposition (Levcopoulos/Lingas)

Polygon zu drei Schachteln falten

Polyeder mit kleinen Koordinaten realisieren

Kurvenapproximation durch Bézier-Splines

Kurvenapproximation durch Kreisbögen

Pictures from Mongolia

Rental Harmony

Strukturen labyrinther Raumsysteme

Topologische Invarianten von Kurven

Wackelpermutationen

Geometric shortest path on polyhedral approximation

• Musin ...
• P. Agarwal; M. Sharir and P. Agarwal

Apportionment by Maximum Likelyhood Methods

Abgeschwächte Definition von Delaunay-Triangulierungen

Hintereinanderschalten von Zeitschaltuhren

Single Transferable Vote

Fermat-Weber-Problem

• Ellipsoid-Methode. ALGEBRAIC OPTIMIZATION: THE FERMAT-WEBER LOCATION PROBLEM, R. CHANDRASEKARAN und A. TAMIR, Mathematical Programming 46 (1990), 219-224. doi:10.1007/BF01585739
  
• Aggregieren. Prosenjit Bose and Anil Maheshwari and Pat Morin, Fast approximations for sums of distances, clustering and the Fermat–Weber problem, Comput. Geom. Theory Appl. 24 (2003), 135-146. doi:10.1016/S0925-7721(02)00102-5.
• Steilheit und Hesse-Matrix der Zielfunktion.
  

Minimizing the bounded Lipschitz norm under translations

Geometrische Realisierung dreidimensionaler Polytope

• Realisierungen dreidimensionaler Polytope mit gegebenem Netz
• Realisierungen dreidimensionaler Polytope mit kleinen Koordinaten
• konstruktiver Algorithmus zum Beweis des Satzes von Alexandroff
• Aufblasen (Heuristik?)
• Sabitov implementieren
• Bestimmung aller Möglichkeiten, ein Polygon zu einem Polytop zu falten. (Getan.)
• Entfaltungen vierdimensionaler Polytope entlang der Grate
• Quellenentfaltung (Miller und Pak)

Golomb-Maßstäbe

• teile und herrsche
• FFT
• verdoppelte Golomb-Rechtecke und dynamische Programmierung

Aufzählung der Ecken und Fahnen eines Polytops

Kompression von TeX-dvi-Dateien durch optimierte Registerverwendung

Abzählen von Polyominos

• Algorithmen für externen Speicher und sequentiellem Zugriff, oder mit Berücksichtigung von Lokalität bei Verwendung von virtuellem Speicher.
• Variante: nicht Breite des Rechtecks sondern größter Querschnitt (à la Zeilberger)??
• neue Felder symmetrisch hinzufügen, z.B. von innen nach außen (Faktor 2)
• nur Konfigurationen, die schon beide Ränder berührt haben (eventuell mit kleinerer Breite)
• Reverse search zum Erzeugen der zulässigen Konfigurationen.

Optimale Triangulierungen

"Delaunay"-Pseudotriangulierungen

Präfix-freie und nicht präfix-freie optimale Codes

Raumfüllende Kurven

Stückweise lineare konvexe Approximation

Diskretisierung im "Raum" aller "Formen"

• Größtes ähnliches Dreieck in einem Polygon
• homothetische Approximation
• alle konvexen geschlossenen Kurven fester Länge; Anwendung: kleinster Behälter, vgl. Budapest Juli 2008.
  • untere Schranke (für feste gegebene Menge von Kurven): Winkel diskretisieren
  • für festen Winkel: Aufzählen der Kontaktmöglichkeiten)

On-line-Erzeugung zufälliger konvexer Kurven oder Funktionen

Axioms and Hulls

Schnapprundung von Strecken

Konvexe n-Ecke mit genau n größten enthaltenen Dreiecken

"Komische" konvexe Hülle?

Quadratische Optimierung unter kürzeste-Wege-Restriktionen

Flächenberechnung der Facetten des Rundreisepolytops

Unique Sink Orientations: Randomisierter Algorithmus