Approximation durch Polyeder

Will man den ''Abstand'' zweier konvexer Körper untersuchen, so muß man sich zunächst Gedanken darüber machen, wie dieser Abstand überhaupt gemessen werden kann, denn auf der Menge ${\mathcal K}$ der konvexen Körper gibt es keine ausgezeichnete Metrik.
Die gebräuchlichste Metrik ist die Hausdorffmetrik, die wir stets mit $\eta$ bezeichnen wollen. Sie ist definiert als das Minimum der Zahlen $\rho$, für die gilt: ${\mathit K}_{\rho} \supset {\mathit L}$ und ${\mathit L}_{\rho} \supset {\mathit K}$, wobei wir mit K und L zwei konvexe Körper bezeichnen. Der Hausdorffabstand $\eta({\mathit K},{\mathit L})$ läßt sich auch anschreiben durch:

$$\eta({\mathit K},{\mathit L}) = \max \{ \sup_{{\mathbf x... ... {\mathit K}} \parallel{\mathbf x}-{\mathbf y}\parallel \}$$ (3.9)

Man kann klarerweise nicht nur das Maximum der beiden Zahlen in der Klammer zu betrachten, sondern auch deren Mittel. Diese Mittel führen bei geeigneter Wahl der Gewichtung zu Metriken, die einen engen Bezug zu den $l_p$-Metriken haben [38].
Mehr Verwendung als derartige Metriken findet jedoch die Symmetrische Differenzmetrik, die für zwei konvexe Körper K und L so definiert ist:

$$\delta^S({\mathit K},{\mathit L}) := \lambda({\mathit K}... ...{\mathit L}) + \lambda({\mathit L} \backslash {\mathit K})$$ (3.10)

Dabei bezeichnen wir mit $\lambda$ das Lebesguemaß des umgebenden ${\rm I\mkern-3mu R}^d$. [Im folgenden wollen wir stets die Hausdorffmetrik verwenden, da in dieser Metrik die meisten Ergebnisse vorliegen.]
Wenn wir konvexe Körper durch konvexe Polyeder approximieren wollen, sind folgende Sätze wichtig [40]:

• Ist $\epsilon > 0$ und ist $K \in {\mathcal K}$ ein konvexer Körper, so lassen sich stets zwei konvexe Polyeder P und Q finden, für die gilt:
  

  $$P \subset {\mathit K} \subset {\mathit Q}; \eta(K,P) < \epsilon; \eta(K,Q) < \epsilon.$$ (3.11)

  
  

• Ist $K \in {\mathcal K}$ ein konvexer Körper und ist $\mu > 1$ eine beliebig vorgegebene Zahl, so läßt sich, wenn der Ursprung in geeigneter Weise in K angenommen wird, stets ein konvexes Polyeder P finden, das $P \subset {\mathit K} \subset {\mathit P}_{\mu}$ erfüllt.

Um den ersten Satz zu beweisen, überdecken wir K durch endlich viele Würfel der Kantenlänge $s < \epsilon/\sqrt k$, von denen jeder Punkte mit K gemeinsam habe und die zB. durch ein achsparalleles Raster mit Maschen der Länge s gegeben sind. Es sei Q die konvexe Hülle der Vereinigung dieser Würfel. Dann ist ${\mathit K} \subset {\mathit Q}$ und ${\mathit Q} \subset {\mathit K}_{\sqrt{k} \cdot s} = {\mathit K}_{\epsilon}$, und daher $\eta({\mathit K},{\mathit Q}) < \epsilon$.
Weiters überdecken wir K durch endlich viele Würfel der Kantenlänge $s < 2\epsilon/\sqrt{k}$, deren Mittelpunkte alle zu K gehören sollen. Auch hier wäre an ein Raster denkbar, allerdings sind eventuell Verschiebungen der einen oder anderen Rasterebene nötig, um die erforderlichen Bedingung erfüllen zu können. Nun sei P die konvexe Hülle der Würfelmittelpunkte. Dann ist ${\mathit K} \subset {\mathit P}_{\sqrt{k} \cdot s/2} = {\mathit P_{\epsilon}}$ und ${\mathit P} \subset {\mathit K}$ und damit $\eta({\mathit K},{\mathit P}) < \epsilon$ $\diamondsuit$
Für den Beweis der zweiten Aussage wählen wir den Ursprung ${\mathbf u}$ des umgebenden Raumes im Inneren von K, und zwar so, daß eine Kugel $B(\rho)$ mit Radius $\rho > 0$ um ${\mathbf u}$ ebenfalls noch ganz im Inneren von K liegt. Es sei $\Delta := \inf \{ \vert {\mathbf x},{\mathbf y}\vert : {\mathbf x} \in \partial {\mathit K}; {\mathbf y} \in \partial B(\rho) \}$ der positive Abstand zwischen den Rändern dieser Körper.
Es sei $\epsilon$ mit $\Delta > \epsilon > 0$ und $(\mu-1) \cdot \rho > \epsilon$ gegeben. Wegen $\Delta > \epsilon$ ist $B(\rho) \subset {\mathit K}_{-\epsilon} \subset {\mathit P}$. Es wäre sogar noch eine Parallelkugel mit Abstand $\Delta$ in K enthalten. Allerdings würde $B(\rho)_{\Delta}$ den Körper K in (mindestens) einem Punkt berühren.
Gemäß (3.11) gibt es stets ein Polyeder P mit ${\mathit P} \subset {\mathit K} \subset {\mathit P}_{\epsilon}$. Wird dieses Polyeder um den Faktor $\mu$ gestreckt, so werden die Trägerhyperebenen der Seitenflächen, die einen Abstand $p > \rho$ zum Ursprung haben, um die Länge $(\mu-1) \cdot p > (\mu-1) \cdot \rho > \epsilon$ nach außen verschoben. Daraus folgt: ${\mathit P}_{\mu} \supset {\mathit P}_{\epsilon}$ $\diamondsuit$

Wir betrachten wir nun die Approximation der $B^3$:
Es sei zunächst bemerkt, daß sich (I.3.8) und (I.3.10) in folgende Form bringen lassen [30]:
Ist ein Polyeder mit n Ecken oder n Flächen in eine konzentrische Kugelschale mit Umkugelradius R und Inkugelradius r eingebettet, so gilt mit der Konvention $\gamma_n = \frac{n}{n-2} \cdot \frac{\pi}{6}$:

$$\frac{R}{r} \geq \sqrt{3} \cdot \tan \gamma_n$$ (3.12)

Denn jede Überdeckung definiert ein Polyeder:

Man betrachte den Schnitt der Halbräume, die durch die Trägerhyperebenen der Kugelkappen begrenzt sind. Das sind die Hyperebenen, die die Kugelkappen von der Kugel trennen, und die den Kugelmittelpunkt in ihrem Inneren enthalten.
Besitzt ein Polyeder P von der Einheitskugel $B^3$ den Hausdorffabstand $\eta$, so ist aufgrund der Definition der Hausdorffmetrik [ ${\mathit P} \subseteq B_{\eta}^3$ ] das Polyeder in einer Kugel vom Radius $1+\eta$ enthalten und enthält [wegen $B^3 \subseteq {\mathit P}$ ] eine Kugel vom Radius $1-\eta$.
Das heißt, daß die Abweichung eines n-eckigen oder n-flächigen Polyeders ${\mathit P}_n$ von der Einheitskugel wegen $\eta \geq R/r$ stets die Ungleichung erfüllt:

$$\eta( {\mathit P}_n,B^3 ) \geq ( \sin \gamma_n / \cos \gamma_n ) > (2\pi) / (\sqrt{27} \cdot n)$$ (3.13)

Die Ungleichungen (4) und (5) lassen sich verschärfen [30], woraus man folgende Korollare erhält:

• $\frac{R}{r} \geq \tan \frac{\pi}{p} \cdot \tan \frac{\pi}{q}$ mit $p = \frac{2k}{f}$ und $q = \frac{2k}{e}$.
• Enthält ein n-seitiges Polyeder ${\mathit Q}_n$ die Einheitskugel, so gilt :
  
  $$V({\mathit Q}_n) \geq (n-2) \cdot (3 \tan^2 \gamma_n -1) \sin 2\gamma_n.$$
  
  

• Enthält ein n-eckiges Polyeder ${\mathit P}_n$ die Einheitskugel, so gilt :
  
  $$V({\mathit P}_n) \geq \frac{\sqrt{3}}{2} \cdot (n-2) \cdot (3 \tan^2 \gamma_n -1).$$
  
  

• Ist ein n-eckiges Polyeder ${\mathit P}_n$ in der Einheitskugel so gilt :
  
  $$V({\mathit P}_n) \leq \frac{n-2}{6} \cdot (3 - \cot^2 \gamma_n ) \cdot \cot \gamma_n.$$