Zufallspolyeder

Eine erste Möglichkeit, Polyeder mit Kugel zu kombinieren, haben wir bereits im ersten Kapitel kennengelernt und im vorigen Paragraphen genauer betrachtet.
Bevor wir der Frage nachgehen, wie gut sich die Kugel durch Polyeder approximeren läßt, wollen wir den Erwartungswert bestimmter Maßzahlen eines Zufallspolyeders ermitteln. Darunter verstehen wir die konvexe Hülle von n zufällig ausgewählten Punkten auf der $S^{d-1}$.
Will man n Punkte gemäß einer Wahrscheinlichkeitsverteilung auf der Sphäre auswählen, so muß man sich zuerst überlegen, auf welche Weise dies möglich ist. Üblicherweise wird dazu die Sphäre mit Polarkoordinaten ausgestattet. Wir können annehmen, daß die gewünschte Verteilung eine gewöhnliche mehrdimensionale Dichte besitzt. Für die Gleichverteilung muß wegen $\int_{S^{d-1}} f = 1$ die Dichte $f \equiv \frac{1}{\kappa_d}$ sein.
Es seien nun gemäß der Gleichverteilung n Punkte auf der $S^{d-1}$ ausgewählt. In [15] wird der Erwartungswert der drei Maßzahlen Oberfläche, mittlere Breite und Anzahl der Seiten berechnet. Da die dabei erhaltenen Formeln zwar exakt, aber kompiliziert sind, werden auch einfachere asymptotische Abschätzungen aus ihnen hergeleitet.

Die zugrundeliegende Denkweise soll im folgenden anhand der Oberfläche erläutert werden.
Es ist zunächst zu bemerken, daß bei statistischen Überlegungen nur Polytope, deren Facetten Simplizes sind, eine Rolle spielen, da andere Polytoptypen nur mit Wahrscheinlichkeit Null auftreten können.
Unter einer Facette eines d-dimensionalen Polytopes P versteht man stets die (d-1)-dimensionalen Flächen von P.
Daher können wir die Oberfläche der konvexen Hülle der Punkte $\{P_1,..,P_n\}$ als Summe d-eckiger Facetten betrachten.
Wählen wir aus $\{P_1,..,P_n\}$ auf beliebige Weise d Punkte aus, die wir o.B.d.A. stets mit $P_1,..,P_d$ bezeichnen wollen, so ist die konvexe Hülle der d Punkte $P_1,..,P_d$ genau dann eine Facette eines konvexen, d-dimensionalen und n-eckigen Polytops, wenn die übrigen (n-d) Punkte $P_{d+1},..,P_n$ auf ein und derselben Seite der Hyperebene ${\mathcal H}$ zu liegen kommen, die durch $P_1,..,P_d$ aufgespannt wird.
Diese Hyperebene ${\mathcal H} = {\mathcal H}({\mathbf u},t)$ zerlegt die Vollkugel $B^d$ in zwei Kugelkappen, eine mit Höhe 1-t und eine mit Höhe 1+t. Dabei bezeichnet t den Abstand der Hyperebene zum Ursprung.
Wird mit $\overline{\omega} = \omega(P_1,..,P_d )$ die Oberfläche der kleineren Kugelkappe bezeichnet, so ist die Wahrscheinlichkeit, daß ein Punkt auf diesem Teil der Kugel liegt, gleich $\overline{\omega}/\omega_d$, das ist Kugelkappenoberfläche/Gesamtkugeloberfläche. Die Wahrscheinlichkeit, daß er auf der anderen Kugelkappe liegt, ist gleich der Gegenwahrscheinlichkeit $1-\overline{\omega}/\omega_d$.
Die $P_i$'s sind gleichmäßig und unabhängig voneinander über $S^{d-1}$ verteilt, und daher tritt das Ereignis, daß alle n-d Punkte $P_{d+1},..,P_n$ vollständig in einem der beiden Kugelteile liegen, mit Wahrscheinlichkeit $q_{n,d}$ ein:

$$q_{n,d} = (\overline{\omega}/\omega_d)^{n-d} + (1-\overline{\omega}/\omega_d)^{n-d}$$ (3.14)

Die Wahrscheinlichkeit $q_{n,d}$ hängt klarerweise nur von den Parametern der Trägerhyperebene ab, da eine Veränderung der Punkte innerhalb dieser Hyperebene keinen Einfluß auf den Abstand der Hyperebene vom Ursprung der $S^{d-1}$ besitzt. Daher können wir $q_{n,d}$ als Funktional der Hyperebenenparameter ${\mathbf u}$ und t betrachten: $q_{n,d} = q_{n,d}(P_1,..,P_d) = q_{n,d}({\mathbf u},t)$.
Weiters sei folgende Konvention eingeführt: Um die folgenden Formeln übersichtlich gestalten zu können, schreiben wir unter das Integralzeichen immer nur die Variable, für die das Zeichen gilt. Integriert wir immer über $S^{d-1}$. Bei reellen Integrationsparametern wird wie üblich das Integrationsintervall angegeben.
Die Punkte $P_1,...,P_d$ spannen im ${\rm I\mkern-3mu R}^d$ ein (d-1)-dimensionales Simplex auf, dessen Inhalt $T:=T(P_1,...,P_d)$ sei. Dann ist:

