Kombinatorische Probleme auf geometrischen Graphen

Rechnerische Geometrie ist ein relativ junges und sehr aktives Wissenschaftsgebiet im Schnittpunkt zwischen Mathematik und Theoretischer Informatik. Das Studium von Algorithmen und Datenstrukturen war von jeher eine Hauptaufgabe dieser wachsenden Forschungsdisziplin. Obwohl geometrische Graphen, wie der Name schon impliziert, durch geometrische Eigenschaften, wie zum Beispiel x- und y-Koordinaten, definiert sind, sind sie doch auch zu einem wesentlichen Teil von diskreter Natur. Durch diskrete, endliche Punktmengen aufgespannte Geraden(stücke) erlauben einfache, speichereffiziente Datenstrukturen. Zusätzlich zu geometrischen Informationen beinhalten geometrische Graphen auch viele wichtige kombinatorische Zusammenhänge, wie zum Beispiel Nachbarschaftsinformationen. Diese rein kombinatorischen Informationen sind für viele Anwendungen ausreichend und erlauben sehr effiziente und vor allem stabile Algorithmen. Darüberhinaus ist für die Lösung vieler Probleme die geometrische Information redundant. In diesen Fällen können Punktmengen, im Prinzip von geometrischer Struktur, alleine mit rein kombinatorischen Eigenschaften gespeichert werden. Ein einfaches Beispiel dafür ist die Berechnung der konvexen Hülle einer Punktmenge, ein zentrales Teilproblem in unzähligen Algorithmen. Dafür ist es ausreichend, für jedes Tripel a,b,c von Punkten zu wissen, ob Punkt c links oder rechts der von a nach b aufgespannten Geraden liegt. Der sogenannte "Order Type" ist eine solche Datenstruktur. Von geometrischen Eigenschaften befreit zu sein, bringt einen enormen Vorteil bei der Entwicklung sehr einfacher, exakter und somit stabiler Algorithmen mit sich. Daher ist das Gebiet der rechnerischen Geometrie zunehmend mit den Gebieten der diskreten und kombinatorischen Geometrie verknüpft. Im beantragten Projekt planen wir eine Gruppe von hochgradig zusammenhängenden Fragen aus diesem Bereich zu untersuchen, die alle auf rein kombinatorische Probleme reduziert werden können. Obwohl die Problemstellung des Blockierens von Delaunay-triangulierungen auf zweifärbigen Punktmengen nicht von rein kombinatorischer Natur ist - und daher eine Ausnahme darstellt - ist dieses Teilproblem mit den anderen, in diesem Antrag vorgestellten Problemstellungen eng verwandt. Allgemeine Methoden auf zweigefärbten Punktmengen können auch auf die Probleme auf kompatiblen oder isomorphen geometrischen Graphen, auf Fragestellungen zum Thema k-Konvexität und natürlich auch für die Klasse der Erdös-Szekeres Probleme auf zweigefärbten Punktmengen angewandt werden. Darüberhinaus ziehen neue Erkenntnisse und Resultate aus den einzelnen, erwähnten Problemen, direkt vertiefende Einsichten für andere im Projekt behandelte Fragestellungen sowie weitere Fragen aus dem Bereich der diskreten und kombinatorischen Geometrie nach sich.

Das Forschungsfeld der Rechnerischen Geometrie ist ein relativ junges und sehr aktives Wissenschaftsgebiet, angesiedelt zwischen Mathematik und Theoretischer Informatik. Eine Hauptaufgabe dieser wachsenden Forschungsdisziplin ist das Studium von Algorithmen und Datenstrukturen, aber auch die Betrachtung kombinatorischer Fragestellungen. Obwohl geometrische Graphen sehr stark durch geometrische Eigenschaften, wie zum Beispiel x-, y-Koordinaten, beschrieben werden, sind sie doch auch zu einem wesentlichen Teil von diskreter Struktur. So beinhalten geometrische Graphen, die aus durch diskrete, endliche Punktmengen (Knoten des Graphen) aufgespannte Geradenstücke (Kanten des Graphen) bestehen, nicht nur die geometrische Information, sondern auch viele wichtige kombinatorische Zusammenhänge, wie zum Beispiel Nachbarschaftsbeziehungen oder die Anzahl bestimmter aufgespannter Strukturen (zum Beispiel punktleere Dreiecke). Diese rein kombinatorischen Informationen sind für viele Anwendungen ausreichend und erlauben einfache, speichereffiziente Datenstrukturen und sehr laufzeit- performante und vor allem stabile Algorithmen. Daher ist das Gebiet der Rechnerischen Geometrie zunehmend mit den Gebieten der diskreten und kombinatorischen Geometrie verknüpft.Das abgeschlossene Projekt befasste sich daher mit einer Gruppe von hochgradig zusammenhängenden Problemstellungen aus diesem Bereich, die auf rein kombinatorische Fragen reduziert werden können. Ein Beispiel ist die Frage nach der Anzahl benötigter Transformationen, um eine zweigefärbte Paarung (Matching) in eine andere überzuführen. Dabei ist eine zweigefärbte Paarung ein geometrischer Graph auf einer zweigefärbte Punktmenge, wobei jeder Punkt nur genau an eine Kante verbunden ist, jede Kante ein Paar Punkte gleicher Farbe verbindet, und Kanten sich nicht schneiden dürfen. Eine Transformation führt eine Paarung in eine andere über, wobei es nach Einfügen aller Kanten beider Paarungen in die zugrunde liegende Punktmenge, ebenfalls keine Kantenschnitte geben darf, ausgenommen komplett identische Kanten. Im Zuge des Projektes konnten wir die bekannte exponentielle Schranke für die Anzahl notwendiger Transformationen auf eine lineare Anzahl reduzieren und damit diese Frage abschließend beantworten. Zusätzlich konnten wir einen effizienten Algorithmus zum Finden einer optimalen Serie von Transformationen angeben.Ein gewaltiger Schritt konnte im Zuge dieses Projektes in der Klasse der sogenannten Erdös- Szekeres Probleme gemacht werden, eine spezielle Untergruppe von Fragestellungen in der sogenannten Ramseytheorie. Es wurden die bekannten Schranken für die Anzahl von in Punktmengen enthaltenen, leeren konvexen Drei-, Vier- und Fünfecken verbessert. Weiters gab es Verbesserungen oder überhaupt erste Betrachtungen der Fälle, in denen die genannten Polygone nicht notwendigerweise leer und/oder nicht notwendigerweise konvex sein müssen. Zusätzlich wurde eine grundlegende Arbeit über die Anzahl leerer Simplizia (Dreiecke in 2D, Tetraeder in 3D, usw.) in mehrfachgefärbten, hochdimensionalen Punktmengen veröffentlicht, und die Frage nach der Anzahl leerer Dreiecke auch auf allgemeinen Graphen (deren Kanten keine Geradenstücke sein müssen) erfolgreich betrachtet.Die in diesem Projekt geleistete Arbeit hatte Auswirkungen in vielen Themenbereichen, auch außerhalb des in der Antragsphase definierten Aufgabenbereichs. Zusammenfassend resultierte dieses Projekt in der Veröffentlichung von bisher 36 Arbeiten in Fachzeitschriften und referierten Konferenzen. Und viele gestartete Forschungen sind immer noch im Gange.