Polytop (Geometrie)

Durch Ziehen kommt man vom Punkt, zur Gerade, zur Fläche, zum 3D-Würfel und zum 4D-Würfel

EinPolytop(das,vonaltgriechischπολύςpolýs‚viel‘ undτόποςtópos‚Ort‘;PluralPolytópe) in derGeometrieist ein verallgemeinertesPolygonin beliebiger Dimension. Man spricht von$d$-Polytopen, wobei$d$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 einPolygondar; ein 3-Polytop besteht wiederum aus mehreren an den Kanten verbundenen 2-Polytopen und stellt somit einPolyederdar; usw.

Allgemein wird ein$(d\!+\!1)$-Polytop gebildet aus mehreren$d$-Polytopen, die untereinander jeweils ein$(d\!\!-\!\!1)$-Unterpolytopgemeinsam haben können (wie die gemeinsame Ecke zweier Kanten oder die gemeinsame Kante zweier Flächen). Alle$(d\!\!-\!\!1)$-Unterpolytope müssen in genau zwei$d$-Polytopen enthalten sein, welch letztere dann als benachbart gelten. Ferner muss zwischen zwei$d$-Polytopen eine Kette von benachbarten$d$-Polytopen existieren, so dass jeweils zwei Glieder auf die beschriebene Weise durch ein$(d\!\!-\!\!1)$-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 desd-Polytops
0	Punkt
1	Strecke
2	Polygon(Vieleck)
3	Polyeder(Vielflächner)
4	Polychor

Betrachtet man ein Polytop der Dimensiond,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 “)

DieDimensioneines Polytops$P$ist dabei definiert als die Dimension seineraffinen Hülle,also des kleinstenaffinen Raums,der$P$enthält. Ein Würfel ist also dreidimensional, weil der kleinste Raum, der ihn enthält, dreidimensional ist. EineigentlichesPolytop 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 derlinearen OptimierunghabenkonvexePolytope (oft auch nurPolytop), also Polytope, sodass die Verbindungsstrecke zwischen zwei beliebigen Punkten des Polytops wiederum komplett im Polytop enthalten ist. Dies sind genau die beschränktenkonvexen Polyeder.Äquivalent dazu lassen sie sich als diekonvexe Hülleendlich 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.

JederFacette(Endpunkt für Strecken, Kante für Polygone etc.) eines Polytops lässt sich einHalbraumzuordnen, 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 ihrenkartesischen Koordinatenerfü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 eineslinearen Ungleichungssystemsin 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\}$

alsSeitenflächebezeichnet. 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$

dieleere Menge.Die Menge aller Seitenflächen eines Polytops ist bzgl. Inklusionverbandsgeordnet.Eine Facette eines$n$-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.

EineEckeeines konvexen Polytops ist ein Punkt im Polytop, der sich nicht durch andere Punkte des Polytopskonvex kombinierenlä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ßtentartet,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ßtganzzahlig,wenn alle seine Ecken durch ganzzahlige Koordinaten beschrieben werden. Diese Begriffe sind unter anderem in derlinearenundganzzahligen linearen Optimierungvon Bedeutung, weil dasOptimumeines linearen Programms stets auch in einer Ecke angenommen wird.

In der Optimierungstheorie werden die Durchschnitte endlich vieler abgeschlossener Halbräume des$\mathbb {R} ^{n}$als Polyederund beschränkte Polyeder als Polytope bezeichnet.Teilweise werden Polytope auch als konvexe Polyeder bezeichnet.

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).