$${\huge E}(q_{n,d} \cdot T) = \int_{P_1} ... \int_{P_d} q_... ...) }{\omega_d} ... \frac{ {\mathit d}\omega(P_1) }{\omega_d}$$

der Erwartungswert des Volumens der Facette $conv \{P_1,..,P_d \}$. Da es stets ${ n \choose d }$ Möglichkeiten gibt, aus n Punkten d auszuwählen, gilt für den Erwartungswert der Gesamtoberfläche $\omega_{n,d}$:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot \int_{P_1}... ...) }{\omega_d} ... \frac{ {\mathit d}\omega(P_1) }{\omega_d}$$

Gemäß [64] kann man die unabhängige und gleichverteilte Auswahl von d Punkten auf der $S^{d-1}$ stochastisch äquivalent durch folgende sequentielle Konstruktion ersetzen :
(i) Wähle eine Trägerhyperebene ${\mathcal H} = {\mathcal H}({\mathbf u},t)$ mit dem als Sphärenelement gleichmäßig verteilten Normalvektor ${\mathbf u}$ und mit dem Abstand t vom Mittelpunkt der $S^{d-1}$.
Dieser besitze als Zufallsvariable ( $-1 \leq t \leq 1$) die Dichte:

$$2 \cdot (1-t^2)^{(d^2-2d-1)/2} / (B(\frac{1}{2},\frac{1}{2} \cdot (d-1)^2 ))$$ (3.15)

Mit $B(p,q)$ wird hier die Beta-Verteilung mit den Parametern p und q bezeichnet. Im folgenden werden wir stets die Abkürzung $\mathbf{B} := B(\frac{1}{2},\frac{1}{2} \cdot (d-1)^2 )$ verwenden.
(ii) Der Schnitt dieser Hyperebene mit der Sphäre ist der Rand einer (d-1)-dimensionalen Vollkugel mit Radius $(1-t^2)^{(1/2)}$, deren sphärisches, (d-2)-dimensionales Oberflächenmaß im weiteren mit $\omega'$ bezeichnet wird.

Da die Oberfläche einer d-dimensionalen Kugel mit Radius r gegeben ist durch $r^{d-1} \cdot \omega_d$, ist

$$\omega'(S^{d-1} \cap {\mathcal H}) = (1-t^2)^{(d-2)/2} \cdot \omega_{d-1}.$$

(iii) Wähle nun d Punkte $P_1',..,P_d'$ aus dem Schnitt von ${\mathcal H}$ und $S^{d-1}$. Die Auswahl der Punkte $P_1',..,P_d'$ erfolge dabei gemäß einer gemeinsamen Gleichverteilung mit der Gewichtung

$$(d-1)! \cdot \frac{\mathbf{B}}{2} \cdot \frac{\omega_{d-1}^... ...} \cdot \frac{1}{(1-t^2)^{(d-1)/2}} \cdot T(P_1',...,P_d').$$ (3.16)

Es ist bei diesen Dichten zu beachten, daß die auftretenden Oberflächenmaße auf 1 zu normieren sind, um Wahrscheinlichkeitsmaße zu erhalten. Daher wird $\omega(P_i')$ im folgenden stets durch $(1-t^2)^{(d-2)/2} \cdot \omega_{d-1}$ dividiert.
Die Auswahl von $P_1,..,P_d$ erfolgt also gemäß einer Dichte, die gleich ist dem Produkt der beiden Dichten (2) und (3). Daher ist:

$$\frac{{\mathit d}\omega(P_1)}{\omega_d} ... \frac{{\mathit d}\omega(P_d)}{\omega_d} =$$

$$\frac{2}{\mathbf{B}} \cdot (1-t^2)^{(d^2-2d-1)/2} \cdot {... ...thbf{B}}{2} \cdot \frac{\omega_{d-1}^d}{\omega_d^{d-1}} \cdot$$

$$\frac{ T(P_1',...,P_d') }{(1-t^2)^{(d-1)/2}} \cdot \frac{{... ...athit d}\omega(P_d')}{(1-t^2)^{(d-2)/2} \cdot \omega_{d-1}} =$$

$$= (d-1)! \cdot \frac{\omega_{d-1}^d}{\omega_d^{d-1}} \cdot... ... d} t }{(1-t^2)^{d/2}} \cdot {\mathit d} \omega({\mathbf u}).$$

Damit kann der Erwartungswert ${\huge E}(\omega_{n,d})$ umgeformt werden zu:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot \int_{P_1}... ...)}{\omega_d} ... \frac{{\mathit d}\omega(P_d)}{\omega_d} =$$

