möchte­gern­geek

Die Frage wie groß das Revier eines Tieres ist, ist in konkreten Fällen für Biologen interessant und dank GPS-Sendern kann man es heutzutage sogar empirisch untersuchen. Aus der Punktwolke der besuchten Orte kann man eine Fläche abschätzen — im einfachsten Fall indem man die konvexe Hülle um alle besuchten Orte zeichnet.

Als Physiker sind mir echte Tiere zu kompliziert, sodass ich stattdessen annehme, dass sie punktförmig sind und ihre Bewegung ein Random Walk in einer isotropen Umgebung ist. Also springen meine idealisierten Tiere unabhängig von ihren bisherigen Handlungen zu ihrem nächsten Aufenthaltsort — der Abstand vom aktuellen Punkt ist dabei in jeder Dimension unabhängig und normalverteilt.

In jeder Dimension? Ja, genau! Wir wollen schließlich auch das Revierverhalten von vierdimensionalen Space Whales untersuchen.

Spaß beiseite, in dieser Veröffentlichung geht es natürlich eher um fundamentale Eigenschaften von Random Walks — einer der einfachsten und deshalb am besten untersuchten Markow-Prozesse. Und zwar im Hinblick auf Large Deviations, die extrem unwahrscheinlichen Ereignisse, die weit jenseits der Möglichkeiten von konventionellen Sampling-Methoden liegen. Details hierzu sind am besten direkt im Artikel oder mit einer Menge Hintergrundinformationen und ausführlicher als für ein Blog angemessen in dem entsprechenden Kapitel und Anhang meiner Dissertation nachzulesen. Insbesondere ist dort auch beschrieben wie die geometrischen Unterprobleme effizient gelöst werden können, auf die wir im Verlauf dieses Blogposts stoßen werden.

Das Problem eine konvexe Hülle zu finden ist einerseits einfach zu begreifen, schön geometrisch und sehr gut untersucht. Dadurch sind überraschend viele Algorithmen bekannt, die unterschiedliche Vor- und Nachteile haben.

Im Folgenden möchte ich deshalb ein paar Methoden vorstellen, wie man effizient die konvexe Hülle einer Punktmenge bestimmen kann, und dies mit animierten gifs von Punkten und Strichen visualisieren. Der Code zur Erstellung der Visualisierungen ist übrigens in Rust geschrieben und auf GitHub zu finden.

Andrew’s Monotone Chain

In zwei Dimensionen kann man ausnutzen, dass die konvexe Hülle ein Polygon ist, das man durch die Reihenfolge der Eckpunkte definieren kann. Die grundlegende Idee ist also die Punkte im Uhrzeigersinn zu sortieren, in dieser Reihenfolge, mit dem Punkt ganz links startend, alle zu einem Polygon hinzuzufügen und dabei darauf zu achten, dass die drei neusten Punkte des Polygons ein negativ orientiertes Dreieck bilden, also dass sie im „Uhrzeigersinn drehen“. Wenn das nicht der Fall ist, wird der mittlere Punkt entfernt.

Dies ist übrigens die ursprüngliche Variante, der Graham Scan. Andrew verbesserte diesen Algorithmus dadurch, dass nicht im Uhrzeigersinn sortiert werden muss, sondern man lexikographisch nach horizontaler Koordinate (bei Gleichstand entscheidet die vertikale Koordinate) sortiert. Dann bildet dieser Algorithmus die obere Hälfte der Hülle und wenn man ihn rückwärts auf die sortierten Punkte anwendet, die untere Hälfte.

Die Komplexität für \(n\) Punkte ist somit \(\mathcal{O}(n \ln n)\) limitiert durch das Sortieren.

Jarvis March: Gift Wrapping

Ein Geschenk einzupacken ist ein relativ intuitiver Prozess: Wir bewegen das Papier so lange herunter, bis wir auf einen Punkt des Geschenkes treffen, wo es hängen bleibt Dann wickeln wir weiter, bis wir auf den nächsten Punkt stoßen. Dabei streben wir an die konvexe Hülle zu finden, denn sie ist das Optimum möglichst wenig Papier zu verbrauchen während wir die Punktwolke einhüllen, die wir verschenken wollen. Und offenbar klappt das auch in drei Dimensionen!

