Algorithmen zur Realisierung von Polytopen in 3D

• Applicant: Professor Dr. André Schulz
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2012 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 219074381

• Final Report Year: 2015

Final Report Abstract

Polyeder sind konvexe geometrische Objekte, welche aus Knoten, Kanten und Flächen bestehen. Der kombinatorische Typ eines Polyeders wird durch seinen Graphen bestimmt. In diesem Projekt wurde nach Algorithmen gesucht, welche ein Polyeder (gegeben als Graph) geometrisch realisieren. Die berechnete geometrische Einbettung sollte auf einem kleinem Gitter konstruiert werden. Das heißt, möglichst kleine ganzzahlige Koordinaten sollten für die Ecken des Polyeders benutzt werden. Im abgelaufenen Projekt konnten wir neue Algorithmen zur Realisierung von Polytopen ermitteln. Als Hauptresultat wurde eine neue Technik entwickelt, die es ermöglicht eine Polaritätstransformation durchzuführen, sodass nach einer geeigneten Störung der Einbettung die Gitterausdehnung kontrollierbar bleibt. Diese Technik lässt sich sowohl für 3D Stapelpolytope als auch für Polyeder mit beschränktem Knotengrad anwenden. Zukünftige Einbettungsalgorithmen für simplizale Polyeder (jede Fläche ist eine Dreieck) können somit für einfache Polyeder (genau 3 Flächen schneiden sich ein einem Knoten) verwendet werden. Dies ist in sofern überraschend, da das Realisierungsproblem für die einfachen Polyeder schwerer erscheint. Des Weiteren wurden Algorithmen für Spezialfälle wie kleine Polyeder und Prismatoide entwickelt. Innerhalb des Projektes konnte auch das bereits bekannte Resultat für die Stapelpolytope verbessert werden. Zum einen wurde dank einer modifizierten Technik zur Bestimmung der z-Koordinaten die Größe des Gitters verbessert. Zum anderen wurde das Ergebnis für höhere Dimensionen verallgemeinert. Dies zeigt, dass sich Stapelpolytope sehr kontrolliert einbetten lassen, denn bereits in 4D gibt es Polytope, die nicht auf dem Gitter realisiert werden können.

Publications

• A Duality Transform for Constructing Small Grid Embeddings of 3d Polytopes Graph Drawing - 21th International Symposium (GD), LNCS 8242, Seiten 173-184, Bordeaux, 2013
  A. Igamberdiev und A. Schulz
  
• Small Grid Embeddings of Prismatoids and the Platonic Solids (Poster abstract), Graph Drawing - 21th International Symposium (GD), LNCS 8242, Bordeaux, 2013
  A. Igamberdiev, F. Nielsen und A. Schulz
  
• Embedding Stacked Polytopes on a Polynomial-Size Grid
  E. D. Demaine und A. Schulz