$$= { n \choose d } \cdot \int_{P_1'} ... \int_{P_d'} ... ... ...t (d-1)! \cdot \frac{\omega_{d-1}^d}{\omega_d^{d-1}} \; \cdot$$

$$\cdot (d-1)! \cdot T(P_1',...,P_d') \cdot \frac{{\mathit ... ... d} t}{(1-t^2)^{d/2}} \cdot {\mathit d} \omega({\mathbf u}) =$$

$$= { n \choose d } \cdot \frac{(d-1)!}{\omega_d^d} \int_... ...t_{-1}^{+1} q_{n,d}(P_1' ... P_d') \cdot T^2(P_1' ... P_d')$$

$${\mathit d}\omega'(P_1') ... {\mathit d}\omega'(P_d') \cd... ...t d} t}{(1-t^2)^{d/2}} \cdot {\mathit d} \omega({\mathbf u})$$

Da die Wahrscheinlichkeit $q_{n,d}$ nur von der Trägerhyperebene ${\mathcal H}$ abhängt, können wir $q_{n,d}$ aus dem Integral über die P's herausziehen, da sich diese nur innerhalb ${\mathcal H}$ bewegen. Das ergibt:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot \frac{(d... ...thbf u}} \cdot \int_{-1}^{+1} q_{n,d}({\mathbf u},t) \: \cdot$$

$$\cdot \bigl( \int_{P_1'} ... \int_{P_d'} T^2(P_1' ... P_d')... ... d} t }{(1-t^2)^{d/2}} \cdot {\mathit d} \omega({\mathbf u})$$

Als nächstes wollen wir den Wert des Integrals über $\omega'(P_i')$ bestimmen, und nehmen uns dazu das zweite Moment folgender Zufallsvariable zu Hilfe:
Das (d-1)-dimensionale Volumen der konvexen Hülle von d Punkten, die auf der Oberfläche einer (d-1)-dimensionalen Kugel mit Radius r liegen, habe die Dichtefunktion f. Es ist dann [64]:

$$\int x^2 \cdot f(x) {\mathit d}x = \frac{r^{2(d-1)} \cdot d}{ (d-1)! \cdot (d-1)^{(d-1)} }$$

Mit der entsprechenden Gewichtung erhält man daraus [15]:

