Kreuzpolytop - LinkFang.de





Kreuzpolytop


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 [math]n[/math]-dimensionalen Raum ist die konvexe Hülle von [math]n[/math] 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.

Einheits-Kreuzpolytop

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 Vektorraums [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.
  • Das dreidimensionale Einheits-Kreuzpolytop ist ein Oktaeder und damit einer der 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, \ldots , v_n) \in \R^n \mid | v_1 | + | v_2 | + \ldots + | 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] Hyperebenen begrenzt.

Komponenten

Das Einheits-Kreuzpolytop ist konvex, abgeschlossen und zusammenhängend (bezüglich der 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 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].

Symmetrien

Das Einheits-Kreuzpolytop ist punktsymmetrisch bezüglich des Koordinatenursprungs, 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 Koordinatenebenen, 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] Einheitssimplizes des [math]\mathbb{R}^n[/math].

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 Verschiebung hervorgeht. Ein Polytop [math]Q \subseteq \mathbb{R}^n[/math] ist demnach ein reguläres Kreuzpolytop, wenn es eine reelle Zahl [math]\lambda \gt 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 dual. Daher stimmen auch ihre Symmetriegruppen überein.

Allgemeine Kreuzpolytope

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


Kategorien: Geometrie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kreuzpolytop (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.