Quelltext der Seite Kreuzpolytop

[[Datei:Euclid Octahedron 3.svg|miniatur|Ein Oktaeder ist ein dreidimensionales Kreuzpolytop]]

Ein '''Kreuzpolytop''' oder '''Hyperoktaeder''' ist in der [[Geometrie]] ein [[Polytop (Geometrie)|Polytop]], das eine Verallgemeinerung eines [[Oktaeder]]s vom [[Dreidimensionaler Raum|dreidimensionalen Raum]] auf Räume beliebiger [[Dimension (Mathematik)|Dimension]] darstellt. Ein Kreuzpolytop im <math>n</math>-dimensionalen Raum ist die [[konvexe Hülle]] von <math>n</math> [[Strecke (Geometrie)|Strecken]], die sich alle in einem gemeinsamen Kreuzungspunkt schneiden. Bei einem '''regulären Kreuzpolytop''' sind diese Strecken alle gleich lang und schneiden sich jeweils zentral und [[Rechter Winkel|rechtwinklig]]. Die [[Symmetriegruppe]] eines regulären Kreuzpolytops ist die [[Hyperoktaedergruppe]]. Neben [[Hyperwürfel]]n und regulären [[Simplex (Mathematik)|Simplizes]] sind reguläre Kreuzpolytope die einzigen [[Platonischer Körper#Verallgemeinerung|regulären Polytope]], die in beliebigen Dimensionen existieren. Kreuzpolytope finden Anwendung unter anderem in der [[Lineare Optimierung|linearen Optimierung]].

== Einheits-Kreuzpolytop ==
[[Datei:Square diamond (shape).svg|miniatur|Zweidimensionales Einheits-Kreuzpolytop mit Koordinatenachsen]]

=== Definition ===
Das <math>n</math>-dimensionale '''Einheits-Kreuzpolytop''' ist die [[konvexe Hülle]] der <math>2n</math> Ecken <math>\pm e_1, \ldots , \pm e_n</math>:

: <math>P = \operatorname{conv}({e_1, \ldots , e_n, -e_1, \ldots, -e_n}) \subseteq \mathbb{R}^n </math>.

Dabei bezeichnet <math>e_i = (0, 0,\ldots, 1, 0, \dots 0)</math> den <math>i</math>-ten [[Einheitsvektor]] des [[Vektorraum]]s <math>\mathbb{R}^n </math>.

=== Beispiele ===
* Das eindimensionale Einheits-Kreuzpolytop ist das abgeschlossene [[Einheitsintervall]] <math>[-1,1]</math>.
* Das zweidimensionale Einheits-Kreuzpolytop ist ein (auf die Spitze gestelltes) [[Quadrat (Geometrie)|Quadrat]].
* Das dreidimensionale Einheits-Kreuzpolytop ist ein [[Oktaeder]] und damit einer der [[Platonische Körper|platonischen Körper]].

=== Darstellung ===
Das Einheits-Kreuzpolytop lässt sich auch folgendermaßen als Punktmenge im <math>n</math>-dimensionalen Raum darstellen:

:<math>P = \{ (v_1, v_2, \dotsc, v_n) \in \R^n \mid | v_1 | + | v_2 | + \dotsb + | v_n | \le 1 \}</math>.

Das Einheits-Kreuzpolytop ist damit die [[Einheitskugel]] bezüglich der [[Summennorm]] <math>\| \cdot \|_1</math>. Diese Betragsungleichung lässt sich auch als System von <math>2^n</math> linearen Ungleichungen umschreiben. Daher wird das Einheits-Kreuzpolytop durch genau <math>2^n</math> [[Hyperebene]]n begrenzt.

=== Komponenten ===
Das Einheits-Kreuzpolytop ist [[Konvexe Menge|konvex]], [[Abgeschlossene Menge|abgeschlossen]] und [[zusammenhängend]] (bezüglich der [[Euklidischer Abstand|euklidischen Metrik]]). Es besteht aus folgenden Komponenten:

* Es hat <math>2n</math> Ecken, eben die (positiven und negativen) Einheitsvektoren.
* Es hat <math>2 n (n - 1)</math> Kanten, denn jede Ecke <math>e_i</math> ist außer mit der gegenüberliegenden Ecke <math>-e_i</math> mit jeder anderen über eine Kante verbunden.
* Es hat <math>2^n</math> Facetten, die [[Simplex (Mathematik)|Simplizes]] des <math>\mathbb{R}^{n-1}</math> sind.

Allgemein besteht das Einheits-Kreuzpolytop aus

:<math>2^{k+1} \cdot {n \choose {k+1}}</math>

Komponenten der Dimension <math>k</math>.
{| class="wikitable"
| rowspan="2" align="center" |&nbsp;
! rowspan="2" align="left" |[[Schläfli-Symbol|Schläfli-]]
[[Schläfli-Symbol|Symbol]]
! colspan="8" align="center" class="hintergrundfarbe6" |Anzahl der Grenzelemente
|- class="hintergrundfarbe6"
!0-dim.
!1-dim.
!2-dim.
!3-dim.
!{{nowrap|4-dim.}}
!<math>\ldots</math>
!<math>(n\!-\!1)</math>-dim.
!<math>n</math>-dim.
|- align="right"
! align="center" class="hintergrundfarbe6" |Punkt
| align="left" |<math>()</math>
| class="hintergrundfarbe5" |1
|
|
|
|
|
|
|
|- align="right"
! align="center" class="hintergrundfarbe6" |Strecke
| align="left" |<math>\{\}</math>
| class="hintergrundfarbe5" |2
| class="hintergrundfarbe5" |1
|
|
|
|
|
|
|- align="right"
! align="center" class="hintergrundfarbe6" |Quadrat
| align="left" |<math>\{4\}</math>
| class="hintergrundfarbe5" |4
| class="hintergrundfarbe5" |4
| class="hintergrundfarbe5" |1
|
|
|
|
|
|- align="right"
! align="center" class="hintergrundfarbe6" |Oktaeder
| align="left" |<math>\{3,4\}</math>
| class="hintergrundfarbe5" |6
| class="hintergrundfarbe5" |12
| class="hintergrundfarbe5" |8
| class="hintergrundfarbe5" |1
|
|
|
|
|- align="right"
! align="center" class="hintergrundfarbe6" |Hexadecachoron
| align="left" |<math>\{3,3,4\}</math>
| class="hintergrundfarbe5" |8
| class="hintergrundfarbe5" |24
| class="hintergrundfarbe5" |32
| class="hintergrundfarbe5" |16
| class="hintergrundfarbe5" |1
|
|
|
|- style="line-height:89%"
! class="hintergrundfarbe6" |<math>\vdots</math>
| align="center" |<math>\vdots</math>
| colspan="8" class="hintergrundfarbe5" align="center" |<math>\vdots</math>
|- align="right"
! align="center" class="hintergrundfarbe6" |<math>n</math>-dim. Kreuzpolytop
| align="left" |<math>\{3^{n-2},4\}</math>
| class="hintergrundfarbe5" |<math>2^1 \cdot \binom{n}{1}</math><math> = n + 1</math>
| class="hintergrundfarbe5" |<math>2^2 \cdot \binom{n}{2}</math>
| class="hintergrundfarbe5" |<math>2^3 \cdot \binom{n}{3}</math>
| class="hintergrundfarbe5" |<math>2^4 \cdot \binom{n}{4}</math>
| class="hintergrundfarbe5" align="center" |<math>\ldots</math>
| class="hintergrundfarbe5" |<math>\ldots</math>
| class="hintergrundfarbe5" |<math>2^n \cdot \binom{n}{n}</math><math> = 2^n</math>
| class="hintergrundfarbe5" |<math> 1</math>
|}

=== Symmetrien ===
[[Datei:Octahedron B2 planes.png|miniatur|Symmetrieebene bei einem dreidimensionalen Kreuzpolytop]]

Das Einheits-Kreuzpolytop ist [[Punktsymmetrie|punktsymmetrisch]] bezüglich des [[Koordinatenursprung]]s, das heißt, für alle <math>v \in \mathbb{R}^n</math> gilt

:<math>(v_1, \ldots , v_n) \in P \Rightarrow (-v_1, \ldots , -v_n) \in P</math>.

Weiterhin ist es symmetrisch bezüglich Spiegelungen an den [[Koordinatenebene]]n, das heißt, 

: <math>(v_1, \ldots, v_i, \ldots, v_n) \in P \Rightarrow (v_1, \ldots, - v_i, \ldots, v_n) \in P</math>

für <math>i=1, \ldots , n</math>. Die <math>n</math> Koordinatenebenen zerteilen dabei das Einheits-Kreuzpolytop in <math>2^n</math> [[Einheitssimplex|Einheitssimplizes]] des <math>\mathbb{R}^n</math>.

Die dabei entstehenden "Schnittflächen" (Schnitthyperebenen der Dimension n-1) mit den "Koordinatenebenen" (Koordinatenhyperebenen, für n=3 Koordinatenebenen, für n=2 Koordinatenachsen) sind jeweils Kreuzpolytope der Dimension n-1.

=== Volumen ===
Das <math>n</math>-dimensionale [[Volumen]] des Einheits-Kreuzpolytops beträgt

:<math>\operatorname{vol}(P) = \tfrac{2^n}{n!}</math>.

Das Volumen wird daher für wachsende Dimension beliebig klein.

== Reguläre Kreuzpolytope ==
=== Definition ===
Ein reguläres Kreuzpolytop ist ein Polytop, das aus dem Einheits-Kreuzpolytop durch [[Skalierung]], [[Drehung]] und [[Parallelverschiebung|Verschiebung]] hervorgeht. Ein Polytop <math>Q \subseteq \mathbb{R}^n</math> ist demnach ein reguläres Kreuzpolytop, wenn es eine reelle Zahl <math>\lambda > 0</math>, eine [[orthogonale Matrix]] <math>A \in \mathbb{R}^{n \times n}</math> und einen Vektor <math>b \in \mathbb{R}^n</math> gibt, sodass

:<math>Q = \lambda AP + b</math>

gilt.

=== Eigenschaften ===
Reguläre Kreuzpolytope haben dieselbe Anzahl von Ecken, Kanten und Facetten wie das Einheits-Kreuzpolytop. Sie besitzen auch die gleichen Symmetrieeigenschaften, lediglich das Symmetriezentrum und die Spiegelebenen werden entsprechend mittransformiert. Auch die Volumenformel bleibt erhalten und erhält lediglich einen zusätzlichen Faktor <math>\lambda^n</math>:

:<math>\operatorname{vol}(Q) = \lambda^n \cdot \tfrac{2^n}{n!}</math>.

Kreuzpolytop (oder Hyperoktaeder) und [[Maßpolytop]] (oder Hyperwürfel) sind zueinander [[Dualität (Mathematik)#Dualität in der Geometrie|dual]]. Daher stimmen auch ihre [[Symmetriegruppe]]n überein.

== Allgemeine Kreuzpolytope ==
[[Datei:Cross graph 4.svg|miniatur|Der [[Kantengraph]] eines vierdimensionalen Kreuzpolytops]]

=== Definition ===
Allgemein werden alle Polytope, die zum Einheits-Kreuzpolytop kombinatorisch äquivalent sind, Kreuzpolytope genannt. Präzise formuliert bedeutet das:
: Ein Polytop <math>Q \subseteq \mathbb{R}^n</math> heißt Kreuzpolytop, wenn es eine [[Bijektion]] <math>f</math> von der Menge der Ecken von <math>Q</math> auf die Menge der Ecken <math>\{ e_1, \ldots ,e_n, - e_1, \ldots ,- e_n \}</math> eines Einheits-Kreuzpolytops <math>P</math> gibt, sodass zwei Ecken <math>v</math> und <math>w</math> von <math>Q</math> genau dann durch eine Kante verbunden sind, wenn <math>f(v)</math> und <math>f(w)</math> dies in <math>P</math> sind.

=== Eigenschaften ===
Ein allgemeines Kreuzpolytop hat dieselbe Anzahl von Ecken, Kanten und Facetten wie das Einheits-Kreuzpolytop, doch die Symmetrien gehen verloren.

=== Verwendung ===
Das Kreuzpolytop gilt als Prototyp eines Polytops, das (in Relation zur Dimension) sehr wenige Ecken, aber sehr viele Facetten besitzt. Diese Eigenschaft ist in der linearen Optimierung besonders wichtig, da der [[Simplex-Algorithmus]], das Standardverfahren zur Lösung linearer Optimierungsprobleme, gezielt Ecken auf ihre Optimalität prüft. Das Gegenstück hierzu ist der [[Hyperwürfel]], dessen Eckenzahl exponentiell, die Facettenzahl aber nur linear in <math>n</math> anwächst.

== Weblinks ==
{{Commonscat|Polytopes|Polytope}}
* {{MathWorld|id=CrossPolytope|title=Cross Polytope}}
* [http://www.igt.uni-stuttgart.de/AbGeoTop/Feichtner/teaching/prev/geometry/4cross.pdf Zwei Darstellungen (Grafiken)] (PDF-Datei, 32 kB) der [[Universität Stuttgart]]
* [http://www.math.uni-hamburg.de/mathges/veranst/Zusamm/frank.html Kurze Definition] von Prof. Dr. Rolfdieter Frank der [[Universität Koblenz-Landau]] auf der Homepage der [[Universität Hamburg]]
* [http://www.math.ubbcluj.ro/~andrasz/dokumentumok/affin/konvexpolytopes.pdf Konvexe Polytope – WS 2003/2004] (PDF-Datei, 416 kB) von Achill Schürmann des Instituts für Algebra und Geometrie der [[Otto-von-Guericke-Universität Magdeburg]]
* [https://page.math.tu-berlin.de/~henk/preprints/henk&polynomdarstellungen%20von%20polyedern.pdf Polynomdarstellungen von Polyedern] (PDF-Datei, 320 kB) von Martin Henk der Universität Magdeburg

[[Kategorie:Polytop]]