In einem Computer ist es allerdings einfacher das Geschenkpapier von innen aus der Punktwolke heraus nach außen zu falten. Für jede Facette testen wir also jeden der \(n\) Punkte in der Punktwolke darauf, ob er links von unserem Stück Geschenkpapier liegt. Wenn ja, falten wir das Papier weiter. Sobald wir alle \(n\) Punkte ausprobiert haben, wissen wir, dass das Geschenkpapier an der richtigen Stelle liegt, sodass anfangen können die nächste Facette mit dem Geschenkpapier zu bilden indem wir von innen alle Punkte durchtesten.

Interessanterweise müssen wir also für jeden der \(h\) Punkte, die zur Hülle gehören \(\mathcal{O}(n)\) Punkte prüfen, sodass die Komplexität abhängig ist vom Ergebnis: \(\mathcal{O}(n h)\)

Chan’s Algorithm

Wir haben also einen \(\mathcal{O}(n \ln n)\) und einen \(\mathcal{O}(n h)\) Algorithmus kennen gelernt, aber können wir noch besser werden? Ja! \(\mathcal{O}(n \ln h)\) ist die theoretische untere Komplexitätsgrenze für 2D konvexe Hüllen. Beispielsweise Chans Algorithmus erreicht diese Komplexität mit einem trickreichen zweistufigen Prozess.

Zuerst teilt man die Punktwolke in zufällige Untermengen mit jeweils etwa \(m\) Punkten ein. Für jede berechnet man die konvexe Hülle, bspw. mit Andrews Algorithmus. Dann benutzt man Jarvis March, um die Hülle zu konstruieren, dabei muss man allerdings nicht mehr alle Punkte durchprobieren, sondern nur noch die Tangenten, die in der Animation mit grünen Strichen gekennzeichnet sind. Die Tangenten kann man für jede der \(k = \lceil \frac{n}{m} \rceil\) Sub-Hüllen effizient in \(\mathcal{O}(m)\) bestimmen. Dazu benutzt man einem Algorithmus, der an eine Binärsuche erinnert. Zusammen hat dies also eine Komplexität von \(\mathcal{O}((n+kh) \ln m)\).

Aber ich hatte \(\mathcal{O}(n \ln h)\) versprochen. Nun, um das zu erreichen, müssen wir einfach nur \(m \approx h\) wählen. Aber wie kommen wir an \(h\) bevor wir die Hülle berechnet haben? Der Trick ist, mit einem niedrigen \(m\) zu starten, dann nur \(m\) Schritte des Jarvis-Teils des Algorithmus durchzuführen und wenn die Hülle dann noch nicht fertig ist \(m\) zu erhöhen und es wieder von vorne zu beginnen. Damit dieser iterative Teil des Algorithmus nicht unsere Komplexität erhöht, muss \(m\) schnell genug wachsen, was in der Regel durch Quadrieren des alten Werten erreicht wird.

QuickHull

Zuletzt möchte ich hier noch QuickHull vorstellen, weil dieser Algorithmus meiner Meinung nach einen sehr hübschen rekursiven divide and conquer Ansatz verfolgt — ein bisschen wie QuickSort. In zwei Dimensionen starten wir mit dem Punkt ganz links \(A\) und ganz rechts \(B\). Dann finden wir den Punkt \(C\) der am weitesten entfernt ist von der Strecke \(\overline{AB}\) und links von der Strecke ist. Diesen Schritt wiederholen wir rekursiv auf den Strecken \(\overline{AC}\) und \(\overline{CB}\) (und \(\overline{BA}\) für die untere Hälfte.)

Mehr Dimensionen

Aber ich hatte Space Whales versprochen, also können wir uns nicht mit 2D zufrieden geben! Tatsächlich müssen wir schon beim Verallgemeinern auf 3D aufpassen. Schließlich konnten wir für 2D die konvexe Hülle als Sequenz von Punkten repräsentieren. Für höhere Dimensionen müssen wir sie allerdings als Menge von Facetten repräsentieren. Glücklicherweise tauchen für noch höhere Dimensionen dann keine weiteren Schwierigkeiten mehr auf — abgesehen von der Grundsätzlichen Schwierigkeit, dass höherdimensionale Gebilde deutlich größere Oberflächen haben und somit die konvexe Hülle aus deutlich mehr Facetten besteht, sodass die untere Schranke für die Komplexität für Dimension \(d\) durch \(\mathcal{O}(n^{\lfloor d / 2 \rfloor})\) gegeben ist.

