Polytop (Geometrie)

Grundidee und Aufbau

Ein Polytop ist in der Geometrie eine Verallgemeinerung eines Polygons auf beliebige Dimensionen. Man spricht von einem d-Polytop, wobei d die Dimension angibt. Ein 0-Polytop ist ein einzelner Punkt, ein 1-Polytop ist eine Strecke mit zwei Ecken und einer verbindenden Kante, ein 2-Polytop ist ein Polygon, und ein 3-Polytop ist ein Polyeder. Höherdimensionale Polytope werden entsprechend aus Polytopelementen niedrigerer Dimension aufgebaut.

Allgemein entsteht ein (d+1)-Polytop aus mehreren d-Polytopen. Diese können jeweils ein gemeinsames (d−1)-Unterpolytop haben, zum Beispiel eine gemeinsame Ecke zweier Kanten oder eine gemeinsame Kante zweier Flächen. Wichtig ist: Jedes (d−1)-Unterpolytop muss in genau zwei d-Polytopen enthalten sein. Diese beiden d-Polytope gelten dann als benachbart.

Außerdem muss das gesamte Polytop zusammenhängend sein: Zwischen zwei beliebigen d-Polytopen muss eine Kette benachbarter d-Polytope existieren, bei der jeweils zwei aufeinanderfolgende Glieder durch ein gemeinsames (d−1)-Unterpolytop verbunden sind. Deshalb bilden mehrere voneinander getrennte Polygone zusammen kein 3-Polytop.

Namen und Dimension

Für Polytope bestimmter Dimensionen gibt es eigene Namen. Ein 0-Polytop heißt Punkt, ein 1-Polytop Strecke, ein 2-Polytop Polygon oder Vieleck, ein 3-Polytop Polyeder oder Vielflächner. In Dimension 4 spricht der Artikel von einem regulären vierdimensionalen Polytop.

Auch die Unterpolytope eines d-dimensionalen Polytops haben besondere Bezeichnungen. Ein 0-dimensionales Unterpolytop heißt Ecke, ein 1-dimensionales Unterpolytop Kante. Ein (d−2)-dimensionales Unterpolytop heißt Grat; Beispiele sind die Ecke eines Polygons bei d = 2 oder die Kante eines Tetraeders bei d = 3. Ein (d−1)-dimensionales Unterpolytop heißt Facette; Beispiele sind die Kante eines Polygons bei d = 2 oder die Seitenfläche eines Würfels bei d = 3. Für weitere Bezeichnungen nennt der Artikel englische Begriffe: ein (d−3)-dimensionales Unterpolytop heißt englisch peak, etwa „Spitze“, und ein d-dimensionales Unterpolytop heißt englisch body, etwa „Rumpf“.

Die Dimension eines Polytops P ist die Dimension seiner affinen Hülle. Die affine Hülle ist der kleinste affine Raum, der P enthält. Ein Würfel ist deshalb dreidimensional, weil der kleinste Raum, der ihn enthält, dreidimensional ist. Ein eigentliches Polytop ist ein Polytop, das nicht vollständig in einem echten Unterraum liegt, sondern dieselbe Dimension hat wie der betrachtete Raum.

Konvexe Polytope

Konvexe Polytope sind in der Mathematik und besonders in der linearen Optimierung wichtig. Ein Polytop heißt konvex, wenn für zwei beliebige Punkte des Polytops die ganze Verbindungsstrecke zwischen diesen Punkten ebenfalls vollständig im Polytop liegt. Konvexe Polytope sind genau die beschränkten konvexen Polyeder. Gleichwertig kann man sie als konvexe Hülle endlich vieler Punkte, zum Beispiel ihrer Eckpunkte, definieren.

Jedes eigentliche Polytop zerlegt den Raum in sein Inneres, sein Äußeres und seinen Rand. Jede Strecke, die einen inneren Punkt mit einem ä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 gilt dies auch für endlich viele eigentliche Polytope mit einem gemeinsamen inneren Punkt.

Jeder Facette eines Polytops kann ein Halbraum zugeordnet werden. Die Facette liegt auf dem Rand dieses Halbraums, und der Halbraum enthält das Polytop. Ein Halbraum lässt sich als Menge von Punkten beschreiben, die eine lineare Ungleichung in ihren kartesischen Koordinaten erfüllen. Der Schnitt aller zu den Facetten gehörenden Halbräume ist wieder das Polytop. Daher kann jedes konvexe Polytop als Lösungsmenge eines linearen Ungleichungssystems in endlich vielen Variablen aufgefasst werden. Umgekehrt gilt: Wenn die Lösungsmenge eines linearen Ungleichungssystems beschränkt ist, also die Abstände aller Punkte voneinander beschränkt sind, dann ist sie ein Polytop.

Seitenflächen, Facetten und Ecken

Ist a^T x ≤ b eine lineare Ungleichung, die von allen Punkten eines Polytops erfüllt wird, dann heißt der Schnitt des Polytops mit der Menge {x | a^T x = b} eine Seitenfläche. Jede Seitenfläche lässt sich durch eine solche Ungleichung darstellen. Im Spezialfall 0^T x ≤ 0 erhält man als Schnitt das ganze Polytop. Bei der Ungleichung 0^T x ≤ 1 ist der Schnitt {x | 0^T x = 1} ∩ P = {x | 0^T x = 1} = ∅, also die leere Menge.

Die Menge aller Seitenflächen eines Polytops ist bezüglich Inklusion verbandsgeordnet. Eine Facette eines n-dimensionalen konvexen Polytops ist eine (n−1)-dimensionale Seitenfläche. Bei einem dreidimensionalen Würfel zählen zum Beispiel alle Ecken, Kanten und Flächen des Würfels als Seitenflächen, außerdem die leere Menge und der ganze Würfel. Facetten des Würfels sind aber nur seine zweidimensionalen Seitenflächen.

Eine Ecke eines konvexen Polytops ist ein Punkt im Polytop, der sich nicht als konvexe Kombination anderer Punkte des Polytops darstellen lässt. Anschaulich liegt eine Ecke also nicht auf einer Strecke zwischen zwei anderen Punkten des Polytops. Bei einem Würfel kann man zum Beispiel keine Strecke zwischen zwei Punkten des Würfels so wählen, dass eine Würfelecke ein innerer Punkt dieser Strecke ist.

Bezug zur Optimierung

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. Ein Beispiel ist die Spitze einer dreidimensionalen Pyramide mit quadratischer Grundfläche: Sie ist entartet, weil sie in vier Facetten enthalten ist. Ein konvexes Polytop heißt ganzzahlig, wenn alle seine Ecken ganzzahlige Koordinaten haben.

Diese Begriffe sind in der linearen und ganzzahligen linearen Optimierung wichtig. Ein Grund ist, dass das Optimum eines linearen Programms stets auch in einer Ecke angenommen wird. In der Optimierungstheorie nennt man Durchschnitte endlich vieler abgeschlossener Halbräume des R^n Polyeder; beschränkte Polyeder heißen dort Polytope. Teilweise werden Polytope auch als konvexe Polyeder bezeichnet.