Realisierungsprobleme für Punktkonfigurationen und Polyedrische Flächen

Realization problems are a recurrent theme in Discrete Geometry. The generic realization problem can be phrased as follows: „Is there an object living in Euclidean space Rd that satisfies some given conditions?“ The most straightforward way to give a solution of such a problem is the construction of an object with the desired properties. For non-realizability the straightforward approach is complete enumeration of all possible objects and showing for each one of them that it doesn't meet the conditions given. In theory this often is possible because the discrete setting reduces to a finite number of combinatorial possibilities. However, the number of possibilities typically grows exponentially with the size of the object and thus makes this approach intractable very quickly. Therefore indirect methods and conceptual arguments are pursued. One method is to expose an „obstruction“ to realizability, i.e. a property all realizable instances have and that contradicts the given conditions. In Chapter 1 we takle a problem for point configurations in the Euclidean plane. Starting from ideas of Ungar and of Pach, Pinchasi and Sharir we present two algorithms that find in a given point configuration sets of segments which are non-parallel and primitive or non- avoiding respectively. Then we turn our attention to the Jamison-Hill catalogue of slope-critical examples which have the minimal possible number of non-parallel segments. Among these we find three examples where the two conditions listed above cannot be met simultaneously. In the other examples of the catalogue we give complete systems of non-avoiding primitive segments. In Chapter 2 we construct a family of special deformed d-cubes. To this end we streamline an approach of Ziegler and Rörig. For every dimension d >= 4 we get a cube Cd that has an increasing Hamiltonian path with respect to the last coordinate xd. At the same time Cd contains the quadrilateral surface Fd on 2d vertices constructed by McMullen, Schulz and Wills (1985) in its 2-skeleton in such a way that Fd survives the projection to the last three coordinates. The starting point for Chapter 3 is Stratified Morse Theory (SMT) as developed by Goresky and MacPherson. For polyhedral complexes in Rd and especially for polyhedral surfaces in R3 the Morse data can be obtained in a purely combinatorial way once a vertex ordering is fixed. Afterwards we go beyond pure SMT for surfaces and do a more detailed analysis of possible forms of critical points. In Chapter 4 we follow the approach of Novik that exploits the classical obstruction theory for piecewise linear embeddability to find „obstruction systems“ for geometric realizability. We associate with any simplicial complex K and any integer m a system of linear equations and inequalities. If K has a simplicial embedding in Rm then the system has an integer solution. This extends the work of Novik by using not only intersection but also linking numbers.Realisierungsprobleme treten in der diskreten Geometrie an den veschiedensten Stellen auf. Die allgemeine Fragestellung ist dabei, ob es ein Objekt im Anschauungsraum gibt, dass vorgegebene kombinatorische Bedingungen erfüllt. Der direkte Weg, diese Frage zu beantworten, ist, ein Objekt mit den geforderten Eigenschaften zu konstruieren. Für Nicht-Realisierbarkeit ist der direkte Weg eine vollständige Aufzählung aller möglichen Objekte und der Nachweis, dass keines davon die kombinatorischen Bedingungen erfüllt. Theoretisch ist das oft möglich, da die diskrete Fragestellung nur endlich viele kombinatorische Möglichkeiten zulässt. In der Praxis scheitert dieser Ansatz an der exponentiell mit der Größe des Objekts wachsenden Anzahl an Möglichkeiten. Daher braucht man alternative Methoden, um Nicht- Realisierbarkeit nachzuweisen. In Kapitel 1 befassen wir uns mit einer Fragestellung über Punktkonfigurationen in der Ebene. Aus Ideen von Ungar einerseits und Pach, Pinchasi und Sharir andererseits entwickeln wir zwei Algorithmen, die für eine gegebene Punktkonfiguration Teilmengen der Verbindungsstrecken finden, die nicht parallel und zusätzlich primitiv oder nicht-vermeidend sind. Danach untersuchen wir den Katalog von Jamison und Hill, der alle bekannten Punktkonfigurationen enthält, die die minimale Anzahl verschiedener Steigungen definieren. Unter diesen finden wir drei Beispiele, in denen es keine Teilmenge von Verbindungsstrecken gibt, die gleichzeitig alle Richtungen repräsentieren, nicht-vermeidend und primitiv sind. In Kapitel 2 konstruieren wir eine Familie deformierter d-dimensionaler Würfel. Für jede Dimension d >= 4 erhalten wir einen Würfel Cd, der einen aufsteigenden Hamiltonpfad bezüglich der letzten Koordinate xd hat. Gleichzeitig enthält Cd die Flächen Fd auf 2d Ecken von McMullen, Schulz und Wills im 2-Skelett derart, dass Fd die Projektion auf die letzten drei Koordinaten übersteht. Dazu benutzen wir Ansätze von Ziegler und Rörig. Der Ausgangspunkt für Kapitel 3 ist die von Goresky und MacPherson entwickelte Stratifizierte Morse Theorie (SMT). Für polyedrische Komplexe in Rd zeigen wir, dass die Morsedaten nur aus der Eckenreihenfolge und den kombinatorischen Daten gewonnen werden können. Anschließend gehen wir für polyedrische Flächen im R3 über die reine SMT hinaus und untersuchen genauer, wie kritische Punkte aussehen können und welche Effekte sie haben. In Kapitel 4 folgen wir einem Ansatz von Novik, der die klassische Hindernistheorie für stückweise lineare Einbettbarkeit nutzt, um „Hindernissysteme'“ für geometrische Realisierbarkeit anzugeben. Wir konstruieren zu einem gegebenen Simplizialkomplex K und ganzzahliges m ein System linearer Gleichungen und Ungleichungen. Wenn K eine simpliziale Einbettung in Rm hat, dann hat das System eine ganzzahlige Lösung. Die Bedingungen bei Novik rühren von Schnittzahlen her. In dieser Arbeit beschreiben wir, wie wir zusätzliche Bedingungen aus Verschlingungszahlen erhalten