next up previous contents
Nächste Seite: Approximation durch Zonotope Aufwärts: Approximation der Kugel durch Vorherige Seite: Approximierbarkeit konvexer Körper   Inhalt

Projektionskörper, Zonotope

Gegeben sind von einem konvexen Körper nur Maße seiner Projektionen. Was können wir über den Körper selbst aussagen ?



In [6] findet sich zu diesem Problem folgender Zugang:
Es sei K ein konvexer Körper und ${\mathit O}({\mathit K},{\mathcal H})$ sei die Oberfläche der orthogonalen Projektion des Körpers ${\it K}$ auf die Hyperebene ${\mathcal H}$. Ist ${\mathbf u}$ der äußere Einheitsnormalvektor der Hyperebene ${\mathcal H}$ und liegt ${\mathbf u}$ in der Borelmenge der Einheitssphäre $S^{d-1}$, so läßt sich ${\mathit O}({\mathit K},{\mathcal H})$ ausdrücken durch:

\begin{displaymath}
{\mathit O}({\mathit K},{\mathcal H}) =
\frac{1}{2} \cdot ...
...} \vert {\mathbf u} \cdot {\mathbf x}\vert d\mu({\mathbf x}).
\end{displaymath} (3.23)

Dabei ist $\mu$ der (d-1)-dimensionale Inhalt desjenigen Teiles vom Rand von K, der in der Stützebene ${\mathcal H}$ enthalten ist. Ist $\mu$ das Oberflächenmaß, so ist ${\mathit O}({\mathit K},{\mathcal H})$ gemäß (II.5) gleich $2\kappa_{d-1}$.
Haben wir weiters eine Familie ${\mathcal L} = ({\mathcal H}_1,\alpha_1;...;{\mathcal H}_n,\alpha_n)$ von n Hyperebenen des ${\rm I\mkern-3mu R}^d$ mit zugeordneten Gewichten $\alpha_i$ gegeben, so können wir die Oberfläche von ${\mathit O}({\mathit K})$ abschätzen durch die Summe
\begin{displaymath}
{\mathit O}({\mathit K},{\mathcal L}) =
\sum \alpha_i \cdot {\mathit O}({\mathit K},{\mathcal H}_i )
\end{displaymath} (3.24)

Die Abschätzung wird klarerweise umso besser, je ''gleichmäßiger'' die Einheitsnormalvektoren der Hyperebenen als Vektoren auf der $S^{d-1}$ verteilt sind. Daraus resultiert die Frage, wie sich für eine gute Wahl der Einheitsvektoren der Quotient ${\mathit O}({\mathit K},{\mathcal L})/{\mathit O}({\mathit K})$ verhält.
Da jede Hyperebene zwei Normalvektoren $\pm {\mathbf u}_i$ besitzt, können wir ${\mathit O}({\mathit K},{\mathcal L})$ darstellen durch:
\begin{displaymath}
{\mathit O}({\mathit K},{\mathcal L}) =
\sum \alpha_i {\m...
... {\mathbf u}_i \cdot {\mathbf x} \vert ) d\omega({\mathbf x})
\end{displaymath} (3.25)

Hier steht unter dem Integral die Stützfunktion eines Zonotops:
\begin{displaymath}
{\mathit h}(Z({\mathcal L}),{\mathbf x}) = \sum \alpha_i \cdot \vert {\mathbf u}_i \cdot {\mathbf x}\vert
\end{displaymath} (3.26)

Ein Zonotop ist die Minkowski-Summe von endlich vielen Strecken mit inneren Punkten [32,61]. Betrachtet man die Minkowski-Summe (III.1) genauer, so erkennt man, daß man jedes Zonotop des ${\rm I\mkern-3mu R}^d$, das von n Strecken aufgespannt wird, als Projektion eines n-dimensionalen Parallelotops auf den ${\rm I\mkern-3mu R}^d$ auffassen kann. Umgekehrt kann man jedes Zonotop in ${ n \choose d }$ Parallelotope zerlegen. [32].
Weiters ist es klar, daß man o.B.d.A. annehmen kann, daß die erzeugenden Linienelemente alle ihren Mittelpunkt im Ursprung haben. Diese erzeugenden Linienelemente bilden den Generator [gen Z] des Zonotopes.
[Im obenstehenden Zonotop ist der Generator gleich der Menge der gewichteten Einheitsnormalvektoren, die wir hier als Strecken auffassen.]
Ist $gen Z = \{{\mathbf x}_1,..,{\mathbf x}_n\}$ mit ${\mathbf x}_i^1 = (x_i^d,..,x_i^d) \in {\rm I\mkern-3mu R}^d$ der Generator von Z, und bezeichnet $[{\mathbf x}_i] = conv\{-{\mathbf x}_i/2,{\mathbf x}_i/2\}$, so kann man das Zonotop Z darstellen als $Z = [{\mathbf x}_1]+...+[{\mathbf x}_n]$.
Daher hat jeder Punkt des Zonotopes Z die Darstellung
$P = \theta_1 \cdot {\mathbf x}_1 /2 +...+ \theta_n \cdot {\mathbf x}_n / 2$ mit $\vert \theta_i \vert \leq 1$ und ${\mathbf x}_i \in gen Z$
Für die Ecken gilt Gleichheit.
Analogerweise [32] besitzt jede Zonotopseite die Darstellung:

