Es gibt wieder mal einen Überblick zu einem Modul der Fernuni Hagen von mir. Diesmal, weil das Modul “Algorithmische Geometrie” sehr umfrangreiche Themen abdeckt, meine Zeit bei der Vorbereitung aber etwas knapp war. Deshalb habe ich wieder darauf gesetzt, mit einem Blog-Eintrag einen Überblick über das gesamte Skript zu erlangen.

Da meine Zeit in der Vorbereitung knapp war, gibt es diesmal einige Stellen, die mit “TODO” markiert sind. “TODO” bedeutet, dass ich mir diese Stellen nicht so genau angesehen habe, wie es sonst zur Vorbereitung eigentlich nötig wäre.

Ich empfehle allen, die das Modul ebenfalls belegen und prüfen lassen, den Studientag zu besuchen (besonders wenn er wie dieses Semester digital stattfinden sollte). Außerdem lohnt sich ein Blick in die älteren Prüfungsprotokolle; man kriegt einen recht guten Einblick, wie Herr Icking seine Prüfungen aufbaut.

Insbesondere sollte man genau wissen, welche “großen” Probleme im Skript behandelt werden und welche Algorithmen zu ihrer Lösung existieren (natürlich inklusive, wie die Algorithmen funktionieren, welche Laufzeit sie haben und warum gerade diese Laufzeit).

Einführung

  • Anwendungsbeispiele: Bahnplanung, geographische Daten, Schnittmuster
  • Topologie:
    • Definition Metrik
    • Epsilon-Umgebung, Innerer Punkt einer Menge, Rand einer Menge, Abschluss einer Menge
    • offene und abgeschlossene Mengen
    • beschränkte Mengen, Durchmesser einer Menge
    • Wege, Länge eines Weges
    • Gebiete: offene, wegzusammenhängende Mengen im zweidimensionalen Raum
    • Zerlegung in Zusammenhangskomponenten
  • Graphen:
    • Homotopie, äquivalente Graphenrealisierungen
    • planare Graphen
    • Eulersche Formel
    • Dualer Graph
    • Doubly Connected Edge List, Quad Edge Data Structure
  • Geometrie:
    • Polygonzug, Polygon, Sichtbarkeit, Polyeder
    • Stützgerade, Stützebene
    • konvexe Hülle
    • Satz des Pythagoras, Kosinussatz, Sinussatz
    • Kreiswinkelsatz / Satz des Thales
    • Bisektor
  • Komplexität:
    • REAL RAM
    • Obere Schranke, untere Schranke, Theta-Notation
    • randomisierte und deterministische Algorithmen
    • Elementtestproblem
    • Epsilon-Closeness
    • Reduktion von Epsilon-Closeness: Am Beispiel Sortieren von Zahlen und All Nearest Neighbors
    • Mannigfaltigkeit