Bevor ich hier QuickHull für \(d=3\) beschreibe, möchte ich darauf hinweisen, dass es die qhull Implementierung gibt, die sich bspw. auch um die subtilen numerischen Fehler kümmert, die sich bei sehr spitzen Winkeln einschleichen können.

Grundsätzlich bleibt das Vorgehen gleich: Wir starten mit einem \(d\)-dimensionalen Simplex, also für \(d=3\) mit einem Tetraeder, dessen Eckpunkte zur konvexen Hülle gehören. Dann führen wir für jede Facette den rekursiven Schritt durch: Finde den Punkt, der am weitesten vor der Facette (also außerhalb des Tetraeders) ist. Diesen Punkt nennt man Eye-Point. Denn es reicht jetzt im Gegensatz zum 2D Fall nicht mehr einfach neue Facetten aus den Rändern und dem neuen Punkt zu bilden. Stattdessen müssen wir alle Facetten, deren Vorderseite (also Außenseite) wir vom Eye-Point aus sehen können entfernen und neue Facetten mit dem Horizont und dem Eye-Point bilden. In der Animation unten sind der Eye-Point sowie die Facetten, die er sieht, rot dargestellt. Der Horizont ist mit schwarzen Strichen gekennzeichnet.

Wird dieser Schritt rekursiv auf alle neu hinzugefügten Facetten angewendet, resultiert die konvexe Hülle. Und genauso, wenn auch deutlich schwieriger darstellbar, funktioniert es auch für alle höheren Dimensionen.

Eine wichtige Anwendung für 3D konvexe Hüllen ist übrigens die Delaunay-Triangulation einer planaren Punktmenge. Die wiederum kann für eine effiziente Berechnung des Relative-Neighborhood-Graphs aus diesem Post genutzt werden.

Meine liebsten Probleme sind solche, die einfach scheinen aber sehr tief sind. Natürlich gehört das Problem des Handlungsreisenden dazu: Es ist einfach zu verstehen, dass der Müllmann bei jeder Mülltonne vorbei muss und dabei möglichst wenig Strecke fahren will. Gerade deshalb ist es das Paradebeispiel für NP-schwere Probleme (technisch gesehen ist nur seine Entscheidungs-Version „Gibt es eine Tour, die kürzer ist als \(X\)“ NP-schwer und nicht die typische Optimierungsversion: „Welche ist die kürzeste Tour“).

Aber fast noch besser gefällt mir das Problem der längsten aufsteigenden Teilfolge, oder auf englisch, longest increasing subsequence (LIS): Gegeben eine Folge von Zahlen \(S_i\), welche Teilfolge ist am längsten unter der Bedingung, dass die Zahlen aufsteigen.

Dieses Problem ist so einfach, dass es erstmals von Stanisław Ulam als Fingerübung beschrieben wurde und nach meinem Eindruck heutzutage als Übung für dynamische Programmierung in Universitäten verwendet wird. Wer weiß wie viele Bewerber vor einem Whiteboard ins Schwitzen geraten sind bei dem Versuch es aus dem Stegreif zu lösen.

Auf der anderen Seite ist es aber offenbar tief genug, dass man ganze Bücher darüber schreiben kann. Es zeigen sich überraschende Querverbindungen zu scheinbar unabhängigen Problemen. Denn die Länge \(L\) der LIS einer Permutation fluktuiert genauso wie der Abstand von der Mitte zum Rand eines Kaffeeflecks oder die größten Eigenwerte von Zufallsmatrizen.

Nun ist die Lösung dieses Problems nicht eindeutig: Es kann viele längste aufsteigende Teilfolgen geben. Tatsächlich wächst die Anzahl sogar exponentiell mit der Länge der ursprünglichen Sequenz.

