Pseudotriangulierung und Bewegungen von Gelenkssystemen

Eine Pseudotriangulierung ist eine Zerlegung eines ebenen Bereichs in Polygone mit jeweils genau drei konvexen Ecken und beliebig vielen einspringenden Ecken (Pseudodreiecke). Von besonderer Bedeutung sind die gespitzten Pseudotriangulierungen (pointed pseudotriangulations), wo an jeder Ecke ein Winkel >180° anliegt. Diese haben genau n-2 Pseudodreiecke und 2n-3 Kanten, und dies ist die kleinste mögliche Anzahl für eine Pseudotriangulierung. In jüngster Zeit hat man erkannt, dass Pseudotriangulierungen viele wünschens-werte Eigenschaften haben und auch bei der Untersuchung der Bewegung von Gelenkssystemen, wie sie etwa bei der Bewegungsplanung von Robotern auftreten, eine wesentliche Rolle spielen. Sie werden auch als Datenstrukturen, insbesondere für die Simulation dynamischer Bewegungen, verwendet. Ein Fachwerk (Stabwerk, Gelenkssystem, framework, linkage) besteht aus Stäben fester Länge, die an den Ecken durch bewegliche Gelenke miteinander verbunden sind. Die Untersuchung der Starrheit oder Beweglichkeit solcher Systeme, sowohl in der Ebene als auch im Raum ist ein Grundproblemen der Statik, das in erster Näherung mit Methoden der linearen Algebra lösbar ist. Viele Aussagen über Starrheit lassen sich aber allein auf Grund der kombinatorischen Struktur, das heißt, auf Grund des darunterliegenden Graphen machen. Das Kriterium von Laman~(1971) charakterisiert zum Beispiel minimal starre Graphen in der Ebene folgendermaßen:

Ein Laman-Graph ist ein Graph mit n Knoten und 2n-3 Kanten, wobei jeder Untergraph mit k>= 2 Knoten höchstens 2k-3 Kanten enthält.

Diese Graphen sind genau jene Graphen, die bei jeder Einbettung in genügend "allgemeiner" Lage starr sind, die aber bei Entfernung einer beliebigen Kante beweglich werden. Das sogenannte Zollstockproblem (carpenter's rule problem) fragt nach einer Bewegung, die ein Gelenksystem in Form eines ebenen Streckenzugs ohne Selbstüberschneidungen gerade macht. Derartige Fragestellungen wurden seit einiger Zeit in der algorithmischen Geometrie, aber auch im Hinblick auf Anwendungen in der Knotentheorie, Robotik (Bewegung von Roboterarmen), Fertigungstechnik (Biegen von Drähten oder Rohrleitungen) der Polymerphysik und Biophysik untersucht (Molekülfaltung). Das Zollstockproblem ist dabei sicher nur ein grundlegendes Problem, das keine direkten Anwendungen hat. Es wurde jüngst von Connelly, Demaine, und Rote in der Richtung gelöst, dass es eine solche "öffnende" Bewegung immer gibt. In ähnlicher Weise kann ein geschlossener Streckenzug (ein Polygon) immer konvex gemacht werden. Die Hauptidee beim Beweis dieser Aussage ist, expansive Bewegungen zu betrachten, bei denen die Abstände zwischen je zwei Punkten nicht abnehmen. Man kann von der Anwendung, Polygone zu öffnen, abstrahieren und den durch die Expansionseigenschaft definierten Expansionskegel aller expansiven Bewegungen einer Punktmenge für sich betrachten. Seine extremen Strahlen stehen wieder in enger Beziehung zu den Pseudotriangulierungen.

In diesem Projekt sollen neue Erkenntnisse über Pseudotriangulierungen, Starrheit und Beweglichkeit von Gelenkssystemen (Fachwerken), und Anwendungen von Pseudotriangulierungen als Datenstrukturen gewonnen werden. Ein weiteres Ziel ist es, analoge Strukturen im Raum zu finden. Dies wäre zum Beispiel wichtig als kinetische Datenstruktur für dynamische Bewegungssimulationen. Derzeit gibt es einige einfache Ansätze, aber noch keine zufriedenstellende Definition dafür, was eine höherdimensionale "Pseudotriangulierung" sein könnte.