Sweep-Verfahren

  • Einführung im Eindimensionalen
    • Maximum einer Menge
    • Closest Pair
    • Maximale Teilsumme
    • Zusammenhang: Maximale Teilsumme wird später bei Berechnung des Kerns eines Polygons verwendet
  • Sweep in der Ebene
    • Dichtestes Punktepaar:
      • Streifen in Breite MinSoFar für Sweep-Status-Struktur (enthält alle Punkte, die im Streifen MinSoFar sind); Einschränkung in Y-Richtung über Bereichsanfrage
      • für Bereichsanfrage genügt in diesem Fall eine eindimensionale Datenstruktur, da man in den Punkten im Sweep-Streifen nur noch nach Y-Koordinate filtern muss (Kosten Bereichsanfrage dann O(log n + k))
      • maximal 10 Punkte mit Mindestabstand M können in einem Rechteck der Kantenlängen 2M x M liegen (Beweis: die Kreisumgebung von jedem Punkt liegt mindestens zu 1/4 in diesem Rechteck)
    • Schnittpunkte von Liniensegmenten: Existenzproblem und Aufzählungsproblem
      • Untere Schranke Existenzproblem (n log n): Reduktion von Epsilon-Closeness auf Schnittpunkte von Liniensegmenten
      • Existenzproblem: Teste Nachbarn auf Schnitt, sobald sie zu Nachbarn werden (Laufzeit O(n log n), Speicherplatz O(n))
      • Aufzählungsproblem: Neues zusätzliches Ereignis für Schnittpunkte, da Reihenfolge der beteiligten Liniensegmente am Schnittpunkt vertauscht wird (Laufzeit O((n + k) log n), Speicherplatz O(n + k))
      • Lösen von einschränkenden Annahmen:
        • Rotation des Koordinationsystems, um Punkte auf gleicher x-Koordinate zuzulassen
        • Sortieren der Schnittpunkte nach lexikographischer Reihenfolge, um Mehrfachschnitte zu erlauben
    • TODO: Untere Konturlinie
      • Untere Konturlinie von Wegen
      • Einfacher Ansatz: Gleicher Algorithmus wie bei Segmentlinien-Schnitt, aber dessen Laufzeit ist abhängig von Anzahl aller Schnittpunkte (ergibt Laufzeit O(sn^2 log n)
      • Algorithmus: Divide-and-Conquer + Sweep zum Zusammenführen
      • Sweep-Ereignisse: Ecken der Konturen und Schnittpunkte der Konturen
      • Davenport-Schinzel-Sequenz: Laufzeit des Algorithmus in O(\lambda_s(n) log n)
      • Untere Konturlinie von (geraden) Liniensegmenten: Einführen von steigenden und fallenden Segmenten, sodass Intervallbereich aller Linien gleich ist
    • TODO: Durchschnitt zweier Polygone
      • Test, ob Schnittmenge nicht-leer ist
      • Ermitteln der Durchschnitt-Polygone
      • Sweep-Status-Struktur:
        • Kanten, die Sweep-Line schneiden
        • für Intervalle auf Sweep-Line: Gehören sie zu Q \intersect P, etc…
        • Kantenfolgen des bisher gefundenen Schnittpolygons
      • Sweep-Ereignisse: Eckpunkte und Schnittpunkte
      • Laufzeit: O((n + k) log n) für n Kanten und k Kantenschnittpunkte
      • Spezialfall: Berechnung des Durchschnitts konvexer Polygone (O(n))
    • Sweeps mit Kreisen
  • Sweeps im Raum: Dichtestes Punktepaar im Raum
    • Bereichsanfrage am besten mit einem statischen 3D-Bereichsbaum; dies ist schneller als einen dynamischen 2D-Baum (kd-Baum) zu verwalten und Punkte nach der Sweep-Line einzufügen und zu entfernen
  • Output-Sensitivität von Algorithmen

Konvexe Hülle und Sichtbarkeit

Konvexe Hülle

  • Beweis der Komplexität durch Reduktion des Sortierproblems
  • Beweis: Rand der konvexen Hülle = kürzester geschlossener Weg, der die Punktmenge umschließt
  • Konstruktion:
    • Inkrementelles Verfahren mit Suchbaum (O(n log n))
      • Schritt 1: Prüfen, ob p in konvexer Hülle liegt (O(log n))
        • Prüfe, in welchem Sektor in Relation zu einem Punkt z der Punkt p liegt
        • Prüfe, auf welcher Seite des Liniensegments des Sektors p liegt
      • Schritt 2: Konstruktion der Tangenten (insgesamt O(n))
        • Suche vom bekannten Sektor aus nach links und rechts die Tangentenpunkte
    • Inkrementelles Verfahren mit Array (Erwartete Laufzeit O(n log n) durch Randomisierung)
      • Array speichert für jeden Punkt Schnittkante mit derzeitiger konvexer Hülle
      • Konfliktpaare: randomisierte Einfügereihenfolge für Kanten
    • Divide and Conquer:
      • Separieren der Punkte durch senkrechte Trennlinie
      • Zusammenfügen der beiden Teillösungen durch Finden der Tangente (“Hochschaukeln” von bekannten Max/Min-Punkten)
      • Startpunkt fürs Hochschaukeln sind die Punkte mit maximaler und minimaler X-Koordinate
    • Konturpolygon-Verfahren:
      • Berechne Konturpolygon P, ein Polygon, dessen Ecken zur Punktemenge gehören und das alle Punkte enthält (im Sweep-Line-Verfahren in O(n) bei sortierten Punkten)
        • Sweep von links mit MinYSoFar und MaxYSoFar für linke Konturlinie
        • Sweep von rechts mit MinYSoFar und MaxYSoFar für rechte Konturlinie
      • Berechne konvexe Hülle von P (insgesamt O(n), weil entfernte Kanten später nicht mehr betrachtet werden)
  • Dualität des Schnitts unterer Halbebenen zur unteren Kante der konvexen Hülle der dualen Punkte

Sichtbarkeit (TODO)

  • Sichtbarkeitspolygon:
    • Von einem sichtbaren Punkt entlanglaufen auf Rand
    • Fallunterscheidungen für Ereignisse
    • Äquivalenzklassen von Punkten und Sichtregionen des Polygons
    • Beweis: Anzahl Sichtregionen ist durch n^3 beschränkt
  • Kern eines Polygons
    • Definition: sternförmiges Polygon, Kern eines Polygons
    • Ein Ansatz: Durchschnitt von Halbebenen in O(n log n)
      • entweder im Divide-and-Conquer-Verfahren mit Merge von konvexen Polygonen
      • oder über Konversion von Geraden in Punkten und Lösen der konvexen Hülle (Dualität)
    • Weiterer Ansatz: Berechnung über maximalen Drehwinkel in O(n)
      • maximaler Drehwinkel >= 3 Pi: leerer Kern
      • maximaler Drehwinkel < 3 Pi: Definiere Kantenfolgen F und B, diese enthalten alle wesentlichen Kanten
      • Berechnung maximaler Drehwinkel: maximale Teilsummen aus Kapitel 2
      • Berechnung Durchschnitt von Halbebenen, die nach Steigung sortiert sind (vgl. Kapitel 3 früher)
      • Berechnung Schnittmenge zweier konvexer Polygone (Kapitel 2)

Triangulationen und geometrische Datenstrukturen

Triangulation

  • Dualer Graph zur Triangulation bildet einen Baum
  • Triangulation konvexer Polygone (O(n)): Wähle beliebige Ecke und verbinde mit allen anderen Nicht-Nachbar-Ecken
  • Triangulation monotoner Polygone (O(n))
    • Sortieren in diesem Fall in O(n), da die Ecken auf dem Polygon bereits vorsortiert sind
    • Fall 1: Punkte aus verschiedenen Polygonketten
    • Fall 2: Punkte aus gleichen Polygonketten
  • Zerlegung in monotone Polygone (O(n log n))
    • Sweep-Line von oben nach unten und von unten nach oben zur Entfernung der horizontalen spitzen Ecken
    • Verwaltung der SSS durch Fallunterscheidung nach Lage der Kanten im Vergleich zur Sweep-Line
      • beide Kanten oberhalb
      • eine Kante oberhalb eine unterhalb
      • beide Kanten unterhalb
    • Speichere während Durchlauf immer einen niedrigsten/höchsten Punkt “kurz vor Sweep-Line”, der bei einer gefundenen spitzen Ecke als Partner für die Diagonale dient
    • Füge während Sweep Diagonalen an spitzen Ecken ein
  • Anwendung: Kunstgalerie-Problem
    • Anzahl Wächter im Allgemeinen Fall: Abgerundet(n/3)
      • Beweis untere Schranke über Beispiel (Toblerone-Polygon)
      • Beweis obere Schranke über 3-Färbbarkeit der Kanten der triangulierten Dreiecke
    • Triangulation und 3-Färbbarkeit liefert auch Konstruktion für Lösung
  • Triangulation von Polyedern:
    • Anzahl der Tetraeder nicht eindeutig
    • teilweise nur lösbar, wenn man neue Eckpunkte einführt

Datenstrukturen

  • Grundlagen:
    • Anfragemethoden: Schnittanfragen und Inklusionsanfragen
    • Speicherort der Daten: interne und externe Daten
    • statische und dynamische Datenstrukturen
  • k-d-Baum
    • Laufzeit Bereichsanfragen bei ausgeglichenem Baum in 2D: O(sqrt(n) + a)
    • Konstruktion ausgeglichener Baum in O(n log n)
    • Speicherplatz: O(n)
    • ausgeglichen: für jeden inneren Knoten gilt, Blattzahl der beiden Teilbäume unterscheidet sich um maximal eins
    • Erweiterter k-d-Baum, wenn Punkte gleiche x- oder y-Koordinaten haben dürfen: 1-D-Suchbaum für Punkte direkt auf der Trenngeraden
    • Ausgeglichenheit für erweiterte k-d-Bäume
  • Bereichsbaum
    • k-dimensionaler Bereichsbaum: rekursive Definition aus 1-dimensionalem Bereichsbaum, dessen Knoten auf k-1-dimensionale Bereichsbäume verweisen
    • Anfrage: O((log n)^k + a)
    • Konstruktion: O(n (log n)^(k - 1))
    • Speicherplatz: O(n (log n)^(k - 1))
  • Prioritätssuchbaum:
    • nur für 2D-Punkte
    • Sortiere Punkte nach X-Koordinate wie in einem Suchbaum, nach Y-Koordinate wie in einem Heap (aufsteigend)
    • Aufbau der Datenstruktur in O(n log n)
    • Beantwortung von Halbstreifen-Anfragen in O(log n + a)
    • Übertragung: Lösen von Intervall-Überlappung mittels Prioritätssuchbaum und Bereichsanfrage
    • Idee für Rechtecksanfragen: Für fixe Höhe h, zerlege Raum in horizontale Streifen der Höhe h. Dann liegt jedes Anfragerechteck der Höhe h in maximal zwei Streifen: Für oberen Streifen nach unten offenen Prioritätssuchbaum, für unteren Streifen nach oben offenen Prioritätssuchbaum. Damit O(log n + a) erreichbar.
  • Anwendung: Dichtestes Punktepaar im Raum
    • Variante 1: 2D-Bereichsanfrage für alle Punkte, die sich in einem Streifen der Breite MinSoFar hinter aktuellem Punkt befinden. Benötigt dynamischen Suchbaum.
      • Laufzeit Anfrage: O(sqrt(n) log(n))
    • Variante 2: 3D-Bereichsanfrage, kommt mit statischem Suchbaum aus
      • Laufzeit Anfrage: O(n (log n)^3)

Voronoi-Diagramm

  • Punkte in Voronoi-Regionen, auf -Kanten und auf -Knoten: Unterscheidung nach Anzahl der nächsten Nachbarn
  • Unbeschränkte Voronoi-Regionen für Punkte auf Rand der konvexen Hülle, Beweis über eine Halbgerade in Voronoi-Region, auf die wir einen Kreis legen
  • Voronoi-Regionen von Punkten mit minimalem Abstand haben eine gemeinsame Kante
  • beschränktes Voronoi-Diagramm: Unbeschränkte Gebiete werden von einem umkreisenden geschlossenen Weg begrenzt
  • Berechnung der konvexen Hülle aus Voronoi-Diagramm in O(n). Daraus folgt: Konstruktion von Voronoi-Diagramm muss mind. O(n log n) dauern, sonst könnten wir über Reduktion von Sortieren auf Voronoi + konvexe Hülle schneller sortieren.
  • Anwendungen:
    • Suche nach nächstem Postamt
      • Finden der Voronoi-Region zu einem Punkt über Streifenmethode
      • Bestimmung des passenden Streifen (Binärsuche), dann Binärsuche über die in diesem Streifen in X-Richtung vorhandenen Voronoi-Regionen
      • Laufzeit Suche der Region: O(log n)
    • Bestimmung aller nächsten Nachbarn
      • In Zeit O(n), weil nächste Nachbarn eine gemeinsame Kante im Voronoi-Diagramm haben und es nur O(n) Kanten gibt
      • Bestimmung dichtestes Punktepaar damit ebenfalls in O(n), wenn Voronoi-Diagramm vorhanden
    • minimaler Spannbaum
      • Mit bekannten nächsten Nachbarn kann der Spannbaum analog zu Kruskal in O(n log n) aufgebaut werden
      • Traveling Salesman Problem: Rundreise um den minimalen Spannbaum weniger als doppelt so lang wie optimaler Rundweg
      • kurze Erklärung Steinerbaum
    • Größter leerer Kreis (innerhalb von konvexem Gebiet A)
      • gesuchter Punkt liegt auf Voronoi-Knoten, Schnittpunkt von A mit Voronoi-Kante oder auf Rand von A
      • Berechnung für vorhandenes Voronoi-Diagramm in O(n + m) bei m Ecken von A
  • Delaunay-Triangulation
    • kreuzungsfreie, geometrische Realisierung des dualen Graphen des Voronoi-Diagramms
    • Konvexe Hülle von S ist Teil von Delaunay-Zerlegung von S
    • Minimaler Spannbaum von S ist Teil von Delaunay-Zerlegung von S
    • Delaunay-Zerlegung besteht aus Dreiecken, wenn jeder Voronoi-Knoten nur drei nächste Punkte hat
    • Delaunay-Triangulation hat größte Winkelfolge (der kleinsten Winkel) unter allen Triangulationen, wenn im Voronoi-Diagramm maximal drei Kanten in einem Knoten zusammenlaufen
    • Umrechnung zwischen Delaunay-Triangulation und Voronoi-Diagramm in O(n)
    • Drei Punkte a, b, c bilden genau dann ein Delaunay-Dreieck, wenn sich im Umkreis durch a, b, c keine anderen Punkte befinden
  • TODO: Verallgemeinerungen
    • andere Metriken als die euklidische Metrik
    • Voronoi-Diagramme von Liniensegmenten
      • Bisektor von Liniensegment und Punkt besteht aus drei Segmenten
        • Segment 1 und 3: “normaler” Bisektor zwischen Punkt und Endpunkt des Liniensegments
        • Segment 2: Parabel
      • Bisektur von zwei Liniensegmenten besteht aus maximal sieben Segmenten, je nach Einfluss der Linien
        • Einfluss von Endpunkt und “Liniensegment”: Parabel
        • Einfluss von zwei “Liniensegmente”: Liniensegment, Winkelhalbierende
        • Einfluss von zwei Endpunkten: Halbgerade
      • Voronoi-Regionen von Liniensegmenten sind sternförmig: Für jeden Punkt x in einer Region ist die gesamte Strecke von x zum nächsten Punkt auf dem Liniensegment in der Voronoi-Region
      • Anwendung: Bewegungsplanung für Roboter

Berechnung des Voronoi-Diagramms

  • Beweis untere Schranke zur Konstruktion O(n log) über Reduktion von Epsilon-Closeness
  • Inkrementelle Konstruktion der Delaunay-Triangulation
    • Prüfen neu eingefügter Punkte auf Konflikte mit bestehenden Dreiecken
      • Fall 1: Punkt p liegt in konvexer Hülle der bisherigen Triangulation:
        • Verbinden von p mit Eckpunkten des Delaunay-Dreiecks, in dessen Umkreis er liegt (ggfs. auch außerhalb des Dreiecks selbst)
        • Finden von weiteren Konfliktpunkten, d.h. weiterer Punkt liegt im Umkreis eines Dreiecks: Edge Flips
        • Testen aller Nachbardreiecke auf Konflikt, so lange bis keine Konflikte mehr auftreten
      • Fall 2: Punkt liegt außerhalb der konvexen Hülle: Kante zwischen neuem Punkt und jedem von diesem aus sichtbaren Punkt der bisherigen konvexen Hülle
    • Delaunay-DAG zur schnelleren Lokalisierung:
      • für ein Dreieck, das mit p in Konflikt steht, gibt es einen Pfad im Delaunay-DAG, der nur aus Knoten besteht, die mit p in Konflikt stehen; also Tiefensuche und Stop bei jedem Knoten, der nicht mit p in Konflikt steht
      • Einfügen eines neuen Punktes p dann in O(m) mit m = Anzahl der Dreiecke deren Vater/Stiefvater in Konflikt mit p stehen
    • TODO: Randomisierung ergibt im Mittel O(n log n)
    • Jedes inkrementelle Verfahren hat eine Worst-Case-Laufzeit von O(n^2)
  • Sweep
    • beziehe Sweep-Line in die Berechnung des aktuell gültigen Voronoi-Diagramms mit ein, es entstehen Parabelbögen (Wellenfront)
    • Verlängerungen der geraden Bisektoren über Wellenfront hinaus heißen “Spikes”
    • Sweep-Status-Struktur: Wellenfront
    • Sweep-Status-Update:
      • Spike-Ereignisse: Ein Wellenstück verschwindet, weil es auf den Schnittpunkt seiner beiden Spikes trifft; neuer Spike durch neue Nachbarn kann entstehen
      • Punkt-Ereignisse: Neuer Punkt wird entdeckt, neue Welle entsteht
  • TODO: Divide and Conquer
    • Bestimmung der Splitgeraden über zwei Verzeichnisse, die Punkte sortiert nach X- und Y-Koordinaten beinhalten
    • Merge-Schritt:
      • Neue Kanten sind solche zwischen Punkten aus linker und rechter Menge (Bisektor von L und R ist polygonale Kette) = Menge aller Punkte, die nächsten Nachbarn in L und R haben
      • Kanten innerhalb einer Menge existieren bereits, sind aber möglicherweise zu lang
      • Schritt 1: Suche eines der beiden unbeschränkten Endstücke des Bisektors von L und R (in Umkreis der Schnittmengen aus Voronoi-Regionen aus L und R)
      • Schritt 2: Verfolge Bisektor durch die einzelnen Voronoi-Regionen, beim Wechsel einer Region (neuer nächster Nachbar) ändert sich immer die Richtung des Bisektors (O(n))
  • Reduktion auf konvexe Hülle im Dreidimensionalen
    • konvexe Hülle im R^3 in O(n log n) berechenbar
    • Wichtige Rekapitulation: Drei Punkte bilden ein Delaunay-Dreieck gdw. ihr Umkreis keinen anderen Punkt beinhaltet
    • Projektion eines Kreises aus der Ebene auf ein Paraboloid liegen dort in einer Schnittebene
    • Zusammenhang R^2 und R^3: Punkte innerhalb des Umkreises im R^2 entsprechen gerade den Punkten am Paraboloid unterhalb der Schnittebene; wenn es also keine Punkte im Umkreis gibt, gibt es keine Punkte unterhalb der Schnittebene
    • Damit bildet der von sichtbare Teil der konvexen Hülle im R^3 (ein Polyeder) gerade die Delaunay-Triangulation der Punktmenge im R^2
    • Laufzeit eines Algorithmus für konvexe Hülle im R^3: O(n log n)

Unvollständige Information

  • Ausweg aus einem Labyrinth
    • Pledge-Algorithmus: Folge Wand, bis Winkelzähler wieder auf 0 steht
      • Winkelzähler nimmt immer nur positive Werte an (auch größer als 2 Pi)
      • Endliche Zahl von Eckpunkten des Weges, daher entweder Endlosschleife oder Entkommen aus Labyrinth
  • Finden eines Zielpunkts
    • Bug (mit Koordinaten): Gehe direkt auf Ziel zu, umkreise Hindernisse einmal komplett, vom nächsten Punkt zum Ziel aus laufe in Richtung Ziel
      • Beweis für korrekten Ablauf darüber, dass jedes Hindernis nur einmal besucht wird
      • nicht kompetitiv, Weg kann beliebig viel länger sein als kürzester Weg
    • Zielsuche mit Kompass:
      • Ausprobieren bis zum universellen Steuerwort führt in Theorie zum Ziel (in Praxis aber in unbrauchbarer Zeit)
  • Definition: Kompetitivität
  • Bin Packing:
    • First-fit ist 2-kompetitiv
    • Beweisansatz: maximal ein Behälter kann nur halbvoll sein
  • Suche nach der Tür in der Wand:
    • Vergrößerung der Suchweite pro Richtung um 1m nicht kompetitiv
    • Verdopplung der Suchweite pro Richtung 9-kompetitiv
    • TODO: Beweis untere Schranke?
  • Exponentielle Vergrößerung der Suchtiefe in Flächen
    • auch bei mehreren Strahlen anwendbar: Kompetitivität dann abhängig von Anzahl der Strahlen
    • Benutze Shortest Path Tree im Polygon zur Suche nach einem Punkt t
  • Kern eines Polygons:
    • Untere Schranke für Kompetitivität: Sqrt(2)
    • CAB (Continuous Angular Bisector):
      • Bewege Roboter so, dass sich Sichtbarkeitspolygon vergrößert
      • wesentliche spitze Ecken spannen einen “Gewinnbereich” auf, in den der Roboter sich bewegen muss
      • Fälle:
        • zwei wesentliche spitze Ecken schränken Gewinnbereich ein
        • eine der beiden wesentlichen Ecken liegt außerhalb des Gewinnbereichs
        • nur eine wesentliche Ecke definiert den Gewinnbereich
        • Haltebereich
      • selbstnähernder Weg: Wenn alle Punkte des nachfolgendes Weges nach p innerhalb der Halbebene liegen, die durch die Normale durch den Punkt p gebildet wird (d.h. wenn man beim Vorwärtslaufen auf dem Weg dem Ziel immer näher kommt)
      • alle Segmente des CAB-Weges sind selbstnähernde Wege und ein selbstnähernder Weg kann höchstens so lang sein wie der Umfang seiner Endpunkte: also ist CAB-Weg höchstens 2-Pi-mal so lang wie der kürzeste Weg
      • TODO: Beweis der Kompetitivität und selbstnährende Wege
I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to blog@stefan-koch.name.