Algorithmen zur Realisierung von Polytopen in 3D

点击翻译按钮获取中文摘要

Konvexe Polytope (im Folgenden beziehen sich alle Aussagen über Polytope auf konvexe Polytope) sind elementare geometrische Objekte. Sie definieren grundlegende Konzepte auf dem Gebiet der Kombinatorischen und Linearen Optimierung (als Schnitt von Halbräumen) oder der Konvexen Geometrie (als konvexe Hüllen endlicher Punktmengen). Aus diesem Grunde ist es wichtig, die kombinatorische Struktur von Polytopen (die Beziehung ihrer Knoten, Kanten, und Facetten zueinander) zu verstehen. Für Polytope in drei Dimensionen können alle kombinatorischen Beschreibungen, die geometrisch als 3D Polytop realisierbar sind, nach dem Satz von Steinitz durch ein einfaches Kriterium charakterisiert werden. Daraus entwickelte sich die Frage, wie man diese Realisierungen algorithmisch erzeugen kann, so dass die Realisierung nicht nur effizient zu berechnen ist, sondern auch kompakt darstellbar. Hierbei ist vor allen Dingen interessant, ob es ausreicht, logarithmisch viele Bits pro Knoten (in Abhängigkeit zur Knotenanzahl) zu verwenden. Im Projekt soll untersucht werden, für welche Klasse von 3D Polytopen dies garantiert werden kann. Neben der Größe der Koordinatendarstellung sind auch andere Vorgaben bei der Realisierung von Interesse. So kann für jedes 3D Polytop die Geometrie einer Fläche frei gewählt werden (Satz von Barnette und Grünbaum) oder jede Symmetrie der kombinatorischen Beschreibung durch die geometrische Einbettung realisiert werden (Satz von Mani). Zu beiden Aussagen sollen innerhalb des Projektes Algorithmen entwickelt werden. Anhand dieser Algorithmen kann man gegebenenfalls neue Eigenschaften charakterisieren, die durch die Realisierung zusätzlich garantiert werden können. Polytope in 4D, haben viele unerwünschte Eigenschaften. So ist es sehr unwahrscheinlich, dass für das Entscheidungsproblem, ob eine kombinatorische Beschreibung als 4D Polytop realisierbar ist, ein effizienter Algorithmus existiert. Zur Generalisierung der Ergebnisse für 3D Polytope soll deshalb die Verallgemeinerung ihrer kombinatorischen Struktur gesucht werden. In vielerlei Hinsicht bilden die schleifenfrei einbettbaren Graphen eine solche natürliche Erweiterung. Zur schleifenfreien Realisierung dieser Graphen sind bislang sehr wenige Ergebnisse bekannt. Innerhalb des Projektes sollen deshalb neue Algorithmen zur Realisierung dieser Graphen in 3D untersucht werden.