Polytop (Geometrie)
Ein Polytop (das, von altgriechisch πολύς polýs ‚viel‘ und τόπος tópos ‚Ort‘; Plural Polytópe) in der Geometrie ist ein verallgemeinertes Polygon in beliebiger Dimension. Man spricht von -Polytopen, wobei die Dimension ist.
.gif)
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 -Polytop gebildet aus mehreren -Polytopen, die untereinander jeweils ein -Unterpolytop gemeinsam haben können (wie die gemeinsame Ecke zweier Kanten oder die gemeinsame Kante zweier Flächen). Alle -Unterpolytope müssen in genau zwei -Polytopen enthalten sein, welch letztere dann als benachbart gelten. Ferner muss zwischen zwei -Polytopen eine Kette von benachbarten -Polytopen existieren, so dass jeweils zwei Glieder auf die beschriebene Weise durch ein -Unterpolytop verbunden sind – so bilden etwa mehrere disjunkte Polygone zusammen kein 3-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 (Vieleck) |
| 3 | Polyeder (Vielflächner) |
| 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
eine lineare Ungleichung, die von allen Punkten des Polytop erfüllt wird, dann wird der Schnitt des Polytops mit der Menge
als Seitenfläche bezeichnet. Jede Seitenfläche lässt sich durch eine solche Ungleichung darstellen. Im Spezialfall der Ungleichung
ergibt sich als Schnitt das ganze Polytop, und für die Ungleichung
ist der Schnitt
die leere Menge. Die Menge aller Seitenflächen eines Polytops ist bzgl. Inklusion verbandsgeordnet. Eine Facette eines -dimensionalen konvexen Polytops ist dann eine -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.
Literatur
- Harold Scott MacDonald Coxeter: Regular Polytopes. 3. Auflage. Dover Publications, 1973, ISBN 0-486-61480-8.
- Günter M. Ziegler: Lectures on Polytopes (= Graduate Texts in Mathematics. Nr. 152). Springer Verlag, 1995, ISBN 0-387-94365-X.
- Branko Grünbaum: Convex Polytopes. Hrsg.: Volker Kaibel, Victor Klee, Günter M. Ziegler. 2. Auflage. Springer-Verlag, 2003, ISBN 0-387-00424-6 (Erstausgabe: 1967).