Polytop (Geometrie)

Polytop bezeichnet in der Geometrie ein verallgemeinertes Polygon in beliebiger Dimension. Man spricht von k-Polytopen, wobei k die Dimension ist.

Definition

Ein 0-Polytop ist eine einzelne Ecke (ein Punkt); ein 1-Polytop besteht aus zwei Ecken, die durch eine Kante verbunden sind; ein 2-Polytop besteht aus mehreren, jeweils an einer Ecke verbundenen, einen Zyklus bildenden 1-Polytopen und stellt somit ein Polygon dar; ein 3-Polytop besteht wiederum aus mehreren an den Kanten verbundenen 2-Polytopen und stellt somit ein Polyeder dar; usw. Allgemein wird ein (k+1) -Polytop gebildet aus mehreren -Polytopen, die untereinander jeweils ein (k-1) -Polytop gemeinsam haben können (wie die gemeinsame Ecke zweier Kanten oder die gemeinsame Kante zweier Flächen). Des Weiteren müssen alle (k-1) -Unterpolytope in genau zwei -Polytopen enthalten sein, und zwischen zwei -Unterpolytopen muss eine Reihe von -Unterpolytopen existieren, so dass jeweils zwei benachbarte Glieder auf die zuvor beschriebene Weise verbunden sind – so bilden etwa nach dieser Definition mehrere disjunkte Polygone zusammen kein 2-Polytop.

Nomenklatur

In gewissen Dimensionen haben Polytope spezielle Namen erhalten, wie sie in folgender Tabelle aufgelistet sind:

Dimension	Name des d-Polytops
0	Punkt
1	Strecke
2	Polygon
3	Polyeder
4	Polychor

Betrachtet man ein Polytop der Dimension d, dann existieren folgende Bezeichnungen:

Dimension	Name des Unterpolytops
0	Ecke
1	Kante
d − 3	engl.: peak (etwa: „Spitze“)
d − 2	Grat (z.B. Ecke eines Polygons (d = 2), Kante eines Tetraeders (d = 3), …)
d − 1	Facette (z.B. Kante eines Polygons (d = 2), Seitenfläche eines Würfels (d = 3), …)
d	engl.: body (etwa: „Rumpf“)

Die Dimension eines Polytops ist dabei definiert als die Dimension seiner affinen Hülle, also des kleinsten affinen Raums, der enthält. Ein Würfel ist also dreidimensional, weil der kleinste Raum, der ihn enthält, dreidimensional ist. Ein eigentliches Polytop ist ein Polytop, das nicht ganz in einem echten Unterraum liegt, also dieselbe Dimension wie der betrachtete Raum hat.

Konvexe Polytope

Eine besondere Bedeutung in der Mathematik und der linearen Optimierung haben konvexe Polytope (oft auch nur Polytop), also Polytope, sodass die Verbindungsstrecke zwischen zwei beliebigen Punkten des Polytops wiederum komplett im Polytop enthalten ist. Dies sind genau die beschränkten konvexen Polyeder. Äquivalent dazu lassen sie sich als die konvexe Hülle endlich vieler Punkte (etwa der Eckpunkte) definieren.

Jedes eigentliche Polytop zerlegt den Raum in sein Inneres, sein Äußeres und seinen Rand. Jede Strecke, die einen inneren und einen äußeren Punkt verbindet, schneidet den Rand in genau einem Punkt. Der Durchschnitt zweier eigentlicher Polytope mit einem gemeinsamen inneren Punkt ist wieder ein eigentliches Polytop. Durch Induktion folgt dasselbe für endlich viele eigentliche Polytope mit einem gemeinsamen inneren Punkt.

Jeder Facette (Endpunkt für Strecken, Kante für Polygone etc.) eines Polytops lässt sich ein Halbraum zuordnen, auf dessen Rand die Facette liegt und der das Polytop enthält. Man stelle sich dazu den Teil des Raumes vor, der auf der dem Polytop zugewandten Seite der Seitenfläche liegt. Ein solcher Halbraum lässt sich als die Menge der Punkte auffassen, die eine lineare Ungleichung in ihren kartesischen Koordinaten erfüllen. Der Schnitt all der Halbräume zu jeder der Facetten ist wiederum das Polytop. Somit lässt sich jedes konvexe Polytop als Lösungsmenge eines linearen Ungleichungssystems in endlich vielen Variablen auffassen. Insofern die Lösungsmenge eines linearen Ungleichungssystems beschränkt ist (d.h. der Abstand aller Punkte voneinander beschränkt ist), gilt auch die Umkehrung.

Ist

$a^{T}x\leq b$

eine lineare Ungleichung, die von allen Punkten des Polytop erfüllt wird, dann wird der Schnitt des Polytops mit der Menge

$\{x|a^{T}x=b\}$

als Seitenfläche bezeichnet. Jede Seitenfläche lässt sich durch eine solche Ungleichung darstellen. Im Spezialfall der Ungleichung

$0^{T}x\leq 0$

ergibt sich als Schnitt das ganze Polytop, und für die Ungleichung

$0^{T}x\leq 1$

ist der Schnitt

$\{x|0^{T}x=1\}\cap P=\{x|0^{T}x=1\}=\varnothing$

die leere Menge. Die Menge aller Seitenflächen eines Polytops ist bzgl. Inklusion verbandsgeordnet. Eine Facette eines -dimensionalen konvexen Polytops ist dann eine (n-1) -dimensionale Seitenfläche. Bei einem dreidimensionalen Würfel sind beispielsweise alle Ecken, Kanten und Flächen des Würfels „Seitenflächen“, aber auch die leere Menge und der ganze Würfel. Aber nur die zweidimensionalen Seitenflächen sind Facetten des Würfels.

Eine Ecke eines konvexen Polytops ist ein Punkt im Polytop, der sich nicht durch andere Punkte des Polytops konvex kombinieren lässt, der also nicht auf einer Strecke zwischen zwei anderen Punkten des Polytops liegt. Dies entspricht der anschaulichen Vorstellung einer Ecke. Beispielsweise lässt sich keine Strecke zwischen zwei Punkten eines Würfels konstruieren, die eine Ecke als inneren Punkt enthält. Eine Ecke eines Polytops heißt entartet, wenn die Anzahl der Facetten, die enthalten, größer ist als die Dimension von . Beispielsweise ist die Spitze einer dreidimensionalen Pyramide mit quadratischer Grundfläche entartet, weil sie in vier Facetten enthalten ist. Ein konvexes Polytop heißt ganzzahlig, wenn alle seine Ecken durch ganzzahlige Koordinaten beschrieben werden. Diese Begriffe sind unter anderem in der linearen und ganzzahligen linearen Optimierung von Bedeutung, weil das Optimum eines linearen Programms stets auch in einer Ecke angenommen wird.

Basierend auf einem Artikel in:

Wikipedia.de