$$\bigl( \int_{P_1'} ... \int_{P_d'} T^2 {\mathit d}\omega... ... \frac{(1-t^2)^{(d-1)} \cdot d}{ (d-1)! \cdot (d-1)^{(d-1)} }$$

Wenn wir dieses Resultat in die Formel für den Erwartungswert einsetzen, ergibt dies:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot \frac{(d... ...\omega_{d-1}^d}{(d-1)!} \cdot \frac{d}{(d-1)^{d-1}} \; \cdot$$

$$\int_{{\mathbf u}} \cdot \int_{-1}^{+1} q_{n,d}({\mathbf u... ...frac{d}{2}} {\mathit d} t {\mathit d} \omega({\mathbf u}) =$$

$${ n \choose d } \cdot \bigl( \frac{\omega_{d-1}}{\omega_d} ... ...2)^{(d^2-d-1)/2}{\mathit d} t {\mathit d} \omega({\mathbf u})$$

Es wurde bereits bemerkt, daß $\overline{\omega}$ die Oberfläche einer d- dimensionalen Kugelkappe mit Höhe 1-t ist. Man kann die Oberfläche ausdrücken durch [15]:

$$\omega_{d-1} \cdot \int_t^1 (1-s^2)^{(d-3)/2} {\mathit d}s ... ... f\uml {u}r \; -1 \; \leq t \; \leq 0 \end{array} \right.$$

Damit erhält man:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot \frac{ d... ...t \bigl( \frac{\omega_{d-1}}{\omega_d} \bigr) ^{d-1} \; \cdot$$

$$\int_{-1}^{+1} \frac{\omega_{d-1}}{\omega_d} \bigl( \int_... ...xponent ??\cdot (1-t^2) (1-t^2)^{(d^2-d-1)/2}{\mathit d} t$$

Das innere Integral ($\int ds$) kann durch partielles Integrieren und explizites Ausrechnen noch umgeformt werden [15]:

$${\huge E}(\omega_{n,d} ) = { n \choose d } \cdot d \cdot ... ...t {{n-d}\choose k } \cdot \gamma_r^{n-d-k} \cdot {\huge S}$$ (3.17)

Um diese Formel übersichtlicher gestalten zu können, wurden folgende Abkürzungen verwendet :

• $\gamma_0 := \frac{1}{2}$, $\gamma_{p+1} := \frac{1}{2\pi \cdot (p+1) \cdot \gamma_p} = \frac{ \Gamma (p+1) }{2^{p+1}} \cdot \bigl( \frac{1}{ \Gamma ( \frac{ p+1 }{2} ) } \bigr) ^2$ für $p\in {\rm I\mkern-3mu N}$.
• $r = \left \{ \begin{array}{ll} 0 & \; f\uml {u}r \; d \; gerade \\ 1 & \; f\uml {u}r \; d \; ungerade \end{array} \right.$
• ${\huge S} := \sum_{j=0}^{(d-r-3) \cdot k/2} [\gamma_r,\gamma_{r+2},...,\gamma_{d-3} ]_j^k \cdot I(r \cdot (n-d-j),d^2-d+2j+r \cdot k-1,k)$

Dabei ist $[c_0,c_1 ,..,c_l]^k_j$ der j-te Koeffizient von:

$$\bigl( \sum_{i=0}^l c_i \cdot x^i \bigr) ^k = \sum [c_0...c_r]_j^k \cdot x^j$$

Weiters setzt man $\cos x := t$ und:

$$I(m,p,q) := \int_0^{\pi} x^m \cdot \sin^p x \cdot \cos^q x {\mathit d}x$$

Das asymptotische Verhalten ist für die Oberfläche gleich:

$$\omega_d - \frac{1}{2(d-2)! \cdot (d+1)} \cdot \omega_{d-1... ...{d+2} ) \cdot \frac{1}{n^{2/(d-1)}} \cdot (1+{\mathit o}(1)).$$

hat also einen Fehlbetrag der Ordnung $( C(d) / n^{2/(d-1)} )\cdot (1+{\mathit o}(1))$.

Weiters wird in [15] der Erwartungswert der Seitenanzahl der konvexen Hülle behandelt. Die asymptotische Abschätzung lautet bei dieser Fragestellung:

$$\frac{2}{d} \cdot \gamma_{(d-2)^2} \cdot \gamma_{(d-1)}^{-(d-1)} \cdot n \cdot (1+{\mathit o}(1)).$$

Eine ähnliche Fragestellung wird in [45] untersucht. Autoren betrachten hier den Tangentialkörper, der aus n Punkten, die auf der $S^{d-1}$ liegen, gebildet wird und fragen nach seiner zu erwartenden Eckenanzahl. Sie erhalten:

$${\huge E}(\char93 \{Ecken\}_{n,d}) = {n \choose d} \cdot... ... \cdot {\mathit C}(d(d-2)) \cdot \sin^{d(d-2)} r {\mathit d}r$$

wo $I_k(r):= \int_0^r \sin^k x {\mathit d}x$ und ${\mathit C}(k) = \frac{ 2 \cdot \Gamma(\frac{1}{2} \cdot k+1)} { \Gamma(\frac{1}{2}) \cdot \Gamma(\frac{1}{2}\cdot k+\frac{1}{2})}$ zu setzen ist.

Ist $t:= \sin^2 r$ und bezeichnen wir mit $B_k$ die Verteilungs- und mit $\beta_k$ die Dichtefunktion der $B(k/2,1/2)$ - Verteilung, so kann man das Ergebnis auch anschreiben als:

$${\huge E}(\char93 \{Ecken\}_{n,d}) = {n \choose d} \cdot ... ...} B_{d-1}(t) \Bigr) \cdot \beta_{d^2+2d-1}(t) {\mathit d}t$$

Für d = 3 gibt es ein exaktes Resultat:

$${\huge E}(\char93 \{Ecken\}_{n,3}) = 2n - 4 - (n+1) \cdot (n-2)/2^{n-1}$$

Für größere Dimensionen ist auch hier eine Abschätzung interessanter als die genaue Formel. In [45] findet man mit Konstanten $c_1 > 0$ und $c_2 > 0$:

$$c_1^d \cdot d^{(d-6)/2} \leq {\huge E}(\char93 \{Ecken\}_{n,d}) \leq c_2^d \cdot d^{(d-5)/2} \cdot n$$ (3.18)

In [14] befindet sich die genaue asymptotische Aussage:

$${\huge E}(\char93 \{Ecken\}_{n,d}) \sim \frac{2}{d} \cdot \gamma_{(d-1)^2} \cdot \gamma_{d-1}^{-(d-1)} \cdot n,$$ (3.19)

Dabei ist $\gamma_n := \Gamma(n)/(2^n \cdot \Gamma^2(n/2) )$ für $n \in {\rm I\mkern-3mu N}$.