Optimization Methods in Discrete Geometry

Abstract

In this thesis we study some problems from discrete geometry and develop new methods for solving them. Many such problems can be formulated as optimization problems over spaces defined by systems of polynomial inequalities. Our method consists of two steps, which can be summarized as follows: Model a problem from discrete geometry as a system of polynomial inequalities and solve it numerically. From the numerical solution, derive an exact solution, which may provide additional structural information. For any specific problem, each of these two steps needs to be adapted. We illustrate this approach in different applications ranging from the classification of polytopes to packing problems.

In der vorliegenden Arbeit werden verschiedene Probleme der diskreten Geometrie untersucht und Methoden entwickelt um diese zu lösen. Die Methoden machen sich nutze, dass sich viele Probleme der diskreten Geometrie als Optimierungsproblem über einem polynomiellen Ungleichungssystem darstellen lassen. In einigen Fällen gelingt es, eine numerische Lösung eines solchen Systems zu bestimmen und dann in eine exakte Lösung zu überführen, die wiederum etwas über das betrachtete Problem aussagt. Wir geben einige Beispiele von solchen Anwendungen. Die Frage welche simplizialen Sphären als Polytop realisiert werden können wird im ersten Kapitel behandelt. Hierbei entwickeln wir eine Möglichkeit für eine gegebene simpliziale Sphäre eine Realisierung zu finden, falls diese existiert. Außerdem werden die bekannten Beweismethoden für die Nichtrealisierbarkeit derartig verbessert, dass sie effizient auf große Familien von simplizialen Sphären und uniformen orientierten Matroiden angewandt werden können. Die Realisierungsmethode besteht darin, ein nicht-lineares Gleichungssystem, welches die Realisierbarkeit der simplizialen Sphäre beschreibt, in einem ersten Schritt numerisch zu lösen und diese numerische Lösung in einem zweiten Schritt in rationale Koordinaten umzuwandeln, für die man dann beweisen kann, dass es sich tatsächlich um eine Realisierung der simplizialen Sphäre handelt. Mit diesen Methoden gelingt die vollständige Klassifizierung der kombinatorischen Typen von simplizialen 4-Polytopen mit 10 Ecken: es gibt genau 162004. Für simpliziale 4-Polytope mit 9 Ecken wurde deren Anzahl, nämlich 1142, von Altshuler, Bokowski und Steinberg bereits 1980 bestimmt. Außerdem erhalten wir die vollständige Klassifizierung von simplizialen nachbarschaftlichen Polytope mit 10 Ecken in Dimension 5 und mit 11 Ecken in den Dimensionen 4, 6 und 7. Wir behandeln in diesem Kapitel nicht nur die Polytopalität von simplizialen Sphären, sondern beschäftigen uns auch mit der Einschreibbarkeit derselben, das heißt wir suchen Realisierungen, so dass alle Koordinaten auf der Einheitssphäre liegen. Hierzu wird zu unserer Überraschung festgestellt, dass alle untersuchten 2-nachbarschaftlichen simplizialen Polytope einschreibbar sind. Das zweite Kapitel behandelt eine Fragestellung aus dem Gebiet der Packungen. Seien zwei Polytope P und Q gegeben. Wir suchen ein Polytop P' von maximalem Volumen, so dass P' ähnlich zu P ist und außerdem P' in Q enthalten ist. Diese Frage wurde bereits verschiedentlich untersucht, insbesondere in der Dimension 2, wo P und Q also Polygone sind. In Dimension 3 hat Croft 1980 alle 20 Paare von 5 platonischen Körpern untersucht und konnte für 14 die optimalen Inklusionen ermitteln. Wir beschäftigen uns mit den verbleibenden 6 Fällen und wenden unsere Methoden darauf an. Zwar erhalten wir hier zunächst nur numerische Ergebnisse, können daraus jedoch Inklusionen bestimmen, deren Koordinaten algebraische Zahlen sind. Im dritten Kapitel werden zwei weitere Probleme untersucht: Zylinderpackungen an der Sphäre und das Zeichnen von planaren Graphen mit vorgeschriebenen Flächeninhalten.