Ordnungstypen und extremale kombinatorische Geometrie

Unser Projekt liegt im Bereich der algorithmischen Geometrie, welcher zur Mathematik und Theoretischen Informatik gehört, und in dem man sich mit den theoretischen Hintergründen zur Verarbeitung geometrischer Strukturen in Computerprogrammen beschäftigt. Unsere Forschung hat Anwendungen in der extremalen kombinatorischen Geometrie, in der man sich mit Abschätzungen der Anzahl von unterschiedlichen Netzwerken beschäftigt, die durch gerade Verbindungen zwischen Punkten auf einer ebenen Fläche definiert sind, ähnlich wie bei Landkarten, auf denen Städte durch gerade Routen verbunden sind. Solche Zeichnungen nennt man geometrische Graphen. Geometrische Graphen lassen sich auf viele Arten klassifizieren, z.B. dadurch, ob sie Kreuzungen oder Zyklen enthalten. Für viele Klassen ohne Kreuzungen weiß man, dass die Anzahl der verschiedenen geometrischen Graphen, welche man durch das Verbinden gegebener Punkte erhält, minimiert wird, wenn die Punkte auf einem Kreis angeordnet sind. Gleichzeitig wird bei dieser Anordnung, für viele Klassen von geometrischen Graphen mit Kreuzungen die Anzahl solcher Graphen maximiert. Die Charakterisierung dieser maximierenden und minimierenden Punktmengen je Graphklasse ist ein Ziel unserer Arbeit. Für solche Probleme ist man üblicherweise nicht an der exakten Lage der Punkte interessiert, sondern wie sie relativ zueinander liegen, da es im Allgemeinen keinen Unterschied macht, wenn wir einige Punkte leicht bewegen. Der Ordnungstyp (engl. order type) einer Menge von Punkten wird festgelegt durch die Reihenfolge, in der wir drei Punkte passieren, wenn wir entgegen dem Uhrzeigersinn entlang des von diesen Punkten definierten Dreiecks gehen. Das heißt, wir klassifizieren Punktmengen anhand der Orientierung ihrer Punktetripel. In vorangehender Arbeit haben wir eine Relation zwischen Ordnungstypen über die Menge der möglichen kreuzungsfreien geometrischen Graphen darauf definiert. Dadurch konnten wir Ordnungstypen charakterisieren, welche Punktmengen enthalten, die die Anzahl der geometrischen Graphen für gewisse Klassen maximieren bzw. minimieren. Allerdings ist diese Charakterisierung ziemlich allgemein, weshalb wir planen, weitere Relationen zwischen Ordnungstypen zu finden, die uns Einsicht in die Struktur der maximierenden und minimierenden Punktmengen geben. Speziell wollen wir die Anzahl von Triangulierungen (das sind geometrische Graphen, in denen jeder geschlossene Bereich ein Dreieck bildet) abschätzen. Wir werden versuchen, eine Vermutung über die Struktur der Punktmenge, welche die wenigsten Triangulierungen hat, zu beweisen. Dazu wollen wir Einsichten über Relationen und lokalen Transformationen (wie das Ändern der Orientierung von drei Punkten) auf Ordnungstypen nutzen, welche auch allgemein von Interesse sind. Wir werden unterschiedliche Arten solcher Transformationen untersuchen.

Das Projekt kann dem Forschungsfeld der algorithmischen und kombinatorischen Geometrie zugeordnet werden, ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Algorithmische Geometrie kommt z.B. in der Computergrafik und in Geoinformationssystemen zur Anwendung. Von dort kennt man Dreiecksnetze (Triangulierungen). Solche Unterteilungen einer Fläche in Dreiecke sind Beispiele für kreuzungsfreie geometrische Graphen, in denen Punkte durch nicht kreuzende Linien verbunden werden. Sogar auf ebenen Flächen stellen uns solche Graphen vor Fragen in der Grundlagenforschung. Für eine Menge von Punkten gibt es üblicherweise eine große Anzahl an unterschiedlichen kreuzungsfreien geometrischen Graphen, die auf den Punkten gezeichnet werden kann. Die Frage nach der minimalen und maximalen Anzahl solcher Graphen (z.B. Triangulierungen) auf entsprechend platzierten Punkten drängt sich auf. Obwohl eine feste Anzahl an Punkten auf unendlich viele Arten platziert werden kann, sieht man, dass im Allgemeinen eine kleine Verschiebung eines Punktes die Anzahl der Triangulierungen auf der Menge nicht ändert. Wegen dieser Beobachtung wurden diverse Arten der Klassifizierung von Punktmengen in eine endliche Anzahl von sich gleich verhaltenden Gruppen beschrieben. Eine solche Gruppierung ist die der order types, welche im Prinzip die Orientierung aller Dreiergruppen von Punkten festlegt. Ergebnisse über order types stehen daher in Verbindung mit der grundlegenden Frage nach der Anzahl von geometrischen Graphen. Im Projekt wurden Probleme über order types und die Anzahl geometrischer Graphen untersucht. Eine Hauptfrage war die nach der Verwandtschaft einzelner order types. Z.B. gibt es Paare von order types sodass wir alle geometrischen Graphen von einem order type auch auf dem anderen zeichnen können. Wir untersuchten wie lokale Veränderungen am order type (z.B. durch Bewegen eines einzelnen Punktes) die Anzahl der kreuzungsfreien geometrischen Graphen auf der Punktmenge beeinflusst. Dafür betrachteten wir den einfachen Fall in dem ein Punkt sich in einem Kreis bewegt, auf dem die anderen Punkte angeordnet sind. Sogar dieser einfache Fall wies eine interessante Struktur auf, deren Eigenschaften wir untersucht haben. Unsere Methoden gaben uns auch Einblick in ein hochdimensionales Problem, was zur Entwicklung eines schnelleren Algorithmus' zur Berechnung der sog. simplicial depth (ein Maß dafür, wie zentral ein Datenpunkt ist) führte. Ein weiteres Resultat in der Forschungsrichtung ist die Verbesserung der unteren Schranke für die maximale Anzahl von kreuzungsfreien geometrischen Graphen. Es wurde eine Familie von Punktkonfigurationen beschrieben, auf der man mehr solche Graphen zeichnen kann als auf bisher bekannten Konfigurationen. Es wurden auch Resultate in spezielleren Forschungsrichtungen erzielt. Alle unsere Themen können der Grundlagenforschung zugeordnet werden. Daher lassen sich keine direkten praktischen Anwendungsfälle darlegen. Dennoch tragen die erhaltenen Resultate zum besseren Verständnis solcher grundlegenden mathematischen Strukturen bei. Das wird auch dadurch bestätigt, dass etliche Resultate aus dem Projekt in anerkannten Journalen veröffentlicht wurden.