Polytop (Geometrie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Polytop bezeichnet in der Geometrie ein verallgemeinertes Polygon in beliebiger Dimension. Man spricht von k-Polytopen, wobei k die Dimension ist. 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 k-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 k-Polytopen enthalten sein, und zwischen zwei k-Unterpolytopen muss eine Reihe von k-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[Bearbeiten]

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

Dimension Name des d-Polytops
0 Ecke
1 Kante
2 Polygon
3 Polyeder
4 Polychor

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

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

Ein eigentliches Polytop ist ein Polytop, das nicht ganz in einem echten Unterraum liegt, also dieselbe Dimension wie der betrachtete Raum hat.

Die Dimension eines Polytops P ist definiert als die Dimension seiner affinen Hülle, also des kleinsten affinen Raums, der P enthält. Ein Würfel ist also dreidimensional, weil der kleinste Raum, der ihn enthält, dreidimensional ist.

Konvexe Polytope[Bearbeiten]

Eine besondere Bedeutung in der Mathematik und der linearen Optimierung haben konvexe Polytope (oft auch nur Polytop oder konvexes Polyeder, teilweise lässt man Objekte zu, die von ihren Seitenflächen nicht ganz eingeschlossen werden, also in eine Richtung unbeschränkt sind), also Polytope, sodass die Verbindungsstrecke zwischen zwei beliebigen Punkten des Polytops wiederum komplett im Polytop enthalten ist. Ä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, Seitenfläche für Polyeder 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.

Etwas formaler ausgedrückt: ist

a^T x \leq b

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

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

eine Seitenfläche. 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. Eine Facette eines n-dimensionalen konvexen Polytops ist 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 x eines Polytops P heißt entartet, wenn die Anzahl der Facetten, die x enthalten, größer ist als die Dimension von P. 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.