\begin{displaymath}
{\mathcal F}= [{\mathbf x}_{\sigma (1)} ] +..+ [{\mathbf x}...
...gma (r+1)} /2 +..+ (\pm 1) \cdot {\mathbf x}_{\sigma (n)} /2,
\end{displaymath}

und ist daher wiederum ein Zonotop. [Mit $\sigma$ wurde eine Permutation von (1..n) bezeichnet].
Mit Hilfe dieser Darstellungsmöglichkeit der Seitenflächen kann man auch den Namen dieser Polytopklasse erklären. In der obigen Darstellung ist ja noch offen, wie das Vorzeichen von ${\mathbf x}_{\sigma (r+1)} $ bis ${\mathbf x}_{\sigma (n)}$ zu wählen ist. Dies geschieht folgendermaßen:


Ist ${\mathbf u}$ der äußere Normalvektor der Trägerhyperebene von ${\mathcal F}$, so ist das Vorzeichen von ${\mathbf x}_{\sigma (i)}$ so zu wählen, daß ${\mathbf x}_{\sigma (i)}$ und ${\mathbf u}$ auf derselben Seite der Trägerhyperebene liegen. Da die Normalvektoren der Seiten, die eine Verschiebung des Generatorelementes ${\mathbf x}_i$ enthalten, orthogonal auf ${\mathbf x}_i$ stehen, formen sie einen ''Ring'' um ${\mathbf x}_i$ und bilden eine ''Zone'' von Z.
Aus der Darstellung eines Punktes sieht man, daß die Stützfunktion eines Zonotopes die folgende Gestalt hat [32,74]:
\begin{displaymath}
{\mathit h}(Z,{\mathbf u}) = \sum {\mathbf x}_i \cdot {\mathbf u}
\end{displaymath} (3.27)

Denn eine Strecke $\pm\alpha \cdot {\mathbf u}$ mit ${\mathbf u} \in S^{d-1}$ und $\alpha \in {\rm I\mkern-3mu R}$ besitzt die Stützfunktion $\alpha \cdot \vert {\mathbf u} \cdot {\mathbf x}\vert $.
Es sei nun $Z({\mathcal L})$ das Zonotop mit Stützfunktion ${\mathit h}$ aus (4). Wir beachten, daß aufgrund ihrer Darstellung die Funktion ${\mathit h}(Z({\mathcal L}),\cdot)$ an nur endlich vielen Stellen ihr Maximum annehmen kann. Diese Maximumsstellen weisen in Richtungen gewisser Zonotopecken.
Setzen wir $\dim Z({\mathcal L}) = d$ voraus, so wird umgekehrt ${\mathit h}(Z({\mathcal L}),\cdot)$ für Normalvektoren gewisser Zonotopseiten minimal. Daraus folgt, daß das Verhältnis ${\mathit O}({\mathit K},Z({\mathcal L}))/
{\mathit O}({\mathit K})$ stets kleiner als der Umkugelradius R und stets größer als der Inkugelradius r des Zonotopes $Z({\mathcal L})$ ausfällt.
Diese Radien können wir durch die Hausdorffmetrik abschätzen: Der Hausdorffabstand $\eta$ ist definiert als die kleinste Zahl, für die gilt: $K_{\eta} \subset L$ und $L_{\eta} \subset K$.
Daher ist die Kugel $B^d_\eta$ mit Radius $(1+\eta)$ eine Umkugel des Zonotopes $Z({\mathcal L})$ und umgekehrt ist $B^d_{-\eta}$, eine Kugel, die den Radius $1-\eta$ besitzt, eine Inkugel von $Z({\mathcal L})$, da Z die Kugel $B^d_\eta$ umfassen muß. Daher ist
\begin{displaymath}
R \leq \eta+1 \quad \mathtt{und} \quad r \geq 1-\eta
\end{displaymath} (3.28)

