Erweiterte Suche

A duality transform for realizing convex polytopes with small integer coordinates

Wir entwickeln eine Dualitätstransformation für Polyeder, die eine Einbettung auf dem polynomiellen Gitter berechnet, wenn das ursprüngliche Polyeder auf einem polynomiellen Gitter gegeben ist. Die Konstruktion erfordert einen beschränkten Knotengrad des Polytop-Graphen, funktioniert aber im allgemeinen Fall für die Klasse der Stapelpolytope. Als Konsequenz können wir zeigen, dass sich die "Truncated Polytopes" auf einem polynomiellen Gitter realisieren lassen. Dieses Ergebnis gilt für jede (feste) Dimension.

We study realizations of convex polytopes with small integer coordinates. We develop an efficient duality transform, that allows us to go from an efficient realization of a convex polytope to an efficient realization of its dual.Our methods prove to be especially efficient for realizing the class of polytopes dual to stacked polytopes, known as truncated polytopes. We show that every 3d truncated polytope with n vertices can be realized on an integer grid of size O(n^(9lg(6)+1)), and in R^d the required grid size is n^(O(d^2*lg(d))). The class of truncated polytopes is only the second nontrivial class of polytopes, the first being the class of stacked polytopes, for which realizations on a polynomial size integer grid are known to exists.

Titel: A duality transform for realizing convex polytopes with small integer coordinates
Verfasser: Igamberdiev, Alexander GND
Gutachter: Schulz, André GND
Organisation: FB 10: Mathematik und Informatik
Dokumenttyp: Dissertation/Habilitation
Medientyp: Text
Erscheinungsdatum: 2016
Publikation in MIAMI: 01.03.2016
Datum der letzten Änderung: 01.03.2016
Schlagwörter: Diskrete Geometrie; Polytope; Gitter-Einbettungen; Dualität; Gleichgewichts-Stresse
Discrete Geometry; Polytopes; Grid Embeddings; Duality; Equilibrium Stresses; Quantitative Steinitz Theorem
Fachgebiete: Informatik, Wissen, Systeme
Sprache: Englisch
Format: PDF-Dokument
URN: urn:nbn:de:hbz:6-16279528400
Permalink: https://nbn-resolving.org/urn:nbn:de:hbz:6-16279528400
Onlinezugriff:
Inhalt:
Introduction 1
Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Main tool and further results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1 Methods for realizing planar graphs: overview 11
2 Efficient duality transforms in R3 17
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2 Convex polytopes and polytopal surfaces . . . . . . . . . . . . . . . . . 18
2.2 Equilibrium stresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Maxwell–Cremona lifting and the canonical equilibrium stress . . . . . . 21
2.2.2 Wheel-decomposition for equilibrium stresses . . . . . . . . . . . . . . . 23
2.2.3 An efficient reverse of the Maxwell–Cremona lifting . . . . . . . . . . . . 25
2.3 Braced stresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Canonical braced stresses . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.3 Braced stresses and equilibrium stresses: flat embeddings . . . . . . . . 28
2.3.4 Braced stresses and stresses of braced graphs . . . . . . . . . . . . . . . 29
2.3.5 Scalability of braced stresses . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.6 Projective equivalence with equilibrium stresses . . . . . . . . . . . . . . 31
2.3.7 Free lunch: wheel-decomposition for braced stresses . . . . . . . . . . . 32
2.3.8 Free lunch: projective properties of equilibrium stresses . . . . . . . . . 34
2.3.9 Canonical braced stresses as Hessians of volume . . . . . . . . . . . . . . 36
2.3.10 Orthogonal projection of the canonical braced stresses . . . . . . . . . . 37
2.4 Lov´asz lifting procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1 Lov´asz dual transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.2 Lov´asz lifting procedure: convex case . . . . . . . . . . . . . . . . . . . . 44
2.4.3 Lov´asz lifting procedure: general case . . . . . . . . . . . . . . . . . . . 45
2.4.4 Geometry of the wheel-decomposition . . . . . . . . . . . . . . . . . . . 46
2.4.5 Geometry of the wheel-decomposition: equilibrium stresses . . . . . . . 49
2.5 Duality transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5.1 High level description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5.2 The stacking approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5.3 A duality transform for general simplicial polytopes . . . . . . . . . . . 59
3 Prismatoid 63
3.0.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.0.2 Realization of the (k,m)-prismatoid . . . . . . . . . . . . . . . . . . . . 64
4 Efficient duality transforms in Rd 73
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.1 Combinatorics and notation of d-polytopes: overview . . . . . . . . . . . 73
4.1.2 Conventions on orientations . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.1.3 Orientation on faces of a polytope . . . . . . . . . . . . . . . . . . . . . 78
4.1.4 Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.5 Realizations of polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Approaches to stresses in higher dimensions . . . . . . . . . . . . . . . . . . . . 82
4.2.1 Equilibrium stress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.2 Braced stress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2.3 From equilibrium stresses to braced stresses and back . . . . . . . . . . 88
4.2.4 Scalability of braced stresses . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2.5 Canonical braced stress . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3 Maxwell–Cremona lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3.1 Maxwell–Cremona lifting . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.2 Canonical equilibrium stress . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.3 Full version of Maxwell–Cremona lifting theorem . . . . . . . . . . . . . 96
4.3.4 Creasing formula for canonical equilibrium stress . . . . . . . . . . . . . 97
4.4 Lov´asz construction in Rd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5 Realizations of truncated polytopes . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.5.1 Truncated and stacked polytopes . . . . . . . . . . . . . . . . . . . . . . 102
4.5.2 High level description of the algorithm . . . . . . . . . . . . . . . . . . . 103
4.5.3 Step 1: Realizations of stacked polytopes . . . . . . . . . . . . . . . . . 103
4.5.4 Step 2: Stacking of the missing vertex . . . . . . . . . . . . . . . . . . . 108
4.5.5 Step 3: Realizing truncated polytopes . . . . . . . . . . . . . . . . . . . 109
4.6 Duality transform for general simplicial polytopes . . . . . . . . . . . . . . . . . 111
4.6.1 Wheel-decomposition theorem . . . . . . . . . . . . . . . . . . . . . . . 111
4.6.2 Duality transform for general simplicial polytopes . . . . . . . . . . . . 116
Conclusion 119