Diese Seite richtet sich an die Lesenden des Buchs Algorithmische Geometrie von Klein, Driemel, und Haverkort. Die folgenden Links verweisen auf externe Inhalte, die das Buch ergänzen oder illustrieren können. Fragen dazu sollten am besten direkt an die entsprechenden AutorInnen gerichtet werden.

(Seiten können verschwinden. Bitte sagen Sie uns Bescheid, falls ein Link nicht mehr funktioniert.)

Noch keine bekannt. Bitte sagen Sie uns Bescheid, falls Sie Fehler finden.

* GeoGebra, ein Tool um geometrische Konfigurationen interaktiv darzustellen und zu untersuchen. Zum Beispiel kann man einen Kreis zeichnen, drei Punkten auf den Kreisrand legen, und sich die Winkel in dem dadurch definierten Dreieck anzeigen lassen. Dann kann man die Punkte entlang des Kreisrandes bewegen und den Satz des Thales in Aktion sehen. Auch komplexere Konfigurationen lassen sich auf ähnliche Weise mit GeoGebra untersuchen.

* Ipe, ein Zeichenprogramm von Otfried Cheong, das Geometer*innen zwei große Vorteile bietet: perfekte mathematische Formeln und Symbole dank Beschriftung mit integriertem LaTeX, und ausgezeichnetes “snapping”, so dass z.B. Linien die einander in einem Punkt treffen sollen, Punkte die auf einem Kreis liegen sollen usw. das auch wirklich machen. Viele geometrische Konfigurationen lassen sich dadurch ganz genau zeichnen. Auch Folien/Präsentationen lassen sich mit Ipe prima machen!

* Paul Heckbert's C++-Implementation einer Quad-Edge-Datenstruktur

* Herman Haverkort's C++-Implementation einer Quad-Edge-Datenstruktur

* CGAL, eine C++-Bibliothek für geometrische Algorithmen.

* Eine Demo des Graham Scan Algorithmus zur Berechnung der konvexen Hülle einer Punktmenge in der Ebene ( Wolfram Player benötigt). (Aaron T. Becker, Yitong Lu, Daniel Biediger); Ein ausfühliches Erklärvideo von Aaron T. Becker dazu.

* Eine interaktive Demo der Zerlegungsgleichheit von Polygonen: über die Triangulierbarkeit von Polygonen wird gezeigt, dass man, gegeben zwei Polygone, das erste immer so zerschneiden kann, dass sich aus den Teilen das zweite Polygon zusammensetzten lässt. (Dima Smirnov, Zivvy Epstein)

* Ruler of the Plane: einige einfache Spiele, die auf Fragestellungen der algorithmischen Geometrie basieren, u.A. “Conquer” (zwei Spieler versuchen Punkte so zu platzieren, dass ihre Voronoi-Regionen möglichst groß sind) und “Illuminate” (finden Sie die optimale Anzahl von Punkten, die einen Raum ausleuchten können— das Kunstgalerie Problem). (Sander Beekhuis, Kevin Buchin, Thom Hurks, Stijn Slot)

* Der Sweep-Algorithmus für Voronoi-Diagramme: eine interaktive Demo. (Edward Zhang)

* Vorosketch, ein einfaches Tool um verschiedene Arten von Voronoi-Diagrammen zu skizzieren (C++-Compiler benötigt). (Herman Haverkort)

* AGB-DTVD, eine C++-Implementation der Algorithmen für Delaunay-Triangulationen und Voronoi-Diagrammen von den Abschnitten 6.2 und 6.4 im Buch (C++-Compiler benötigt). (Herman Haverkort)

* Fréchet View, ein Tool mit dem man Fréchet-Abstände und Free-Space-Diagramme interaktiv erkunden kann. Für die Eingabe der Kurven kann man z.B. Ipe benutzen (siehe oben). In Fréchet View kann man u.A. auf einzelne Strecken eines zulässigen Pfades im Free-Space-Diagramm zeigen; der Viewer zeigt dann die dazugehörigen Strecken der Kurven—und umgekehrt. (Peter Schäfer)

* Streaming Delaunay Triangulation: Dieses Video zeigt, wie man die Struktur der Eingabedaten in der Praxis benutzen kann, um große Punktmengen schnell mittels inkrementeller Konstruktion zu triangulieren. Publikation mit weiterführenden Informationen: PDF (Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink).

* Folding Free-Space Diagrams: Dieses Video zeigt, wie sich das Free-Space-Diagramm für den Fréchet-Abstand zwischen eindimensionalen Kurven mit zwei Schnitten in einem geschickt gefaltetem Blatt Papier erstellen lässt (und wie man das algorithmisch ausnutzen kann). Probieren Sie es selber! Publikation mit weiterführenden Informationen: PDF (Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada)

* Fold and Cut Theorem (Video: Katie Steckles, Brady Haran): Wie man eine geometrische Figur mit einem Schnitt ausschneiden kann, wenn das Papier gefaltet werden darf. Publikation mit weiterführenden Informationen: PDF (Erik Demaine, Martin Demaine, Anna Lubiw)

* Kakeya Needle Problem (Video: Charles Fefferman, Brady Haran): Was ist die kleinste Fläche, sodass darin eine Nadel der Länge 1 um 360 Grad gedreht werden kann (die Nadel darf innerhalb der Fläche auch verschoben werden)? Eine Übersicht zu weiteren Varianten findet sich hier PDF (Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, Sang Duk Yoon)

* Cat and Mouse Game (Video: Ben Sparks, Brady Haran): Gibt es eine Strategie, mit der die Maus aus dem See entkommen kann, ohne am Ufer von der Katze gefangen zu werden? Eine Übersicht zu weiteren Varianten und algorithmischen Problemen zu dem Thema: PDF (Zachary Abel, Hugo Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jason S. Ku, Jayson Lynch)

* Ham-Sandwich Theorem (Video: Hannah Fry, Brady Haran): Kann jedes belegte Brot mit einem geraden Schnitt so in zwei Teile geschnitten werden, dass jeweils alle Teile (Brot und Belag) gleich groß sind? Publikation zum Thema: PDF (Chi-Yuan Lo, J. Matousek, W. Steiger)

* Finding Relevant Points for Nearest-Neighbor Classification: Wie man eine Menge von Punkten mit Labels effizient reduzieren kann, ohne die Voronoi-Kanten zwischen Voronoi-Regionen verschiedener Labels zu verändern. Publikation mit weiterführenden Informationen: PDF (David Eppstein)