Kreuzpolytop

regelmäßiges Polytop, das zum Hyperwürfel dual ist

Ein Kreuzpolytop oder Hyperoktaeder ist in der Geometrie ein Polytop, das eine Verallgemeinerung eines Oktaeders vom dreidimensionalen Raum auf Räume beliebiger Dimension darstellt. Ein Kreuzpolytop im -dimensionalen Raum ist die konvexe Hülle von 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 rechtwinklig. Die Symmetriegruppe eines regulären Kreuzpolytops ist die Hyperoktaedergruppe. Neben Hyperwürfeln und regulären Simplizes sind reguläre Kreuzpolytope die einzigen regulären Polytope, die in beliebigen Dimensionen existieren. Kreuzpolytope finden Anwendung unter anderem in der linearen Optimierung.

Ein Oktaeder ist ein dreidimensionales Kreuzpolytop

Einheits-Kreuzpolytop

Bearbeiten
 
Zweidimensionales Einheits-Kreuzpolytop mit Koordinatenachsen

Definition

Bearbeiten

Das  -dimensionale Einheits-Kreuzpolytop ist die konvexe Hülle der   Ecken  :

 .

Dabei bezeichnet   den  -ten Einheitsvektor des Vektorraums  .

Beispiele

Bearbeiten
  • Das eindimensionale Einheits-Kreuzpolytop ist das abgeschlossene Einheitsintervall  .
  • Das zweidimensionale Einheits-Kreuzpolytop ist ein (auf die Spitze gestelltes) Quadrat.
  • Das dreidimensionale Einheits-Kreuzpolytop ist ein Oktaeder und damit einer der platonischen Körper.

Darstellung

Bearbeiten

Das Einheits-Kreuzpolytop lässt sich auch folgendermaßen als Punktmenge im  -dimensionalen Raum darstellen:

 .

Das Einheits-Kreuzpolytop ist damit die Einheitskugel bezüglich der Summennorm  . Diese Betragsungleichung lässt sich auch als System von   linearen Ungleichungen umschreiben. Daher wird das Einheits-Kreuzpolytop durch genau   Hyperebenen begrenzt.

Komponenten

Bearbeiten

Das Einheits-Kreuzpolytop ist konvex, abgeschlossen und zusammenhängend (bezüglich der euklidischen Metrik). Es besteht aus folgenden Komponenten:

  • Es hat   Ecken, eben die (positiven und negativen) Einheitsvektoren.
  • Es hat   Kanten, denn jede Ecke   ist außer mit der gegenüberliegenden Ecke   mit jeder anderen über eine Kante verbunden.
  • Es hat   Facetten, die Simplizes des   sind.

Allgemein besteht das Einheits-Kreuzpolytop aus

 

Komponenten der Dimension  .

  Schläfli-

Symbol

Anzahl der Grenzelemente
0-dim. 1-dim. 2-dim. 3-dim. 4-dim.    -dim.  -dim.
Punkt   1
Strecke   2 1
Quadrat   4 4 1
Oktaeder   6 12 8 1
Hexadecachoron   8 24 32 16 1
     
 -dim. Kreuzpolytop                    

Symmetrien

Bearbeiten
 
Symmetrieebene bei einem dreidimensionalen Kreuzpolytop

Das Einheits-Kreuzpolytop ist punktsymmetrisch bezüglich des Koordinatenursprungs, das heißt, für alle   gilt

 .

Weiterhin ist es symmetrisch bezüglich Spiegelungen an den Koordinatenebenen, das heißt,

 

für  . Die   Koordinatenebenen zerteilen dabei das Einheits-Kreuzpolytop in   Einheitssimplizes des  .

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.

Das  -dimensionale Volumen des Einheits-Kreuzpolytops beträgt

 .

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

Reguläre Kreuzpolytope

Bearbeiten

Definition

Bearbeiten

Ein reguläres Kreuzpolytop ist ein Polytop, das aus dem Einheits-Kreuzpolytop durch Skalierung, Drehung und Verschiebung hervorgeht. Ein Polytop   ist demnach ein reguläres Kreuzpolytop, wenn es eine reelle Zahl  , eine orthogonale Matrix   und einen Vektor   gibt, sodass

 

gilt.

Eigenschaften

Bearbeiten

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  :

 .

Kreuzpolytop (oder Hyperoktaeder) und Maßpolytop (oder Hyperwürfel) sind zueinander dual. Daher stimmen auch ihre Symmetriegruppen überein.

Allgemeine Kreuzpolytope

Bearbeiten
 
Der Kantengraph eines vierdimensionalen Kreuzpolytops

Definition

Bearbeiten

Allgemein werden alle Polytope, die zum Einheits-Kreuzpolytop kombinatorisch äquivalent sind, Kreuzpolytope genannt. Präzise formuliert bedeutet das:

Ein Polytop   heißt Kreuzpolytop, wenn es eine Bijektion   von der Menge der Ecken von   auf die Menge der Ecken   eines Einheits-Kreuzpolytops   gibt, sodass zwei Ecken   und   von   genau dann durch eine Kante verbunden sind, wenn   und   dies in   sind.

Eigenschaften

Bearbeiten

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

Verwendung

Bearbeiten

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   anwächst.

Bearbeiten
Commons: Polytope – Sammlung von Bildern, Videos und Audiodateien