Allerdings wurde bisher nie untersucht wie viele genau. Oftmals hört man, es sei nicht praktikabel alle durchzuzählen, da es exponentiell viele seien. Und wenn es darum ginge alle zu enumerieren, würde das stimmen. Aber wir wollen an dieser Stelle nur die Anzahl wissen, die wir mittels dynamischer Programmierung effizient bestimmen können. Die Idee ist, dass wir für jedes Element, das an Position \(x\) in einer LIS auftauchen kann, berechnen, wie viele aufsteigende Teilfolgen der Länge \(L-x\) mit diesem Element beginnen.

Besonders einfach geht das, wenn wir zuerst eine Datenstruktur aufbauen, die kodiert welche Elemente in einer LIS aufeinander folgen können. Dazu erweitern wir Patience Sort, und da dieser Algorithmus nach einem Kartenspiel benannt ist, werden wir es auch mit Karten visualisieren: Wir schreiben jedes Element unserer Sequenz auf eine Karte und legen die Karten auf einen Stapel, sodass das erste Element der Sequenz oben liegt. Dann nehmen wir Karten von oben ab und legen sie auf verschiedene Stapel. Die erste Karte legen wir auf den ersten, noch leeren Stapel. Die folgenden Karten legen wir auf den ersten Stapel, dessen oberstes Element größer ist als die aktuelle Karte und ansonsten machen wir einen neuen Stapel rechts davon auf. Jedes mal wenn wir eine Karte ablegen, lassen wir sie auf alle Karten, die aktuell auf dem Vorgängerstapel liegen und kleiner sind, zeigen — dies sind die Karten die in einer aufsteigenden längsten Teilfolge direkt vor ihr auftauchen können.

Am Ende haben wir \(L\) Stapel, wobei \(L\) die Länge der LIS ist, und wir können vom Stapel ganz rechts starten und den Pfeilen folgen, um eine LIS zusammenzubauen. Wenn wir nur an der Länge interessiert wären, müssten wir uns über den Inhalt der Stapel keine Gedanken machen und der Algorithmus ließe sich sehr kompakt darstellen:

fn lis_len<T: Ord>(seq: &[T]) -> usize {
    let mut stacks = Vec::new();
    for i in seq {
        let pos = stacks.binary_search(&i)
            .err()
            .expect("Encountered non-unique element in sequence!");
        if pos == stacks.len() {
            stacks.push(i);
        } else {
            stacks[pos] = i;
        }
    }
    stacks.len()
}

Aber wir wollen mehr, deshalb notieren wir uns im nächsten Schritt bei allen Karten des rechtesten Stapels wie viele aufsteigende Teilfolgen der Länge \(x=1\) mit ihnen starten, was trivialerweise je eine ist. Dann notieren wir bei allen Karten des Stapels links davon wie viele aufsteigenden Teilfolgen der Länge 2 mit ihnen anfangen. Das können wir berechnen, indem wir den Pfeilen rückwärts folgen und die Annotationen jeweils aufaddieren. Nachdem wir dies für alle Stapel wiederholt haben und den linkesten Stapel beschriftet haben, können wir alle Annotationen des linkesten Stapels aufaddieren, um die gesamte Anzahl LIS zu erhalten: hier \(7\).

Wie sich das ganze für längere Sequenzen aus unterschiedlichen Zufallsensembles im Detail verhält haben wir in einem Artikel veröffentlicht.

In diesem Artikel wird ein Ensemble von Problemen des Handlungsreisenden (TSP) eingeführt, das abhängig von einem Parameter \(\sigma\) von einer trivial einfach zu lösenden Konfiguration, nämlich Städte, die äquidistant auf einem Kreis angeordnet sind, zum zufälligen euklidischen TSP in der Ebene interpoliert.

Danach werden mittels linearer Programmierung einige Phasenübergänge festgestellt, ab welchen Werten von \(\sigma\) das Problem schwierig zu lösen wird. Zu zwei dieser Übergänge werden strukturelle Eigenschaften der optimalen Lösung gefunden, die sich an dieser Stelle ebenfalls charakteristisch ändern. Da die optimale Lösung nicht von der Lösungsmethode abhängt, sind diese Phasenübergänge also nicht nur von Bedeutung für das spezielle Lineare Programm bzw. den Algorithmus der zu dessen Lösung genutzt wurde, sondern fundamentale Eigenschaft dieses TSP Ensembles.