Somit ist:

\begin{displaymath}
1-\eta \leq r \leq {\mathit O}({\mathit K},Z({\mathcal L}))/
{\mathit O}({\mathit K}) \leq R \leq 1 + \eta
\end{displaymath}

und :

\begin{displaymath}
-\eta \leq {\mathit O}({\mathit K},Z({\mathcal L}))/
{\mathit O}({\mathit K}) - 1 \leq +\eta
\end{displaymath}


\begin{displaymath}
\vert 1-{\mathit O}({\mathit K}, Z({\mathcal L}))/
{\mathit O}({\mathit K})\vert \leq \eta(B^d,Z({\mathcal L}))
\end{displaymath} (3.29)

Damit haben wir:
\begin{displaymath}
\vert {\mathit O}({\mathit K}) - {\mathit O}({\mathit K},Z...
...q
{\mathit O}({\mathit K}) \cdot \eta(B^d,Z({\mathcal L}))
\end{displaymath} (3.30)

Um also das am Beginn des Paragraphen gestellte Problem lösen zu können, müssen wir die Approximation der Kugel durch Zonotope betrachen. Um dies besser notieren zu können, setzen wir :
$\zeta(n,d) := \inf \{\eta(B^d,Z): $ Z ist ein d-dimensionales Zonotop mit n Generatorelementen $\}$

Weiters benötigen wir noch folgende Definition [10]:
Es sei P ein Polytop und ${\mathit h}({\mathbf u})$ sei stets gleich dem Inhalt der orthogonalen Projektion von P auf eine Hyperebene mit Normalvektor ${\mathbf u}$. Dann heißt das Polytop $\Pi({\mathit P})$, das ${\mathit h}$ als Stützfunktion besitzt, Projektionskörper.
Eine erste Untersuchung des Problemes stammt von Betke und McMullen [6]. Sie erhalten für die Zahl $\zeta$ die Abschätzung
\begin{displaymath}
c_1 \cdot n^{-2} \leq \zeta(n,d) \leq c_2 \cdot n^{-2/(d-1)}
\end{displaymath} (3.31)

Ihr Beweis stützt sich auf die grundlegenden Approximationssätze des zweiten Paragraphen und benützt folgende Tatsache:
Für $\nu = 2/(R+r)$ ist $\eta(B^d,Z_{\nu}) = (R-r)/(R+r) = (1-r/R)/(1-r/R).$
Die Autoren betrachten ein d-dimensionales und n-eckiges Polytop, das von der Kugel den Hausdorffabstand $\gamma_d \cdot n^{-2/(d-1)}$ hat und dessen Existenz laut III.2 gesichert ist. Sie beweisen, daß der Projektionskörper des dualen Polytopes, der stets ein Zonotop ist [6], $\zeta(n,d) \leq (d-1) \cdot \gamma_d \cdot n^{-2/(d-1)}$ besitzt.
Um eine Ungleichung in der anderen Richtung zu erhalten, schätzen sie die Radien r und R ab.
Wir wollen als nächstes untersuchen, wie ''nahe'' - in verschiedener Hinsicht - ein Zonotop der Kugel kommen kann. Auf die ursprüngliche Fragestellung werden wir dann wir im sechsten Paragraphen zurückkommen.


Als erstes sei die Frage gestellt, welches Zonotop die kleinste mittlere Breite besitzt. Zur Vereinfachung setzen wir voraus, daß alle Generatorelemente gleich lang sind. [So ein Zonotop heißt üblicherweise ''gleichseitig''.]
Die mittlere Breite eines konvexen Körpers können wir (III.1) als ''Erwartungswert der Breite'' bezeichnen. Bei Zonotopen ist er bis auf einen konstanten Faktor gleich der Summe der Längen der erzeugenden Strecken.
Es scheint natürlich zu sein, diejenigen Zonotope, die eine kleinstmögliche Varianz der Breite besitzen als regulärßu bezeichnen. Denn der Begriff der Regularität ist nicht analog zu der Definition von (I.2) definierbar, denn es sonst wäre für $d = 3$ der Würfel das einzige reguläre Zonotop.
Diese Definition von ''regulär'' stammt aus [54]. Der Autor beweist, daß dann unter einem ''regulären'' Zonotop ein Zonotop mit gleich langen Generatorelementen ${\mathbf x}_i$ zu verstehen ist, bei dem der Generator einen ''eutaktischen Stern'' bildet, und bei dem die Geraden durch den Ursprung mit Richtungsvektoren ${\mathbf x}_i$ und ${\mathbf x}_j$ für alle ${\mathbf x}_i$ und ${\mathbf x}_j$ aus dem Generator denselben Winkel einschließen.
Eine Menge $\{{\mathbf x}_i,..,{\mathbf x}_n\}$ von Vektoren heißt eutaktischer Stern, wenn in einer (n x d)-Matrix ${\mathbf{\mathit X}}$, deren i-te Zeile gleich ${\mathbf x}_i$ ist, die Spalten paarweise orthogonal sind und gleiche Norm haben.
Man kann jede orthogonale (n x d)-Matrix zu einer Orthonormalbasis des ${\rm I\mkern-3mu R}^n$ erweitern. Die Vektoren dieser Basis spannen dann einen Würfel auf. Da man eine orthogonale Projektion dadurch beschreiben kann, daß man (n-d) Richtungen einfach ''wegläßt'', sind die Zonotope, deren Generator einen eutaktischen Stern bildet, genau die Zonotope, die als orthogonale Projektion eines Würfels dargestellt werden können.


Als nächstes stellt sich die Frage nach Zonotopen mit maximalem Volumen. Dieses ist zum Beispiel dadurch berechenbar, daß Zonotope eine enge Beziehung zur äußeren Algebra haben.
Daraus kann man beweisen [32], daß das Volumen eines Zonotopes Z mit Generator $\{{\mathbf x}_1,..,{\mathbf x}_n\}$ sich anschreiben läßt als:
\begin{displaymath}
V_d(Z)= \sum \vert \det({\mathbf x}_{i_1},...,{\mathbf x}_{i_d} )\vert
\end{displaymath} (3.32)

Dabei ist $1 < i_1 < .. < i_d < n$ ; summiert wird über alle möglichen d-Tupel dieser Art.
In [32] wird weiters bewiesen, daß das größte Zonotop, das als Projektion eines n-dimensionalen Würfels auf den d-dimensionalen Teilraum, der durch die ersten d Koordinatenachsen aufgespannt wird, erhalten werden kann, zugleich das größte d-dimensionale Zonotop ist, für dessen Generator gen Z = $\{{\mathbf x}_1,...,{\mathbf x}_n \}$ gilt : $\sum \parallel {\mathbf x}_i \parallel^2 = d$.


In [32] werden auch noch folgende Abschätzungen angegeben:
Erfüllt ein d-dimensionales Zonotop Z mit n-elementigem Generator die zuletzt genannte Eigenschaft, so ist:
\begin{displaymath}
{\mathit V}(Z) \leq \sqrt{ n \choose d }
\end{displaymath} (3.33)

es gilt sogar:
\begin{displaymath}
{\mathit V}(Z) \leq
\omega_d \cdot (\sqrt{n/d} \cdot \omega_{d-1} / \omega_d )
\end{displaymath} (3.34)

(Die erste Ungleichung läßt sich auch auf innere Volumina erweitern [52]; die zweite ist für $n > const \cdot d^2$ schärfer als die erste und von richtiger Größenordnung.)
Im dreidimensionalen Fall gilt für Zonotope, die aus Würfelprojektionen gewonnen werden die Ungleichung [33]:
\begin{displaymath}
V(Z) \leq \sqrt{\frac{n}{3}} \cdot \cot \frac{\pi}{2\cdot (n-1)}
\end{displaymath} (3.35)

[Diese Abschätzung ist für $n < 15$ besser als die bisherigen.]


Für die Oberfläche und den Inkugelradius gilt im ${\rm I\mkern-3mu R}^3$ [53]:
Sei n = 3,4 oder 6. Unter allen dreidimensionalen Zonotopen, die durch n Einheitsstrecken erzeugt werden, haben die, deren Seitenflächen kongruente Rhomben und deren Eckfiguren kongruente Polygone sind, größte Oberfläche und größten Inkugelradius.
next up previous contents
Nächste Seite: Approximation durch Zonotope Aufwärts: Approximation der Kugel durch Vorherige Seite: Approximierbarkeit konvexer Körper   Inhalt

2004-03-25