Konvexgeometrie Skript Teil 1

Konvexgeometrie
Dr. Theo Overhagen
Mathematik
Universität Siegen
Literatur
[1] Barvinok, A.: A Course in Convexity, Amer. Math. Soc., Providence, R.I., 2002.
[2] Bonnesen,T.,Fenchel,W.: Theorie der konvexen Körper, Springer, 1934, Reprint 1974.
[3] Eggleston,H.: Convexity, Cambridge Univ.Press, 1969.
[4] Ewald,G.: Combinatorial Convexity and Algebraic Geometry, Springer, 1996.
[5] Gruber, P.M.: Convex and Discrete Geometry, Springer, 2007.
[6] Gruber,P./Lekkerkerker,C.: Geometry of Numbers, North-Holland, 1987.
[7] Gruber/Wills (Hrsg.): Handbook of Convex Geometry, Vol.A+B, Elsevier Sc.Publ.North Holland, 1993.
[8] Grünbaum,B.: Convex Polytopes, Interscience Publ., London, 1967.
[9] Hadwiger,H.: Vorlesungen über Inhalt, Oberfläche und Isoperimetrie, Springer, 1957.
[10] Henk,M.: Convex Geometry, Vorlesungsskript TU Berlin, WS 2014/15.
[11] Hug,D./Weil,W.: A Course on Convex Geometry, Vorlesungsskript Universität Karlsruhe, 2010.
[12] Leichtweiß,K.: Konvexe Mengen, Springer, 1980.
[13] MacMullen,P.,Shephard,G.: Convex Polytopes and the Upper Bound Conjecture, Cambridge
Univ.Press, 1971.
[14] MacMullen,P.: Metrical Properties of Convex Sets, unveröffentlicht.
[15] Matousek, J.: Discrete Geometry, Springer 2002.
[16] Schneider,R.: Convex Bodies: The Brunn–Minkowski Theory, Cambridge Univ.Press, 1993.
[17] Webster,R.: Convexity, Oxford University Press, 1994.
[18] Ziegler,G.: Lectures on Polytopes, Springer, 1995.
I
1
1
Einleitung
Versteht man unter Geometrie“ zunächst einmal (ohne die Klassifikation durch das Erlanger Pro”
”
gramm“ von Felix Klein) die Untersuchung von Gebilden im Anschauungsraum (und höherdimensionaler Verallgemeinerungen), dann bieten sich die Objekte der linearen Geometrie in den affinen
Räumen wie Punkte, Geraden, Ebenen u.s.w. und die damit gebildeten Konfigurationen sowie sogenannte Mengen zweiter Ordnung wie Kegelschnitte bzw. Quadriken an. Für darüber hinaus gehende
Untersuchungen muß man den Rahmen der zu betrachtenden Objekte einschränken, um sinnvolle
Ergebnisse zu erzielen.
In der algebraischen Geometrie beschränkt man sich auf Punktmengen, die durch algebraische Gleichungen beschrieben werden können. In der Differentialgeometrie betrachtet man Kurven, Flächen
und andere Untermannigfaltigkeiten, die durch genügend oft differenzierbare Funktionen beschrieben
werden können.
Wir betrachten hier konvexe Mengen, d.h. Mengen, die mit zwei Punkten auch ihre Verbindungsstrecke
enthalten. Solche Mengen gibt es sicher in linearen Räumen (Vektorräumen und affinen Räumen). Da
wir auch Funktionale auf konvexen Mengen betrachten wollen, die mit Abständen verbunden sind
(Volumen, Oberflächen), betrachten wir euklidische Räume, i.a. den d-dimensionalen euklidischen
Raum.
2
2
2.1
Grundlagen
Der euklidische Raum, affine Unterräume
Im folgenden sei
IE d = {x; x = (ξ1 , . . . , ξd ), ξi ∈ IR, 1 ≤ i ≤ d}
der d-dimensionale euklidische Raum mit dem natürlichen Skalarprodukt
xy :=
d
X
ξi ηi
i=1
und der induzierten Norm
kxk =
√
xx =
d
X
ξi2
i=1
bzw. der zugehörigen euklidischen Metrik
v
u d
uX
2
d(x, y) := kx − yk = t
ξi − ηi .
i=1
Als Verallgemeinerung der Vektoraddition und Skalarmultiplikation auf Mengen ergibt sich die
(Minkowski-)Summe von zwei Mengen und das Vielfache einer Menge
A + B := {x + y; x ∈ A, y ∈ B},
λA := {λx; x ∈ A}.
Eine Summe der Form
x + B := {x} + B
heißt auch Translat von B, und es gilt
A+B =
[
(x + B).
x∈A
Beispiel 2.1.1
✻
✻
✻
r
r
✲
Quadrat A
✲
Kreis B
✲
Summe A + B
2. Grundlagen
Bemerkung 2.1.2 Es gelten zwar viele der zu erwartenden Rechenregeln für Minkowski-Summen
und für Vielfache von Mengen wie Kommutativität, Assoziativität, Existenz des neutralen Elements
{0} wie
1 · A = A,
λ(µA) = (λ · µ)A,
λ(A + B) = λA + λB,
aber i.a. gilt für A 6= ∅ nur
{0} ⊂ A + (−A)
bzw. allgemein
(λ + µ)A ⊂ λA + µA,
und nicht die Gleichheit.
Lineare Unterräume sind für unsere Betrachtungen zu speziell, da sie immer den Nullpunkt enthalten.
Daher betrachten wir zusätzlich Translate von linearen Unterräumen, die affinen Unterräume im
IE d . Die leere Menge ∅ betrachten wir auch als affinen Unterraum.
Es gilt
Satz 2.1.3 U ⊂ IE d ist affiner Unterraum
⇐⇒
^
x,y∈U,λ∈IR
λx + (1 − λ)y ∈ U.
Durch Vorgabe des Translationsvektors und des linearen Unterraums erhält man natürlich den eindeutig bestimmten affinen Unterraum. Umgekehrt bestimmt ein affiner Unterraum eindeutig den
zugehörigen linearen Unterraum (wogegen verschiedene Translationsvektoren mit gleichem linearen
Unterraum zu demselben affinen Unterraum führen können):
Korollar 2.1.3.1 Ist U 6= ∅ ein affiner Unterraum, dann gibt es genau einen linearen Unterraum U0
des IE d , so dass U Translat von U0 ist.
Beispiele 2.1.4 Die affinen Unterräume im IE 3 sind außer der leeren Menge und dem ganzen Raum
- die Mengen, die nur aus einem Punkt bestehen,
- die Geraden und
- die Ebenen.
Geraden und Ebenen werden auch in der üblichen Parameterdarstellung
{x = a + λ(b − a); λ ∈ IR}
bzw.
{x = a + λ(b − a) + µ(c − a); λ, µ ∈ IR}
beschrieben.
Wir bezeichnen im folgenden zwei affine Unterräume als parallel, wenn sie Translate voneinander sind.
Speziell ist jeder affine Unterraum parallel zu sich selbst, und im Gegensatz zur üblichen Definition
der Parallelität in der Elementargeometrie vergleichen wir nur affine Unterräume gleicher Dimension.
Analog zur Vektorraumtheorie ergibt sich
Satz 2.1.5 Der Durchschnitt beliebig vieler affiner Unterräume ist ein affiner Unterraum.
3
2. Grundlagen
Bemerkung 2.1.6 Die Vereinigung affiner Unterräume ist i.a. kein affiner Unterraum.
Definition 2.1.7 Sei X ⊂ IE d . Der Durchschnitt aller affinen Teilräume U von IE d mit X ⊂ U heißt
affine Hülle von X. Bezeichnung: aff X.
Bemerkungen 2.1.8
(1) aff X ist (bezüglich der Inklusion) der kleinste affine Unterraum, der X enthält.
(2) Da IE d ein affiner Unterraum ist und X enthält, ist die Menge der in Frage kommenden affinen
Unterräume, über die der Durchschnitt gebildet wird, nicht leer.
⇐⇒
(3) X ist affiner Unterraum
aff X = X.
Die Charakterisierung affiner Unterräume nach Satz 2.1.3 läßt sich verallgemeinern:
Definition 2.1.9 Für x0 , x1 , . . . , xn ∈ IE d , λ0 , . . . , λn ∈ IR mit
x :=
n
X
λi xi
n
X
λi = 1 heißt
i=0
Affinkombination von x0 , . . . , xn .
i=0
Satz 2.1.10
U.
(a) Ist U affiner Unterraum, dann enthält U alle Affinkombinationen von Punkten aus
(b) Für X 6= ∅ ist aff X die Menge aller Affinkombinationen aus X.
Für Summen und Vielfache von affinen Unterräumen gilt (im Gegensatz zu Bemerkung 2.1.2)
Satz 2.1.11 Seien Ai , 1 ≤ i ≤ n, affine Unterräume, λi ∈ IR, 1 ≤ i ≤ n.
(a) Dann ist
n
X
λi Ai ein affiner Unterraum.
i=1
(b) Ist
n
X
i=1
λi 6= 0, dann gilt
(λ1 + . . . + λn )A1 = λ1 A1 + . . . + λn A1 .
Ist U ein nichtleerer affiner Unterraum, U0 der zugehörige lineare Unterraum mit U = a + U0 , dann
gibt es in U0 eine maximale Menge linear unabhängiger Vektoren x1 , . . . , xr , sie bilden eine Basis
von U0 , ihre Anzahl ist eine Invariante von U0 und heißt Dimension von U0 . Betrachtung der Punkte
a, a + x1 , . . . , a + xr in U führt zu folgender Definition:
4
2. Grundlagen
Definition 2.1.12 (a) Eine endliche Menge von Punkten a0 , . . . , an ∈ IE d heißt affin abhängig
genau dann, wenn es Skalare λ0 , . . . , λn ∈ IR gibt mit
n
X
λ2i > 0,
i=0
n
X
λi = 0
i=0
und
n
X
λi ai = 0.
i=0
Sonst heißt sie affin unabhängig.
(b) Eine beliebige Menge M ⊂ IE d heißt affin abhängig, wenn sie eine endliche affin abhängige
Teilmenge enthält.
(c) Ist U ein nichtleerer affiner Unterraum mit zugehörigem linearen Unterraum U0 , dann heißt
dim U0 die Dimension von U . Bezeichnung: dim U .
Für die leere Menge setzt man dim ∅ := −1.
Ist U = a + U0 und B0 = {x1 , . . . , xr } eine Basis von U0 , dann heißt B = {a, a + x1 , . . . a + xr }
affine Basis von U .
(d) Ist X eine nichtleere Menge, dann heißt die Dimension der affinen Hülle aff X Dimension von
X. Bezeichnung: dim X.
(e) Die affinen Unterräume der Dimension 1 heißen Gerade, der Dimension 2 Ebene und der
Dimension d − 1 Hyperebene.
Analog zur Vektorraumtheorie folgt
Satz 2.1.13 (a) Eine Menge M ⊂ IE d ist genau dann affin abhängig, wenn es ein a ∈ M gibt mit
a ∈ aff (M \ {a}).
(b) Ist M := {a0 , . . . , ar } affin unabhängig, dann läßt sich jedes a ∈ aff M eindeutig als Affinkombin
X
nation aus Punkten von M darstellen, d.h. es existieren λi ∈ IR, 0 ≤ i ≤ n, mit
λi = 1 und
a=
n
X
i=0
λi ai . Die Skalare λ0 , . . . , λn heißen baryzentrische Koordinaten.
i=0
(c) Eine affin unabhängige M ⊂ IE d hat höchstens d + 1 Elemente.
(d) Jeder nichtleere affine Unterraum U ⊂ IE d ist affine Hülle einer affinen Basis mit dim U + 1
Elementen.
(e) Sind U und V affine Unterräume des IE d mit nichtleerem Durchschnitt, dann gilt
dim(U + V ) + dim(U ∩ V ) = dim U + dim V.
(f ) Ist U ein affiner Unterraum des IE d und M ⊂ U eine affin unabhängige Teilmenge, dann gibt es
eine affine Basis B von U mit M ⊂ B, d.h. M kann zu einer Basis von U erweitert werden.
(g) Jede nichtleere Menge M ⊂ IE d enthält eine affine Basis von aff M .
5
2. Grundlagen
Lineare Unterräume des IE d der Dimension r haben einen engen Bezug zur Lösungsmenge eines linearen homogenen Gleichungssystems mit Koeffizientenmatrix vom Rang d − r. Analog haben affine
Unterräume eine entsprechende Beziehung zu linearen (möglicherweise inhomogenen) Gleichungssystemen:
Satz 2.1.14 Sei d ≥ 1.
(a) Eine Menge M ⊂ IE d ist eine Hyperebene genau dann, wenn es einen Vektor n 6= 0 und ein
Skalar α ∈ IR gibt mit
M = {x; n · x = α}.
n heißt Normalenvektor der Hyperebene. Der Normalenvektor einer Hyperebene ist bis auf
Skalarmultiplikation eindeutig bestimmt.
(b) Jeder affine Unterraum der Dimension r, −1 ≤ r ≤ d, kann als Durchschnitt von d − r Hyperebenen dargestellt werden und ist damit Lösungsmenge eines linearen Gleichungssystems von
d − r Gleichungen.
(c) Zwei Hyperebenen
H = {x; n · x = α}
und
H ′ = {x; n′ · x = α′ }
sind parallel genau dann, wenn die Normalenvektoren n und n′ linear abhängig sind. Die Hyperebenen sind dann identisch oder disjunkt.
(d) Zwei nicht parallele Hyperebenen haben einen nichtleeren Durchschnitt.
Ersetzt man die die Hyperebene bestimmende lineare Gleichung durch eine Ungleichung, dann erhält
man
Definition 2.1.15 Ist n ∈ IE d , n 6= 0, α ∈ IR, dann heißen die Mengen
H − := {x; n · x ≤ α}
und
H + := {x; n · x ≥ α}
und
int H + := {x; n · x > α}
abgeschlossene Halbräume und die Mengen
int H − := {x; n · x < α}
offene Halbräume.
Bemerkungen 2.1.16
(1) Ersetzt man den Vektor n und das Skalar α durch jeweils dasselbe Vielfache, d.h. durch λn und
λα (mit λ 6= 0), dann erhält man dieselben Halbräume. Die Halbräume werden also durch die
Hyperebene H = {x; n · x = α} eindeutig festgelegt.
Es gilt
H − ∪ H + = IE d ,
H − ∩ H + = H,
int H − ∪ int H + = IE d \ H,
int H − ∩ int H + = ∅.
6
2. Grundlagen
(2) Die offenen Halbräume sind (bezüglich der durch das Skalarprodukt induzierten Metrik) offene Mengen, die abgeschlossenen Halbräume und die affinen Unterräume sind abgeschlossene
Mengen.
(3) Liegen zwei Punkte a und b in verschiedenen offenen Halbräumen bezüglich der Hyperebene H,
dann schneidet die offene Verbindungsstrecke {x = a + λ(b − a), 0 < λ < 1} die Hyperebene H
in genau einem Punkt.
Wie die linearen Abbildungen die Vektorraumstruktur erhalten, gibt es entsprechende Abbildungen,
bei denen die Bilder affiner Unterräume ebenfalls affin sind.
Definition 2.1.17 Eine Abbildung T : IE d → IE m heißt affin, wenn
T λx + (1 − λ)y = λT (x) + (1 − λ)T (y)
für alle x, y ∈ IE d , λ ∈ IR.
Beispiele 2.1.18
(1) Die Translationen T : IE d → IE d mit T (x) := x + a (mit festem a ∈ IE d ) sind affine Abbildungen.
(2) Die Orthogonalprojektion T : IE 3 → IE 3 mit T (ξ1 , ξ2 , ξ3 ) := (ξ1 , ξ2 , 1) ist eine affine Abbildung.
Zwischen linearen und affinen Abbildungen gibt es enge Beziehungen, und damit ergeben sich wichtige
Eigenschaften der affinen Abbildungen:
Satz 2.1.19 Sei T : IE d → IE m eine Abbildung.
(a) T ist genau dann affin, wenn es eine lineare Abbildung T0 und ein q ∈ IE m mit
T (x) = T0 (x) + q
für alle x ∈ IE d .
Die lineare Abbildung T0 ist durch T eindeutig bestimmt.
(b) T ist genau dann affin, wenn
T
n
X
i=0
λi xi =
n
X
i=0
λi T (xi )
d
für alle n ∈ IN0 , xi ∈ IE , λi ∈ IR, 0 ≤ i ≤ n, mit
n
X
λi = 1.
i=0
(c) Ist T affin, M ⊂ IE d eine beliebige Menge. Dann gilt
T (aff M ) = aff T (M ) .
Ist M ein affiner Unterraum, dann auch T (M ).
(d) Ist M = {x0 , . . . , xd } eine affine Basis des IE d , {y0 , . . . , yd } ⊂ IE m , dann gibt es genau eine
affine Abbildung T : IE d → IE m mit T (xi ) = yi , 0 ≤ i ≤ d.
7
2. Grundlagen
Die Invertierbarkeit einer affinen Abbildung hängt mit der Invertierbarkeit der zugehörigen linearen
Abbildung zusammen:
Satz 2.1.20 Sei T : IE d → IE d eine affine Abbildung.
(a) T ist invertierbar genau dann, wenn die zugehörige lineare Abbildung T0 invertierbar ist.
(b) Ist T invertierbar, dann ist T −1 eine affine Abbildung mit zugehöriger linearer Abbildung T0−1 .
(c) Sind A, B ⊂ IE d gleichdimensionale affine Unterräume, dann gibt es eine invertierbare affine
Abbildung T : IE d → IE d mit T (A) = B.
In einem euklidischen Raum (in dem man Abstände messen kann,) sind auch die Abbildungen interessant, die Abstände nicht verändern.
Definition 2.1.21 Eine Abbildung T : IE d → IE d heißt Kongruenzabbildung des IE d , wenn
für alle x, y ∈ IE d .
kT (x) − T (y)k = kx − yk
Kongruenzabbildungen sind spezielle affine Abbildungen, denn es gilt
Satz 2.1.22 Ist T : IE d → IE d eine Kongruenzabbildung des IE d , dann ist T eine affine Abbildung mit
einer zugehörigen orthogonalen linearen Abbildung.
2.2
Konvexe Mengen
Definition 2.2.1 Sei X ⊂ IE d eine Menge.
(a) X heißt konvex, wenn
z := λx + (1 − λ)y ∈ X
für alle x, y ∈ X, 0 ≤ λ ≤ 1.
(b) Ist X konvex und kompakt, dann heißt X konvexer Körper.
(c) Der Durchschnitt aller konvexen Mengen K von IE d mit X ⊂ K heißt konvexe Hülle von X.
Bezeichnung: conv X.
Wir bezeichnen im folgenden
- die Familie der konvexen Mengen im IE d mit Kd und
bd.
- die Familie der konvexen Körper im IE d mit K
Bemerkung 2.2.2 Für beliebige Mengen A ⊂ B ⊂ IE d gilt conv A ⊂ conv B.
8
2. Grundlagen
Beispiele 2.2.3
(1) Eine Menge heißt also konvex, wenn sie mit je zwei Punkten x, y auch deren Verbindungstrecke
xy := {z ∈ IE d ; z = x + λ(y − x), 0 ≤ λ ≤ 1}
enthält. Im besonderen sind Strecken konvex.
(2) Affine Unterräume sind dadurch charakterisiert, dass mit je zwei Punkten ihre Verbindungsgerade in der Menge enthalten ist. Damit folgt, dass jeder affine Unterraum eine konvexe Menge
ist, speziell auch der ganze Raum, die Hyperebenen, die Geraden, die einpunktigen Mengen und
die leere Menge.
(3) Sei a ∈ IE d , r > 0. Die offene Kugel
B(a; r) := {x ∈ IE d ; kx − ak < r}
mit Mittelpunkt a und Radius r ist konvex und die abgeschlossene Kugel
B[a; r] := {x ∈ IE d ; kx − ak ≤ r}
ist ein konvexer Körper.
Der Kugelrand (die Sphäre) S(a; r) := bd B(a, r) := {x ∈ IE d ; kx − ak = r} ist nicht konvex.
(4) Sei H eine Hyperebene. Dann sind die zugehörigen offenen und abgeschlossenen Halbräume
konvex.
Analog zu den Betrachtungen der linearen bzw. affinen Geometrie gilt:
Satz 2.2.4
(a) Der Durchschnitt beliebig vieler konvexer Mengen im IE d ist eine konvexe Menge.
Speziell ist die konvexe Hülle einer beliebigen Menge konvex.
(b) Ist K ⊂ IE d eine konvexe Menge, T : IE d → IE m eine affine Abbildung, dann ist T (K) konvex.
(c) Ist K ′ ⊂ IE m eine konvexe Menge, T : IE d → IE m eine affine Abbildung, dann ist T −1 (K ′ )
konvex.
Bemerkungen 2.2.5
(1) Die Vereinigung konvexer Mengen ist i.a. nicht konvex.
(2) Ist eine Familie konvexer Mengen bezüglich der Inklusion linear geordnet, dann ist ihre Vereinigung konvex.
(3) Im Sinne von Kleins Erlanger Programm“ gehört die Konvexgeometrie zur affinen Geometrie.
”
n
X
d
Definition 2.2.6 Für n ∈ IN0 , xi ∈ IE , λi ∈ IR, 0 ≤ i ≤ n mit λi ≥ 0 und
λi = 1 heißt
i=0
x :=
n
X
i=0
λi xi
Konvexkombination von x0 , . . . , xn .
9
2. Grundlagen
10
Satz 2.2.7 (a) Ist K eine konvexe Menge, dann enthält K alle Konvexkombinationen von Punkten
aus K.
(b) conv X ist die Menge aller Konvexkombinationen aus X.
(c) X ist konvex
⇐⇒
X = conv X.
Bemerkungen 2.2.8
n
n
X
X
(1) Für X = {a1 , . . . , an } ist conv X = {
λi ai ; λi ≥ 0, 1 ≤ i ≤ n,
λi = 1}.
i=1
i=1
conv X hängt also nur von den Punkten a1 , . . . , an ab.
(2) Für jede Menge X gilt conv (conv X) = conv X.
(3) Im Gegensatz zu linearen und affinen Unterräumen lassen sich konvexe Mengen i.a. nicht aus
endlichen Mengen erzeugen. Beispiel: Kreis bzw. Parabel im IE 2 .
Beispiele 2.2.9
(1) Mit Hilfe von Satz 2.2.7 (b) kann man die konvexe Hülle einer Menge X von innen“ konstruieren.
”
Die konvexe Hülle von
- 2 verschiedenen Punkten ist ihre (abgeschlossene) Verbindungsstrecke,
- 3 affin unabhängigen Punkten (in der entsprechenden Ebene) ist das Dreieck mit diesen
Punkten als Ecken,
- 4 affin unabhängigen Punkten im IE 3 ist das Tetraeder mit diesen Punkten als Ecken.
(2) Die konvexe Hülle der Einheitssphäre S(0; 1) ist die abgeschlossene Einheitskugel B[0; 1].
Konvexe Hüllen endlicher Mengen sind von besonderer Bedeutung:
Definition 2.2.10 Sei X ⊂ IE d eine nichtleere endliche Menge der Dimension r.
(a) P := conv X heißt (konvexes) Polytop bzw. r-Polytop.
(b) Ist X affin unabhängig, so heißt P r-Simplex.
(c) T = conv {0, a1 , ..., ar } mit ai aj = 0 für i 6= j heißt Orthogonalsimplex.
Wir bezeichnen die Familie aller Polytope im IE d mit P d .
Die affine Hülle einer r-dimensionalen Menge X kann man als Menge der Affinkombinationen von
höchstens r + 1 Punkten aus X darstellen.
Für konvexe Hüllen ist das i.a. nicht richtig, denn z.B. das Einheitsquadrat
conv {(1; 1), (−1; 1), (−1; −1), (1; −1)}
läßt sich nicht als konvexe Hülle von 3 Punkten darstellen (denn das wäre ein Dreieck).
Für jeden einzelnen Punkt a ∈ conv X läßt sich die Anzahl der Summanden zur Darstellung von a als
Konvexkombination aus Punkten aus X auf r + 1 beschränken:
2. Grundlagen
11
Satz 2.2.11 (Caratheodory(1907)) Sei X eine nichtleere r-dimensionale Menge, a ∈ conv X.
r
X
λi = 1 und
Dann gibt es r + 1 Punkte {x0 , . . . , xr } ⊂ X, λi ∈ IR mit λi ≥ 0, 0 ≤ i ≤ r,
i=0
a=
r
X
λi xi .
i=0
Korollar 2.2.11.1 Jedes Polytop ist die Vereinigung von endlich vielen Simplices.
Die beiden folgenden Sätze sind eng mit dem Satz von Caratheodory verknüpft und von grundlegender
Bedeutung z.B. für die kombinatorische Geometrie der konvexen Mengen sowie Überdeckungs- und
Durchschnittsprobleme.
Satz 2.2.12 (Radon(1921)) Sei X = {x1 , . . . , xn } ⊂ IE d . Ist n ≥ d + 2, so existieren X1 , X2 ⊂ X
mit
X1 ∪ X2 = X,
X1 ∩ X2 = ∅
und
conv X1 ∩ conv X2 6= ∅.
Bemerkung 2.2.13
(1) X darf nicht weniger als d + 2 Elemente enthalten (Simplex).
(2) Die Zerlegung ist i.a. nicht eindeutig.
(3) Für 4 Punkte in IE 2 ergeben sich folgende Konstellationen:
- Einer der Punkte liegt in dem von den anderen 3 Punkten aufgespannten (möglicherweise
degenerierten) Dreieck, oder
- die vier Punkte sind Ecken eines konvexen Vierecks.
Der Durchschnitt konvexer Mengen ist konvex, aber er kann leer sein. Der folgende Satz gibt Bedingungen dafür an, daß der Durchschnitt einer Familie konvexer Mengen nichtleer ist.
Satz 2.2.14 (Helly(1913)) Seien n ∈ IN, n ≥ d + 1, K1 , . . . , Kn ∈ Kd , und je d + 1 der Ki haben
einen gemeinsamen Punkt. Dann gilt
n
\
Ki 6= ∅.
j=1
Bemerkung 2.2.15 Der Satz gilt i.a. nicht, wenn nur je m < d + 1 der Mengen einen nichtleeren
Durchschnitt haben oder mindestens eine der Mengen nicht konvex ist. Andererseits kann man einen
analogen Satz für eine unendliche Familie kompakter konvexer Mengen zeigen.
Eine interessante Fragestellung ist, ob sich metrische Eigenschaften einer Menge auf ihre konvexe Hülle
übertragen:
2. Grundlagen
12
Satz 2.2.16 Sei X ⊂ IE d .
(a) Ist X offen, dann ist conv X offen.
(b) Ist X kompakt, dann ist conv X kompakt.
Bemerkungen 2.2.17
(1) Für abgeschlossene Mengen gilt die Aussage i.a. nicht, wie das Beispiel mit
X := {(ξ; 0); ξ ∈ IR} ∪ {(0; 1)} ⊂ IE 2 zeigt.
(2) Die konvexe Hülle einer beschränkten Menge ist beschränkt.
Sei X eine nichtleere beschränkte Menge. Dann heißt
sup{kx − yk; x, y ∈ X}
Durchmesser von X.
Der Durchmesser eines Dreiecks ist seine längste Seite, der eines Rechtecks ist die Diagonalenlänge und der einer offenen oder abgeschlossenen Kugel mit Radius r ist 2r.
Es gilt sogar: X und conv X haben denselben Durchmesser.
(3) Jedes Polytop ist kompakt.
Umgekehrt überträgt sich die Eigenschaft der Konvexität auf den offenen Kern und die abgeschlossene
Hülle einer Menge:
Satz 2.2.18 Sei K ∈ IE d eine nichtleere konvexe Menge. Dann gilt:
(a) Für x ∈ cl K, y ∈ int K und die Verbindungsstrecke xy von x nach y ist xy\{x} ⊂ int K.
(b) Für int K 6= ∅ und x ∈ K gilt:
x ∈ int K
⇐⇒
für alle y ∈ K gibt es ein µ > 1 mit (1 − µ)y + µx ∈ K.
(c) int K ist konvex.
(d) cl K ist konvex.
Die Begriffe offener Kern“ und Rand“ sind für Mengen der Dimension kleiner d nicht besonders
”
”
sinnvoll.
Definition 2.2.19 Sei X ⊂ IE d nichtleer und A = aff X.
x ∈ X heißt relativ innerer Punkt von X, falls eine Umgebung B(x, r) mit r > 0 existiert mit
B(x, r) ∩ A ⊂ X.
Die Menge aller relativ inneren Punkte von X wird als relatives Inneres von X bezeichnet. (Schreibweise relint X)
2. Grundlagen
13
Satz 2.2.20 Sei K ∈ Kd , K 6= ∅. Dann gilt relint K 6= ∅ und relint K ist konvex.
Bemerkungen 2.2.21
(1) Sei K ⊂ IE d konvex. Dann gilt:
int K = ∅
⇐⇒
dim K < d.
Das ist nur dann erfüllt, wenn es eine Hyperebene H gibt mit K ⊂ H.
(2) Die Menge der entsprechend definierten relativen Randpunkte (bezüglich aff X) von X wird mit
relbd X bezeichnet. Für kompaktes X gilt offensichtlich X = relint X ∪ relbd X.
b d nichtleer, x ∈ relint K, y ∈ aff K, y 6∈ K. Dann schneiden sich conv {x, y}
Satz 2.2.22 Sei K ∈ K
und relbd K in genau einem Punkt.
Für Polytope läßt sich das relative Innere leicht beschreiben:
Satz 2.2.23 Sei P = conv {x1 , . . . , xn } ∈ P d . Dann gilt x ∈ relint P genau dann, falls positive
n
n
X
X
λi = 1 und x =
λi xi .
λ1 , . . . , λn ∈ IR existieren mit
i=1
i=1
Betrachtet man sowohl die Bildung des relativen Inneren als auch der abgeschlossenen Hülle, dann
gilt (für konvexe Mengen)
Satz 2.2.24 Für eine konvexe Menge K gilt
(a) relint K = relint (cl K)
(b) int K = int (cl K)
und
cl K = cl (relint K).
und, falls int K 6= ∅
(c) relbd K = relbd (cl K)
und
cl K = cl (int K).
bd K = bd (cl K).
Bemerkung 2.2.25 Satz 2.2.24 gilt i.a. nicht für nichtkonvexe Mengen.
Für Summen und Vielfache von konvexen Mengen gilt
Satz 2.2.26 Seien Ki , 1 ≤ i ≤ n, konvexe Mengen, λi ∈ IR, 1 ≤ i ≤ n.
(a) Dann ist
n
X
λi Ki konvex. Speziell sind Summen und Vielfache von konvexen Mengen konvex.
i=1
(b) Ist λi ≥ 0, 1 ≤ i ≤ n, dann gilt
(λ1 + . . . + λn )K1 = λ1 K1 + . . . + λn K1 .
Für beliebige Mengen A, B, C folgt i.a. aus A + B = A + C nicht B = C. Für beschränktes A und
konvexe abgeschlossene B, C gilt aber
Satz 2.2.27 Sei A eine nichtleere beschränkte Menge, C und D abgeschlossen und konvex. Dann gilt:
(a) A + B ⊂ A + C
=⇒
B ⊂ C.
(b) A + D = A + C
=⇒
D = C.
2. Grundlagen
2.3
14
Stützeigenschaften
Definition 2.3.1 Sei X ⊂ IE d , a ∈ IE d , a 6= 0, β ∈ IR. Die Hyperebene
H = {x ∈ IE d ; ax = β} ⊂ IE d
heißt Stützhyperebene von X, falls gilt:
H ∩ cl X 6= ∅
und
X ⊂ H+
oder
X ⊂ H− .
Für X ⊂ H − heißt a äußerer Normalenvektor von X und H − Stützhalbraum von X.
Beispiel 2.3.2 Die Tangentialhyperebenen an B(a; r) (und andere glatte konvexe Körper) sind
Stützhyperebenen.
Ein erstes Ergebnis über die Stützhyperebenen konvexer Hüllen gibt
Satz 2.3.3 Sei X ⊂ IE d , H Stützhyperebene von X. Dann gilt H ∩ conv X = conv (H ∩ X).
b d ein nichtleerer konvexer Körper und a ∈ IE d , a 6= 0. Dann existiert eine
Satz 2.3.4 Sei K ∈ K
Stützhyperebene H von K mit äußerem Normalenvektor a.
Bemerkung 2.3.5 Satz 2.3.4 gilt schon für beschränkte nichtleere Mengen X ⊂ IE d .
Im folgenden betrachten wir die Abbildung des IE d auf eine abgeschlossene konvexe Menge K, die
jedem Punkt p ∈ IE d den nächstgelegenen Punkt p′ ∈ K zuordnet:
Definition 2.3.6 Sei K ∈ Kd eine nichtleere abgeschlossene konvexe Menge und p ∈ IE d . Weiter sei
p′ ∈ K der (eindeutig bestimmte) Punkt mit
kp − p′ k = min{kp − qk; q ∈ K}.
(a) Die Abbildung Φ : IE d → K mit Φ(p) := p′ heißt Lotabbildung von K.
(b) Sei p 6∈ K. Die offene Halbgerade
−
→
p′ p := {x ∈ IE d ; x = p′ + λ(p − p′ ), λ ≥ 0}
mit Anfangspunkt p′ durch p heißt Strahl von K durch p.
Bemerkung 2.3.7 Zu p ∈ IE d ist p′ ∈ K eindeutig bestimmt und damit Φ wohldefiniert.
Die von p′ ausgehenden Strahlen haben die folgenden Eigenschaften:
2. Grundlagen
15
Satz 2.3.8 Sei K ∈ Kd abgeschlossen und nicht leer, Φ die Lotabbildung von K, p ∈ IE d \ K und
p′ = Φ(p).
−
→
(a) Für jedes q ∈ p′ p gilt Φ(q) = Φ(p).
−
→
(b) Die Hyperebene H durch p′ und orthogonal zu p′ p ist Stützhyperebene von K.
Damit kann man jede nichtleere abgeschlossene konvexe Menge durch ihre Stützhalbräume beschreiben:
Satz 2.3.9 Sei K ∈ Kd abgeschlossen und nicht leer. Dann ist K Durchschnitt aller Stützhalbräume
H − von K.
Korollar 2.3.9.1 Sei X ∈ IE d , X 6= ∅. Dann ist cl (conv X) Durchschnitt aller Halbräume, die X
enthalten.
Die wichtigsten Eigenschaften der Lotabbildung ergeben sich aus
Satz 2.3.10 Sei K ∈ Kd abgeschlossen und nicht leer, Φ die zugehörige Lotabbildung.
(a) Für alle p, q ∈ IE d gilt
kΦ(p) − Φ(q)k ≤ kp − qk,
d.h. die Lotabbildung vergrößert die Entfernung nicht.
(Lemma von Busemann-Feller)
(b) Die Lotabbildung Φ genügt einer Lipschitz-Bedingung mit Konstanten 1. Insbesondere ist sie
gleichmäßig stetig.
(c) Für p 6∈ K gilt
Φ(p) ∈ bd K.
(d) Ist K kompakt, B ⊂ IE d eine Kugel mit Rand S und K ⊂ int B. Dann ist
Φ|S : S → bd K
surjektiv.
Jeder Randpunkt einer nichtleeren konvexen Menge K ist in einer Stützhyperebene enthalten:
Satz 2.3.11 Sei K ∈ Kd nicht leer und p ∈ bd K. Dann existiert eine Stützhyperebene H von K mit
p ∈ H.
Die letzte Aussage läßt sich unter gewissen Voraussetzungen umkehren:
Satz 2.3.12 Sei d ≥ 2, X ⊂ IE d abgeschlossen, int X 6= ∅, und durch jeden Randpunkt von X gehe
eine Stützhyperebene von X. Dann ist X konvex.
2. Grundlagen
16
Bemerkung 2.3.13 Sowohl die Abgeschlossenheit als auch dim X = d ist notwendige Voraussetzung.
In engem Zusammenhang mit den Stützhyperebenen stehen die Stützfunktionen:
b d kompakt, K 6= ∅.
Definition 2.3.14 Sei K ∈ K
H(K, ·) : IE d → IR
mit
H(K, u) = sup{ux; x ∈ K}
heißt Stützfunktion von K.
Beispiele 2.3.15
(1) Für K = {x} ist H(K, ·) linear wegen H(K, u) = xu.
(2) Für K = B(0, r) ist H(K, u) = r · kuk.
(3) Sei K das achsenparallele Quadrat im IE 2 mit Mittelpunkt 0 und Kantenlänge 2, {x1 , x2 } die
kanonische Basis des IE 2 . Dann ist
H(K, x1 ) = H(K, x2 ) = 1,
H(K, λ1 x1 + λ2 x2 ) = |λ1 | + |λ2 |.
b d kompakt, K 6= ∅, u ∈ IE d , u 6= 0, dann ist
Bemerkung 2.3.16 Ist K ∈ K
H = {x ∈ IE d ; ux = H(K, u)}
Stützhyperebene von K.
Für die Vereinigung endlich vieler kompakter Körper gilt
b d nichtleer und kompakt, 1 ≤ i ≤ n, und K := conv
Satz 2.3.17 Seien Ki ∈ K
für alle u ∈ IE d
n
[
i=1
Ki
!
. Dann gilt
H(K, u) = max{H(Ki , u); 1 ≤ i ≤ n}.
Zwischen reellwertigen Funktionen mit einem bestimmten Krümmungsverhalten und konvexen Mengen
gibt es Beziehungen:
Definition 2.3.18 Sei K ∈ Kd nicht leer.
(a) Eine Funktion f : K → IR. heißt
(i) konvex, falls für alle u, v ∈ K und 0 ≤ λ ≤ 1 gilt
f (λu + (1 − λ)v) ≤ λf (u) + (1 − λ)f (v),
2. Grundlagen
17
(ii) konkav, falls für alle u, v ∈ K und 0 ≤ λ ≤ 1 gilt
f (λu + (1 − λ)v) ≥ λf (u) + (1 − λ)f (v).
(b) Eine Funktion f : IE d → IR heißt positiv linear homogen, wenn für alle λ ∈ IR, λ ≥ 0, u ∈ IE d
gilt
f (λu) = λf (u).
Beispiele 2.3.19
(1) Jede lineare Abbildung f : IE d → IR ist positiv linear homogen, konvex und konkav.
(2) f : IR → IR mit f (x) = x2 ist konvex.
(3) Sei x0 ∈ IE d . f : IE d → IR mit f (x) := kx − x0 k ist konvex.
Für konvexe Funktionen gilt
Satz 2.3.20 Sei K ∈ Kd , f : K → IR konvex.
(a) Für alle xi ∈ K, λi ∈ IR mit λi ≥ 0, 1 ≤ i ≤ n und
n
n
X
X
f(
λ1 xi ) ≤
λi f (xi ).
i=1
n
X
λi = 1 gilt
i=1
(Jensensche Ungleichung)
i=1
(b) Ist K offen, dann ist f stetig.
Die wichtigsten Eigenschaften der Stützfunktion gibt
b d ein nichtleerer konvexer Körper. Dann gilt
Satz 2.3.21 Sei K ∈ K
(a) H(K, ·) ist positiv linear homogen.
(b) H(K, ·) ist konvex.
Bemerkung 2.3.22 Im nächsten Abschnitt zeigen wir die die Umkehrung: Zu jeder konvexen, positiv
linear homogenen Funktion f gibt es einen konvexen Körper K mit f = H(K, ·).
2. Grundlagen
2.4
18
Unbeschränkte konvexe Mengen
Beispiel 2.4.1 Die Menge
K := {(x, y); y ≥
1
, x > 0}
x
ist eine unbeschränkte konvexe Menge im IE 2 . Für jeden Punkt x ∈ K gibt es einen Strahl mit
Anfangspunkt x, der ganz in K liegt. Die Vereinigung Kx der Strahlen mit Anfangspunkt x, die in K
liegen, ist ein Translat des 1. Quadranten, denn es gilt
Kx = x + {(x, y); x, y ≥ 0}.
Allgemein gilt
Satz 2.4.2 Sei K konvex, abgeschlossen und unbeschränkt. Dann gilt:
(a) K enthält (mindestens) eine Halbgerade L+ .
(b) Ist L+ eine solche Halbgerade mit Anfangspunkt x und ist
+
L+
0 := L − x
die bei 0 beginnende zu L+ parallele Halbgerade, dann gilt für beliebiges y ∈ K
L+
0 + y ⊂ K.
Die Aussage läßt sich auf das relative Innere einer unbeschränkten konvexen Menge übertragen:
Korollar 2.4.2.1 Sei K konvex und unbeschränkt. Dann gilt:
(a) relint K enthält (mindestens) eine Halbgerade L+ .
(b) Ist L+ eine solche Halbgerade mit Anfangspunkt x und ist
+
L+
0 := L − x
die bei 0 beginnende zu L+ parallele Halbgerade, dann gilt für beliebiges y ∈ relint K
L+
0 + y ⊂ relint K.
Konvexe Mengen, die Vereinigung von Strahlen mit demselben Anfangspunkt sind, haben in der
Konvexgeometrie eine besondere Bedeutung:
Definition 2.4.3 Sei X ⊂ IE d eine nichtleere Menge.
(a) Gilt λx ∈ M für alle x ∈ M , λ ≥ 0, dann heißt M Kegel.
(b) Ist M konvex und ein Kegel, dann heißt M konvexer Kegel.
Wir bezeichnen im folgenden die Familie der konvexen Kegel im IE d mit C d .
2. Grundlagen
19
Beispiele 2.4.4 Jeder lineare Unterraum, jeder Strahl mit Anfangspunkt 0, jeder abgeschlossene
Halbraum
H + = {x ∈ IE d ; x · n ≥ 0}
mit Randpunkt 0 und der Orthant“
”
{ξ1 , . . . , ξd ; ξi ≥ 0, 1 ≤ i ≤ d}
ist ein konvexer Kegel.
Bemerkungen 2.4.5
(1) Kegel müssen nicht konvex sein wie man am Beispiel
{(x, y); x · y ≥ 0} ⊂ IE 2
erkennt.
(2) Die hier definierten (konvexen) Kegel enthalten alle den Nullpunkt als ausgezeichneten Punkt,
als Spitze. Allgemeiner kann man auch (konvexe) Kegel mit beliebiger Spitze a ∈ IE d betrachten.
Analog zu den linearen bzw. affinen Unterräumen bzw. den konvexen Mengen sind die konvexen Kegel
die Mengen, die gegenüber der Bildung spezieller Linearkombinationen abgeschlossen sind:
Satz 2.4.6 Eine nichtleere Menge M ⊂ IE d ist ein konvexer Kegel genau dann, wenn für alle x, y ∈ M
und λ, µ ≥ 0 gilt
λx + µy ∈ M.
Bemerkungen 2.4.7
(1) Der Durchschnitt beliebig vieler konvexer Kegel ist die leere Menge oder wieder ein konvexer
Kegel.
(2) Die Vereinigung beliebig vieler Kegel ist ein Kegel, aber die Vereinigung zweier konvexer Kegel
i.a. kein konvexer Kegel.
(3) Ist K ∈ C d ein konvexer Kegel, H eine Stützhyperebene von K, dann gilt 0 ∈ H.
Analog zur linearen, affinen bzw. konvexen Hülle definieren wir
Definition 2.4.8 Sei M ⊂ IE d .
Der Durchschnitt aller konvexen Kegel C von IE d mit M ⊂ C heißt positive Hülle von M .
Bezeichnung: pos M .
Bemerkungen 2.4.9
(1) Wegen Bemerkung 2.4.7 (1) ist pos M für jede Menge M ⊂ IE d ein konvexer Kegel.
2. Grundlagen
20
(2) Analog zu lin M , aff M und conv M gilt für M 6= ∅
pos M = {x; x =
n
X
i=1
λi xi , n ∈ IN, xi ∈ M, λi ≥ 0, 1 ≤ i ≤ n}.
(3) M ist ein konvexer Kegel genau dann, wenn
pos M = M .
Beispiele 2.4.10
(1) Für M = ∅ ist pos M = {0}.
(2) Für die kanonische Basis M = {x1 , x2 , x3 } ⊂ IE 3 ist pos M der 1.Oktant.
Im Beispiel 2.4.1 war die Vereinigung aller Strahlen in K mit demselben Anfangspunkt ein Translat
des 1. Quadranten. Das führt zu
Definition 2.4.11 Sei K ⊂ IE d eine nichtleere konvexe Menge.
C(K) := {y ∈ IE d \ {0}; K + λy ⊂ K für alle λ ≥ 0} ∪ {0}
heißt charakteristischer Kegel von K.
Beispiele 2.4.12
(1) Im Beispiel 2.4.1 ist C(K) der 1. Quadrant.
(2) Ist U ein nichtleerer affiner Unterraum, dann ist C(U ) = U0 der zugehörige lineare Unterraum.
(3) Für K = {(x, y); x, y > 0} ∪ {0}
nicht abgeschlossen sein.
ist
C(K) = K, der charakteristische Kegel muß also
(4) Aus Satz 2.4.2 folgt: Eine nichtleere abgeschlossene konvexe Menge K ist beschränkt genau dann,
wenn C(K) = {0}.
Wir haben noch nicht gezeigt, daß ein charakteristischer Kegel wirklich ein Kegel ist. Es gilt
Satz 2.4.13 Ist K eine nichtleere konvexe Menge, dann ist C(K) ein konvexer Kegel. Ist K zusätzlich
abgeschlossen, dann auch C(K).
Wir zeigen nun die Umkehrung von Satz 2.3.21:
Satz 2.4.14 Zu jeder konvexen, positiv linear homogenen Funktion f : IE d → IR gibt es einen konvexen
Körper K mit
H(K, x) = f (x)
für alle x ∈ IE d .
2. Grundlagen
2.5
21
Die Seitenstruktur einer konvexen Menge
Ein Würfel im IE 3 hat 6 (2-dimensionale) Seiten, 12 Kanten und 8 Ecken. Für die Verallgemeinerung
auf konvexe Mengen im IE d bezeichnen wir alle diese Gebilde als Seiten.
Es gibt verschiedene Möglichkeiten, Seiten zu charakterisieren. Wir verallgemeinern die Tatsache, daß
eine Strecke, die einerseits ganz in der konvexen Menge und andererseits mit mindestens 1 inneren
Punkt in einer Seite liegt, auch ganz in der Seite liegt.
Definition 2.5.1 Seien K und B ⊂ K konvexe Mengen.
(a) Folgt für jedes z ∈ B, der innerer Punkt einer Strecke in K ist, ( d.h. es gibt x, y ∈ K und
λ ∈ (0, 1) mit z = λx + (1 − λ)y,) dass dann x, y ∈ B, dann heißt B Seite von K.
(b) Ist B eine Seite mit dim B = j, dann heißt B j-Seite. Eine 0-Seite heißt extremaler Punkt.
(c) Die (−1)-Seite ∅ und die (dim K)-Seite K heißen uneigentliche Seiten, die anderen Seiten von
K eigentliche Seiten.
(d) Die 1-Seiten von K, die Halbgeraden sind, heißen extremale Halbgeraden, ihre Richtungen,
d.h. die Translate mit Anfangspunkt 0, extremale Richtungen.
Beispiele 2.5.2
(1) Ein Tetraeder im IE 3 hat als eigentliche Seiten 4 2-Seiten, 6 1-Seiten und 4 0-Seiten.
(2) Die konvexe Menge
K := {(x, y) ∈ IE 2 ; x ≥ 0, −x + y + 1 ≥ 0, x + 3y − 1 ≥ 0, 3x + y − 1 ≥ 0}
hat die extremalen Punkte
x1 = (0, 1),
1 1
x2 = ( , ),
4 4
x3 = (1, 0)
und die extremalen Halbgeraden
{(0, 1 + λ); λ ≥ 0},
{(1 + λ, λ); λ ≥ 0}.
Entfernt man z.B. von einem Würfel im IE 3 eine Seite B, dann ist der Rest immer noch konvex.
Außerdem ist B gerade der Durchschnitt des Würfels mit der affinen Hülle von B.
Allgemein gilt
Satz 2.5.3 Seien K und B ⊂ K konvexe Mengen. Dann gilt:
(a) B ist Seite von K genau dann, wenn K \ B konvex ist und B = (aff B) ∩ K.
(b) x ∈ K ist extremaler Punkt von K genau dann, wenn K \ {x} konvex.
2. Grundlagen
22
Bemerkung 2.5.4 Jede der beiden Bedingungen von Satz 2.5.3 (a) ist notwendig.
Satz 2.5.5 (a) Jede Seite einer konvexen Menge ist konvex und jede Seite einer abgeschlossenen
konvexen Menge ist abgeschlossen.
(b) Ist M ⊂ IE d eine nichtleere Menge, K := conv M , dann liegt jeder extremale Punkt von K in
M.
Der Durchschnitt von 2 Seitenflächen eines Würfels im IE 3 ist leer oder eine Kante, also eine 1-Seite,
und der Durchschnitt von 3 Seitenflächen ist leer oder eine Ecke, also ein extremaler Punkt. Weiter
ist die Kante wiederum Seite jeder der beiden Seitenflächen und die Ecke Seite der 3 Seitenflächen.
Allgemein gilt
Satz 2.5.6 Sei K eine konvexe Menge.
(a) Der Durchschnitt einer beliebigen nichtleeren Familie von Seiten von K ist eine Seite von K.
(b) Ist B eine Seite von K, C eine Seite von B, dann ist C eine Seite von K.
(c) Der Durchschnitt von K mit einer beliebigen Stützhyperebene von K ist eine Seite von K. Eine
solche Seite von K heißt exponierte Seite von K.
Die Bedingung für eine Seite aus Definition 2.5.1 kann man verschärfen:
Satz 2.5.7 Seien K eine konvexe Menge mit Seite B und sei C ⊂ K. Dann gilt:
relint C ∩ B 6= ∅
=⇒
C ⊂ B.
Korollar 2.5.7.1 Sei K eine konvexe Menge.
(a) Sind B und C Seiten von K mit relint B ∩ relint C 6= ∅, dann ist B = C.
(b) Ist B 6= K eine Seite von K, dann gilt
dim B < dim K.
(c) Der Durchschnitt D einer beliebigen Familie von Seiten von K kann als Durchschnitt von d + 1
oder weniger Mitgliedern der Familie dargestellt werden.
Jedem Punkt eines Würfels im IE 3 kann man eine kleinste Seite zuordnen, in der der Punkt enthalten
ist: Für eine Ecke ist es die Ecke selbst, für einen relativ inneren Punkt einer Kante ist es die Kante,
für einen relativ inneren Punkt einer Seitenfläche ist es die Seitenfläche und für einen inneren Punkt
ist es K.
2. Grundlagen
23
Das führt zu
Definition 2.5.8 Für eine konvexe Menge K und x ∈ K sei
\
Fx :=
B.
x∈B⊂K, B Seite
Satz 2.5.9 Sei K eine konvexe Menge, x ∈ K beliebig. Dann gilt:
(a) x ∈ relint Fx .
(b) Die relativen Inneren aller Seiten von K bilden eine Zerlegung von K.
(c) Für x ∈ relbd K ist dim Fx < dim K.
Als nächstes untersuchen wir, wann eine abgeschlossene konvexe Menge als konvexe Hülle ihres (relativen) Randes dargestellt werden kann. Die einzigen nichtleeren abgeschlossenen konvexen Mengen
im IE 2 , für die das nicht geht, sind die Mengen, die aus einem Punkt bestehen, die Geraden, die
Halbgeraden, die Ebenen und die Halbebenen.
Definition 2.5.10 Eine nichtleere abgeschlossene konvexe Menge K heißt primitiv, wenn
K 6= conv (relbd K).
Die Situation für primitive Mengen im IE 2 gilt analog für beliebiges d:
Satz 2.5.11 Eine abgeschlossene konvexe Menge ist primitiv genau dann, wenn sie ein affiner Unterraum oder Durchschnitt eines affinen Unterraums mit einem Halbraum ist.
Als konvexes Erzeugendensystem reicht die Vereinigung der primitiven Seiten aus:
Satz 2.5.12 Sei K eine abgeschlossene konvexe Menge. Dann gilt:
(a) K ist die konvexe Hülle der Vereinigung seiner primitiven Seiten.
(b) K ist konvexe Hülle aller Seiten von K, die affine Unterräume oder Durchschnitt eines affinen
Unterraums mit einem Halbraum sind.
(c) Enthält K keine Geraden, dann ist K konvexe Hülle der Vereinigung seiner extremalen Punkte
und extremalen Halbgeraden.
(d) (Krein-Milman) Ist K beschränkt (also kompakt), dann ist K konvexe Hülle der Vereinigung
seiner extremalen Punkte.
2. Grundlagen
24
Bemerkung 2.5.13 Nach Satz 2.5.12 (d) ist die konvexe Hülle der Menge E der extremalen Punkte
einer kompakten konvexen Menge K abgeschlossen (nämlich K). Für dim K ≤ 2 ist auch die Menge
E selbst abgeschlossen. Für dim K ≥ 3 muß das aber nicht gelten: Sei
A := {(x, y, 0) ∈ IE 3 ; x2 + y 2 ≤ 1},
B := {(1, 0, z); −1 ≤ z ≤ 1},
C := conv (A ∪ B).
Dann ist
E = {(1, 0, −1), (1, 0, 1)} ∪ relbd A \ {(1, 0, 0)},
d.h. E ist nicht abgeschlossen.
In Satz 2.5.6 wurden die exponierten Seiten einer konvexen Menge K als Durchschnitt von K mit
einer Stützhyperebene von K definiert. Man bezeichnet ∅ und K auch als (uneigentliche) exponierte
Seiten.
Beispiel 2.5.14 Nicht jede Seite einer konvexen Menge ist exponierte Seite, wie man an der konvexen
Hülle von zwei Kreisen mit verschiedenen Mittelpunkten und gleichem Radius sieht:
✻
s
s
✲
s
Die hervorgehobenen Punkte sind 0Seiten, also extremale Punkte, aber keine
exponierten Seiten.
s
Satz 2.5.15 Seien K, K ′ konvexe Mengen. Dann gilt:
(a) Der Durchschnitt einer nichtleeren Familie von exponierten Seiten von K ist eine exponierte
Seite.
(b) Jede exponierte Seite von K + K ′ läßt sich als Summe einer exponierten Seite von K und einer
exponierten Seite von K ′ darstellen.
Für kompakte konvexe Mengen gilt
Satz 2.5.16 Sei K eine nichtleere kompakte konvexe Menge. Dann gilt:
(a) Für jedes y ∈ IE d gibt es einen fernsten Punkt z ∈ K, d.h. es gilt
kz − yk = max{kx − yk; x ∈ K}.
z ist ein exponierter Punkt von K.
(b) Jeder offene Halbraum H − mit H − ∩ K 6= ∅ enthält einen exponierten Punkt von K.
(c) K ist die abgeschlossene Hülle der konvexen Hülle der Vereinigung seiner exponierten Punkte.
2. Grundlagen
2.6
25
Dualität und Polarität
Beispiele 2.6.1
(1) Für eine abgeschlossene konvexe Menge gibt es einerseits eine innere Darstellung“ als Verei”
nigung ihrer Punkte (bzw. als Menge der Konvexkombinationen einer Teilmenge), andererseits
nach Satz 2.3.9 eine äußere Darstellung“ als Durchschnitt aller abgeschlossenen Halbräume, die
”
die Menge enthalten.
(2) Sei V ein m-dimensionaler reeller Vektorraum. Die Linearformen, d.h. die linearen Abbildungen
f : V → IR, bilden einen m-dimensionalen Vektorraum V ∗ , den Dualraum“ von V , der isomorph
”
zu V ist. Zu jeder Basis B = {x1 , . . . , xm } von V gibt es eine Basis B ∗ = {f1 , . . . , fm } von V ∗
mit fi (xj ) = δij . Und zu jedem linearen Unterraum U von V ist
U ∗ := {f ∈ V ∗ ; f (x) = 0 für alle x ∈ U }
ein linearer Unterraum von V ∗ mit dim U ∗ = m − dim U , der zu U orthogonale“ Raum. Das
”
gibt die Möglichkeit, auch in Vektorräumen ohne Skalarprodukt etwas entsprechendes wie das
orthogonale Komplement zu definieren.
Der Menge der (m − 1)-dimensionalen linearen Unterräumen von V kann man damit die Menge
der 1-dimensionalen linearen Unterräume von V ∗ zuordnen. Bei Räumen mit Skalarprodukt ist
diese isomorph zu der Menge der Untervektorräume, die jeweils von den Normalenvektoren der
Hyperebenen durch 0 erzeugt werden.
(3) Die konvexe Hülle der Seitenmittelpunkte eines Würfels im IE 3 (mit 8 Ecken, 12 Kanten und 6
2-Seiten) ist ein Oktaeder, d.h. ein regelmäßiges Polytop mit 8 2-Seiten, 12 Kanten und 6 Ecken.
Einer Würfelecke entspricht umkehrbar eindeutig eine der Oktaeder-2-Seiten, einer Würfelkante
eine Oktaederkante und einer Würfel-2-Seite eine Oktaederecke. Umgekehrt erhält man als konvexe Hülle der Seitenmittelpunkte eines Oktaeders einen Würfel. Man nennt Würfel und Oktaeder
zueinander dual.
Auf Grund der vorherigen Beispiele liegt es nahe, nach einer Beziehung zwischen Punkten (bzw.
Ortsvektoren) im IE d und den abgeschlossenen Halbräumen (bzw. Normalenvektoren) zu suchen.
Definition 2.6.2 Für beliebige u ∈ IE d , M ⊂ IE d sei
(a) u∗ := {x ∈ IE d ; u · x ≤ 1},
\
(b) M ∗ := {u∗ ; u ∈ M } = {x ∈ IE d ; u · x ≤ 1 für alle u ∈ M }.
(c) M ∗∗ := (M ∗ )∗ .
M ∗ heißt die zu M polare Menge.
Bemerkungen und Beispiele 2.6.3
(1) Es gilt
0∗ = IE d ,
∅∗ = {0}∗ = IE d und
(IE d )∗ = {0}.
2. Grundlagen
26
(2) Für jedes u 6= 0 ist u∗ ein abgeschlossener Halbraum mit innerem Punkt 0.
Umgekehrt gibt es zu jedem abgeschlossenen Halbraum H − mit innerem Punkt 0 ein eindeutig
bestimmtes u ∈ IE d \ {0} mit H − = u∗ .
Es gibt also eine bijektive Abbildung zwischen IE d \ {0} und der Menge der abgeschlossenen
Halbräume des IE d , die 0 als inneren Punkt enthalten.
(3) Sei u ∈ IE d \ {0} und H = {x ∈ IE d ; u · x = 1} die Hyperebene mit zugehörigem Halbraum
u
∈ H, d.h. H hat vom Nullpunkt
H − = u∗ . Dann ist u Normalenvektor von H und u′ :=
kuk2
1
den Abstand
.
kuk
Folgende Zeichnung beschreibt für den IE 2 die Fälle kuk < 1, kuk = 1 und kuk > 1:
H
su′
q
H
H−
H−
H
su
H−
u = u′ qs
su
H
s ′
qu
s0
−
s0
s0
H−
H−
kuk < 1
kuk = 1
(4) Für die abgeschlossene Einheitskugel gilt
(5) Die zum Würfel
kuk > 1
∗
B[0; 1] = B[0; 1].
W := {u = (η1 , . . . , ηd ) ∈ IE d ; |ηi | ≤ 1, 1 ≤ i ≤ d}
polare Menge ist das Kreuzpolytop
∗
d
W = {x = (ξ1 , . . . , ξd ) ∈ IE ;
und es gilt
W ∗∗ = W
d
X
i=1
|ξi | ≤ 1}
wie im Beispiel 2.6.1 (3).
Die Bildung der polaren Menge dreht Inklusion, Durchschnittsbildung und Skalarmultiplikation um:
Satz 2.6.4 Seien A, B ⊂ IE d Mengen, λ ∈ IR \ {0}. Dann gilt
(a) Aus A ⊂ B folgt B ∗ ⊂ A∗ .
∗
(b) A ∪ B = A∗ ∩ B ∗ .
∗
1
(c) λ · A = · A∗ .
λ
(d) A∗∗ = cl conv A ∪ {0} .
Ist A abgeschlossen und konvex mit 0 ∈ A, dann gilt A∗∗ = A.
2. Grundlagen
27
Beschränkt man sich auf die Betrachtung von abgeschlossenen konvexen Mengen, die den Nullpunkt
enthalten, dann folgt
Satz 2.6.5 Sei K eine abgeschlossene konvexe Menge mit 0 ∈ K. Dann gilt:
(a) K ist beschränkt genau dann, wenn 0 innerer Punkt von K ∗ ist.
(b) K ∗ ist beschränkt genau dann, wenn 0 innerer Punkt von K ist.
Korollar 2.6.5.1 Ist K die Menge der konvexen Körper im IE d , die 0 als inneren Punkt enthalten.
Dann wird durch
F :K→K
mit F (K) := K ∗
eine bijektive Abbildung definiert.
Der nächste Satz verallgemeinert die Beziehung zwischen den Seiten des Würfels und des Oktaeders
aus Beispiel 2.6.1 (3):
Satz 2.6.6 Sei K ein konvexer Körper mit 0 ∈ int K. Dann gilt:
(a) Ist A ⊂ K eine exponierte Seite von K, dann ist
φK (A) := {u ∈ K ∗ ; x · u = 1 für alle x ∈ A}
eine exponierte Seite von K ∗ .
(b) Setzt man φK (∅) := K ∗ , dann ist φK eine bijektive und inklusionsumkehrende Abbildung der
Menge der exponierten Seiten von K auf die Menge der exponierten Seiten von K ∗ .
Beispiel 2.6.7 Wir ordnen den Seiten eines achsenparallelen Quadrats Q die entsprechenden Seiten
des zugehörigen Kreuzpolytops Q∗ zu:
Kreuzpolytop Q∗
Quadrat Q
✻
D
✻
X
C
Y
✲
A
W
✲
Z
B
Für die Abbildung φ ergibt sich folgende Wertetabelle:
φ
∅
Q∗
{A} {B}
YZ
{C}
WZ WX
{D}
XY
AB
BC
CD
AD
Q
{Z} {W } {X} {Y }
∅
28
3
3.1
Polytope
Polyeder
Polytope in der Ebene und im Raum standen neben Kreis und Kugel schon während der griechischen
Antike im Mittelpunkt des mathematischen (und philosophischen) Interesses. Durch ihre spezielle
Seitenstruktur kann man relativ einfach Volumen und Oberfläche berechnen, man kann durch Polytope
beliebige konvexe Körper approximieren und sie spielen in anderen Bereichen wie Linearer Optimierung
oder Spieltheorie eine wichtige Rolle.
Im folgenden werden wir die üblichen Bezeichnungen Ecke für eine 0-Seite, Kante für eine 1-Seite
und Facette für eine (dim K − 1)-Seite einer konvexen Menge K verwenden. Weiter bezeichnen wir
mit vert K die Eckenmenge der konvexen Menge K.
Anschaulich lassen sich die bekannten Polytope im IE 2 und IE 3 auch als Durchschnitte von endlich
vielen Halbräumen darstellen. Deshalb betrachten wir in diesem Abschnitt zuerst solche Mengen:
Definition 3.1.1 Der Durchschnitt endlich vieler abgeschlossener Halbräume heißt Polyeder. Speziell betrachten wir ∅ und IE d als Polyeder.
Bemerkungen 3.1.2
(1) Die Lösungsmenge von endlich vielen linearen Ungleichungen mit d Unbekannten ist ein Polyeder
im IE d .
(2) Ein Polyeder ist abgeschlossen und konvex, aber i.a. nicht beschränkt.
(3) Endliche Durchschnitte von Polyedern sind wieder Polyeder.
Beispiele 3.1.3
(1) Jede Hyperebene H, jeder Halbraum H − und jeder affine Unterraum von IE d ist ein Polyeder.
(2) Ist {e1 , . . . , ed } die kanonische Basis des IE d , dann sind
P1 := {(ξ1 , . . . , ξd ); ξi ≥ 0},
P2 := {(ξ1 , ..., ξd ); ξi ≥ 0,
d
X
i=1
ξi ≤ 1},
P3 := {x; −1 ≤ xei ≤ 1}
Polyeder.
Der nächste Satz beschreibt, wie man die Facetten eines Polyeders erhält und wie diese die Seitenstruktur des Polyeders festlegen:
3. Polytope
29
Satz 3.1.4 Sei n ∈ IN, Hi := {x ∈ IE d ; ai · x ≤ αi }, 1 ≤ i ≤ n, Hyperebenen im IE d , K ein Polyeder
mit
n
\
K :=
Hi− ∩ (aff K)
i=1
und Fi := K ∩ Hi , 1 ≤ i ≤ n. Weiter sei K weder ein affiner Unterraum noch kann man bei der
Durchschnittsbildung einen der Halbräume weglassen. Dann gilt
(a) relint K = {x ∈ K; ai · x < αi , 1 ≤ i ≤ n}.
(b) relbd K =
n
[
Fi .
i=1
(c) F1 , . . . , Fn sind Facetten von K und es gibt keine weitere.
\
(d) Für jede eigentliche Seite A von K gilt A =
Fi .
A⊂Fi
(e) K hat eine endliche Anzahl von Seiten, und jede eigentliche ist exponiert.
(f ) Jede Seite von K ist ein Polyeder.
(g) Ist Aj eine j-Seite von K, Ak eine k-Seite von K mit 0 ≤ j ≤ k − 2 und Aj ⊂ Ak , dann gibt es
Seiten Aj+1 , . . . , Ak−1 von K, so daß Ai Facette von Ai+1 , j ≤ i ≤ k − 1.
Allgemein folgt
Satz 3.1.5 Sei K ein Polyeder. Dann gilt:
(a) K hat nur endlich viele Seiten und jede der eigentlichen Seiten ist exponiert und wieder ein
Polyeder.
(b) Jede eigentliche Seite ist Durchschnitt aller Facetten von K, die die Seite enthalten.
(c) relbd K ist die Vereinigung aller Facetten (in aff K).
(d) F1 , . . . , Fn sind Facetten von K und es gibt keine weitere.
(e) Hat K eine nichtleere j-Seite, dann hat K auch k-Seiten für jedes k mit j ≤ k ≤ dim K.
Der nächste Satz gibt ein Kriterium dafür, wann eine beliebige konvexe Menge ein Polyeder ist.
Satz 3.1.6 Sei K eine abgeschlossene konvexe Menge.
(a) Hat K nur endlich viele exponierte Seiten, dann ist K ein Polyeder.
(b) Hat K nur endlich viele Seiten, dann ist K ein Polyeder.