Im Detail haben wir die klassische Formulierung von Dantzig genutzt:

Hier ist \(c_{ij}\) die Distanzmatrix zwischen allen Paaren von Städten aus \(V\) und \(x_{ij}\) die gesuchte Adjazenzmatrix, also \(x_{ij} = 1\), wenn \(i\) und \(j\) aufeinanderfolgende Stationen der Tour sind und \(x_{ij} = 0\) sonst. Die erste Zeile minimiert also die Strecke der Tour. Um zu vermeiden, dass wir die triviale Lösung \(x_{ij}=0\), also „wenn wir zu Hause bleiben müssen wir am wenigsten Strecke zurücklegen“ finden, zwingt die dritte Zeile unseren Handlungsreisenden seine Tour so zu planen, dass in Summe zwei Striche an jede Stadt gezeichnet werden — genug, um hinein und wieder hinaus zu reisen. Allerdings, ist unser Handlungsreisender clever und würde versuchen uns auszutricksen, indem er halbe Striche einzeichnen würde, wie in einem anderen Blogeintrag visualisiert. Deshalb ist die Bedingung in der zweiten Zeile nötig, die die Einträge in der Adjazenzmatrix auf ganze Zahlen beschränkt. Dann bleibt nur noch das Problem, dass mehrere Routen, die nicht verbunden sind erlaubt wären, sodass wir sie durch die letzte Zeile verbieten: die Subtour Elimination Constraints. Der aufmerksame Leser mag schon erkannt haben, dass es für jede Untermenge von Städten so eine Constraint definiert, also exponentiell viele in der Anzahl der Städte. Die Lösung zu dieses Problem liegt darin, dass nur sehr wenige wirklich gebraucht werden, sodass man das Problem ohne diese Constraint löst, testet ob eine verletzt ist, was mittels der Berechnung eines minimum cut sehr schnell geht und dann eine einzelne Constraint, die diese Konfiguration verbietet hinzufügt. Diese Methode iterativ Constraints hinzuzufügen wird meist als Cutting Planes bezeichnet.

Also haben wir einen schnellen Algorithmus für das Problem des Handlungsreisenden gefunden? Nein, leider können wir den Millenium Preis noch nicht beanspruchen. Es gibt keinen bekannten Algorithmus, der dieses Problem unter Erfüllung der zweiten Zeilen, also Beschränkung auf ganzzahlige Lösungen lösen kann. Aber sobald wir diese Bedingung fallen lassen, können wir klassische Verfahren der linearen Programmierung nutzen, um dieses Problem effizient zu lösen. Dies wird auch Relaxation genannt. Die Länge der Strecke ist immer eine untere Schranke für die tatsächliche Lösung. Und wenn unsere Lösung per Zufall ganzzahlig ist, können wir uns sicher sein, die Optimale Lösung gefunden zu haben.

Als Ordnungsparameter des Phasenübergangs zwischen leichten und schweren Konfigurationen dient uns also die Wahrscheinlichkeit, dass mittels eines Simplex-Solvers eine ganzzahlige, und damit optimale, Lösung gefunden wird. Ohne die Subtour Elimination Constraints, fällt der Phasenübergang auf den Punkt, an dem sich die optimale Lösung erstmals von der Reihenfolge der Städte des ursprünglichen Kreises unterscheidet. Mit den Subtour Elimination Constraints, fällt der Phasenübergang auf den Punkt, wo die optimale Tour anfängt von einem Zickzack-Kurs auf große Meander zu wechseln. Dies wird durch die geometrische Gewundenheit, die Tortuosität,

ermittelt, die an diesem Punkt maximal wird. Hier wird die Tour in \(N\) Teilstücke mit gleichem Vorzeichen der Krümmung unterteilt und für jedes Teilstück das Verhältnis von direkter Ende-zu-Ende-Distanz \(S_i\) zu der Länge entlang der Tour \(L-i\) summiert.

Wir haben also kontinuierliche Phasenübergänge in der Schwierigkeit dieses Problems mittels linearer Programmierung detektiert und sie mit strukturellen Änderungen des Verhaltens in Verbindung gebracht.