Konstruktionen für kubische Polytope

Polytope (konvexe, beschränkte Polyeder beliebiger Dimension) sind klassische Objekte der Kombinatorischen Geometrie. Eine der bekanntesten --- und auch gut verstandenen --- Klassen von Polytopen bilden die simplizialen Polytope, dies sind Polytope deren Seiten alle Simplices der entsprechenden Dimension sind. Anlog werden kubische Polytope definiert als Polytope deren Seiten alle die kombinatorische Struktur von Würfeln der entsprechenden Dimension besitzen. Es ist bekannt, dass jedes kubische d-dimensionale Polytop eine Immersion einer abstrakten geschlossenen (d-1)-dimensionalen Mannigfaltigkeit in den Rand des Polytopes bestimmt. In dem Falle von kubischen 4-Polytopen sind die Zusammenhangskomponenten der dualen Mannigfaltigkeiten Flächen, geschlossene 2-dimensionale Mannigfaltigkeiten (d.h. kompakt und ohne Rand). Für den allgemeineren Fall von kubischen PL (d-1)-Spähren haben Babson & Chan gezeigt, dass jeder PL-Typ einer normal-schneidenden Immersion einer geschlossenen (d-2)-Mannigfaltigkeit in eine (d-1)-Spähre als eine Komponente der dualen Mannigfaltigkeit einer kubischen PL (d-1)-Spähre auftaucht. Für kubische Polytope war bisher kein analoges Resultat bekannt. Dies geht zurück auf einen Mangel an flexiblen Konstruktionstechniken für kubische Polytope und allgemeiner, für kubische Bälle, wie sie z.B. in der Hexaedernetzgenerierung (CAD) verwendet werden. In dieser Arbeit entwickeln wir neue Konstruktionstechniken für kubische Polytope und kubische Bälle. Eine unserer kompliziertesten Konstruktionen verallgemeinert das ''Hexhoop template'' welches aus der Hexaedernetzgenerierung bekannt ist. Mit den beschriebenen Konstruktionen erzielen wir folgende neue Resultate: Ein relativ elementare Konstruktion liefert ein kleines kubisches 4-Polytop (mit 72 Ecken und 62 Facetten) dessen duale Mannigfaltigkeit eine Kleinsche Flasche als eine Komponente enthält. Dies ist die erste bekannte Instanz eines kubischen 4-Polytops mit einer nicht orientierbaren dualen Mannigfaltigkeit, was die Frage von Hetyei nach der Existenz von nicht ''Kanten-orientierbaren'' kubischen 4-Polytopen beantwortet. Allgemeiner können wir zeigen, dass jeder PL-Typ einer normal-schneidenden Immersion einer Fläche in eine 3-Spähre als eine Komponente der dualen Mannigfaltigkeit eines kubischen 4-Polytops auftaucht. Im Falle einer nicht orientierbaren Fläche ungeraden Geschlechts liefert dies ein kubisches 4-Polytop mit einer ungeraden Anzahl von Facetten. Wir konstruieren explizit eine Instanz eines kubischen 4-Polytops mit 19.520 Ecken und 18.333 Facetten mit einer dualen Boyschen Fläche, einer Immersion der projektiven Ebene mit einem Schnittpunkt vom Grad 3. Mit Hilfe von Schlegeldiagrammen folgt daraus, dass jeder geometrische Typ eines 3-dimensionalen Würfels eine Kubifizierung (d.h. eine Zerlegung in Würfel, ohne Unterteilung des Randes) mit einer geraden Anzahl von Würfeln besitzt. Dies impliziert, dass der kubische Flip-Graph für geometrische Hexaedernetze mindestens 2 Komponenten besitzt, was Fragen von Eppstein und Thurston beantwortet.In this thesis we consider cubical d-polytopes, convex bounded d-dimensional polyhedra all of whose facets are combinatorially isomorphic to the (d-1)-dimensional standard cube. It is known that every cubical d-polytope P determines a PL immersion of an abstract closed cubical (d-2)-manifold into the polytope boundary. The immersed manifold is orientable if and only if the 2-skeleton of the cubical d-polytope (d > 2) is ''edge orientable'' in the sense of Hetyei, who conjectured that there are cubical 4-polytopes that are not edge-orientable. In the more general setting of cubical PL (d-1)-spheres, Babson and Chan have observed that every type of normal crossing PL immersion of a closed PL (d-2)-manifold into an (d-1)-sphere appears among the dual manifolds of some cubical PL (d-1)-sphere. No similar general result was available for cubical polytopes. The reason for this may be blamed to a lack of flexible construction techniques for cubical polytopes, and for more general cubical complexes (such as the ''hexahedral meshes'' that are of great interest in CAD and in Numerical Analysis). In this thesis, we develop a number of new and improved construction techniques for cubical polytopes. We try to demonstrate that it always pays off to carry along convex lifting functions of high symmetry. The most complicated and subtle one of our constructions generalizes the ''Hexhoop template'' which is a well-known technique in the domain of hexahedral meshes. Using the constructions developed here, we achieve the following results: A rather simple construction yields a cubical 4-polytope (with 72 vertices and 62 facets) for which the immersed dual 2-manifold is not orientable: One of its components is a Klein bottle. Apparently this is the first example of a cubical polytope with a non-orientable dual manifold. Its existence confirms the conjecture of Hetyei mentioned above. More generally, all PL-types of normal crossing immersions of closed 2-manifolds appear as dual manifolds in the boundary complexes of cubical 4-polytopes. In the case of non-orientable 2-manifolds of odd genus, this yields cubical 4-polytopes with an odd number of facets. (This result is a polytopal analog to the Babson-Chan construction restricted to 2-manifolds.) In particular, we construct an explicit example with 19520 vertices and 18333 facets of a cubical 4-polytope that has a cubation of Boy's surface (an immersion of the projective plane with exactly one triple point) as a dual manifold immersion. Via Schlegel diagrams, this implies that for every cubification of a 3-dimensional domain there is also a cubification of opposite parity. Thus the flip graph for hexahedral meshes has at least two connected components. This answers questions by Eppstein and Thurston