Halbreguläre Lagerungen

Als ein wichtiges Hilfsmittel in der Untersuchung des Unterdeckungsproblemes hat sich folgender Graphen erwiesen:

Sind n Punkte auf der Kugeloberfläche gegeben, so verbinden wir diejenigen Punkte durch einen Großkreisbogen, die voneinander sphärischen Minimalabstand $2r_n$ haben. Das bedeutet, daß wir zwei Mittelpunkte verbinden, wenn sich die zugehörigen Kreise berühren. Die Kreismittelpunkte heißen nun Ecken des Graphen, die verbindenden Großkreisbögen wollen wir Kanten des Graphen nennen [29, 30, 63].
Zwei Kanten AB und CD des Graphen können einander nicht schneiden, denn sonst gilt, wenn S den Schnittpunkt von AB und CD bezeichnet:

$$4r_n = 2r_n + 2r_n = AB + CD = (AS + SC) + (BS + SD) > AC + BD > 4r_n$$

[In dieser Ungleichungskette verwenden wir die Dreiecksungleichung auf den Dreiecken $\Delta(ASC)$ und $\Delta(BSD)$.]
Unser Graph zerlegt die Kugel in offene, einfach zusammenhängende Gebiete, sogar in sphärische Polygone. Ein Polygon, das aus m Kanten und m Ecken gebildet wird, zerlegt die Sphäre in zwei Teile. Enthält eines dieser Teilgebiete keine weitere Kante des Graphen, so soll es m-Eck heißen.
Der Grad einer Ecke P sei die Anzahl der Kanten, die in diesem Eckpunkt P zusammentreffen. Ist der Grad 0, so heißt die Ecke isoliert. Hat eine Ecke den Grad 1 oder 2, so hat sie noch genügend '' Bewegungsfreiheit'', sodaß wir sie isolieren können. Daher können wir o.B.d.A. annehmen, daß der Graph keine Ecken vom Grad 1 oder 2 enthält.
Einen Graph, der keine Verschiebungen mehr zuläßt, durch die man alle Punkte isolieren kann, nennen wir irreduzibel.
In einem irreduziblen Graphen können nur Winkel kleiner $\pi$ auftreten [29]. Enthält der Graph ein m-Eck, so ordnen wir diesem ein umfanggleiches sphärisches Dreieck zu. Da jedes vorkommende m-Eck gleichlange Seiten hat [= $2r_n$], ist sein Umfang gleich $2r_n \cdot m$. Weiters ist der Umfang eines sphärischen Dreiecks stets kleiner $4\pi$, und daraus schließen wir, daß ein irreduzibler Graph, der ein m-Eck enthält, einen Radius $r_n < \frac{\pi}{m}$ hat.
Wegen $2r_{12} = 72^\circ$ bestehen daher die Graphen für $6 < n < 12$ nur aus Drei- und Vierecken. Diese Graphen enthalten weiters keine isolierten Punkte, da in jedem gleichseitigen Drei- oder Viereck mit Seitenlänge 2r der Abstand von jedem inneren Punkt zu einem Eckpunkt stets kleiner 2r ist.
Bezeichnet $\Delta(\theta)$ den Flächeninhalt eines gleichschenkeligen Dreieckes mit gleichlangen Seiten der Länge a und dem von ihnen eingeschlossenem Winkel $\theta$, so ist $\Delta(\theta)$ eine konkave Funktion:

$$\Delta(\theta) = 2 \cdot (\pi/2 - \arctan(\cos a \cdot \tan \frac{\theta}{2})) + \theta - \pi$$

$\Delta_r$ := $\Delta(\rho_r)$ sei der Flächeninhalt des gleichseitigen Dreieckes mit Seitenlänge r, $V(\beta)$ sei der Flächeninhalt eines Viereckes des Graphen mit Winkel $\beta$. Wie wir bereits [I.2] wissen, kann sich $\beta$ nur zwischen $\rho_r/2$ und $2\rho_r$ bewegen. Da $V(\beta) = 2 \cdot \Delta(\beta)$ konkav ist, nimmt die Funktion $V(\beta)$ ihr Minimum nur in $\beta = \rho_r$ und $2\rho_r$ an.
Wird die Summe zweier Winkel $\beta_1+\beta_2=s$ festgehalten, so ist auch $V(\beta_1)+V(\beta_2) = V(\beta_1+V(s-\beta_1)$ eine konkave Funktion, die ihren Minimalwert genau dann annimmt, wenn eines der beiden Vierecke in zwei Dreiecke zerfällt [30]. Treffen in einem reinen Drei- und Vierecksgraphen in einer Ecke d Drei- und v Vierecke zusammen (Die Viereckswinkel seien dabei $\beta_1,..,\beta_v$), so ist die Flächensumme aller Polygone, die sich dort treffen, gleich $S = d \cdot \Delta_r + \sum^v_{i=1} V(\beta_i)$.
Auf diese Summe wenden wir die Überlegung des vorhergehenden Absatzes an, und erhalten, daß S genau dann minimal wird, wenn bis auf eine Ausnahme alle Vierecke des Graphen in Dreiecke zerfallen.
Bezeichnen wir mit $\beta$ den Winkel des nicht zerfallenden Vierecks so gilt die Ungleichung:

$$S \geq (d+2v) \cdot \Delta_r + U(\omega), \mathtt{mit} \; U(\beta) := V(\beta) - 2\Delta_r.$$

[Dieses U ist der '' Flächenüberschuß'' des '' störrischen'' Vierecks gegenüber dem Minimalwert.]
Man kann $\beta$ dadurch berechnen, daß man von $2 \rho$ solange $\rho_r$ abzieht, bis der ''Rest'' zwischen $\rho_r$ und $2\rho_r$ liegt. Daher ist $\beta$ nicht von der Anzahl der Drei- und Vierecke in dem betrachteten Eckpunkt abhängig; auch ist $\beta$ in allen Eckpunkten gleich. Addiert man die obige Ungleichung über alle Ecken des Graphen, so erhält man:

$$\sum S = 3 \cdot S_3 + 4 \cdot S_4 \geq (3{\mathit f}_3... ...athit f}_3 + 2{\mathit f}_4) \cdot \Delta + n \cdot U(\beta),$$

wenn man mit $S_k$ bzw. ${\mathit f}_k$ die Inhaltssumme bzw. die Anzahl der k-Ecke bezeichnet. Wir ergänzen auf jeder Seite $S_3 = \mathit{f}_3 \cdot \Delta_r$, und erhalten:

$$4 \cdot 4\pi = 4 \cdot (S_3 + S_4 ) \geq ( 3 {\mathit f}... ...f}_4) \cdot \Delta_r + \frac{4}{4} \cdot n \cdot U(\beta).$$

Daher gilt:

$$4\pi = ({\mathit f}_3+2{\mathit f}_4) \cdot \Delta + \frac{1}{4} \cdot n \cdot U(\beta).$$

Hat der Graph k Kanten und f Flächen, so gilt nach der Eulerschen Polyederformel:

$$n-2 = {\mathit k}-{\mathit f} = \frac{1}{2} \cdot (3... ...t f}_4) = \frac{1}{2} \cdot ({\mathit f}_3+2{\mathit f}_4),$$

da jedes k-Eck k Seiten [=Kanten des Graphen] hat.

Mit der Bezeichnung $\Delta^*:= \Delta(\beta)$ können wir die Ungleichung ausdrücken durch :

$$(2n-4) \cdot \Delta_r + \frac{1}{2} \cdot n \cdot (\Delta^*-\Delta_r) \leq 4\pi$$ (1.15)

Gleichheit kann hier nur auftreten, wenn der Graph entweder nur Dreiecke oder in jeder Ecke genau ein Viereck enthält. Da der Viereckswinkel $\beta$ auf der ganzen Sphäre gleich ist, sind alle auftretenden Vierecke regulär. Daher haben wir das Netz eines Archimedischen Körpers, der aus Drei- und Vierecken gebildet wird, vorliegen.

Es gibt nur zwei solche Körper, und zwar (3,3,3,4) [mit 8 Eckpunkten] und (3,3,3,3,4) [mit 24 Eckpunkten]. Diese Polyeder stellen tatsächlich die optimalen Anordnungen für das Unterdeckungsproblem für n = 8 bzw. 24 dar. Für $n = 8$ reicht es zu zeigen, daß die obige Ungleichung scharf ist, für n = 24 benötigt man eine Verschärfung.
Eine solche stammt von Robinson [70] und besagt:
Ist $\beta = 2\pi-4\rho$, $\Delta^*:= \Delta(\beta)$ sowie $60^\circ < 2r_n < 72^\circ$, so ist

$$(2n-4) \cdot \Delta + \frac{2}{3} \cdot (n-6) \cdot (\Delta^* -\Delta) \leq 4\pi$$ (1.16)

Diese Ungleichung gilt für beliebige Graphen. Um die grundlegende Aussage: ''Treffen in einer Ecke einer r-Triangulierung k Dreiecke zusammen, so ist die Gesamtfläche dieser Dreiecke stets $> 4 \cdot \Delta_r + (k-4) \cdot \Delta^*$'' beweisen zu können, benötigt Robinson [70] komplizierte Fallunterscheidungen, obwohl er im wesentlichen ''nur'' die obige Beweisidee der Bestimmung eines Maximums unter Nebenbedingungen verwendet. Durch Summation über alle Ecken und nach Umformungen erhält er dann das obige Resultat, aus dem die optimale Anordnung für $n=24$ [Arch. Körper (3,3,3,3,4)] folgt.
Die Robinson'sche Methode ist aber mit dieser Ungleichung noch nicht völlig ausgeschöpft. Indem man die Dreiecksflächen, die sich um einen Punkt gruppieren, ''reguliert'' dh. indem man die Fläche von den zusammenstoßenden Dreiecken so ''umverteilt'' sodaß sie ''gleichmäßiger'' werden, kann man die genannte Ungleichung noch verfeinern.
Als neue Bezeichnung muß man dazu einführen: $\Delta ' := \Delta(r')$, wobei $r'$ die Länge der Diagonale eines sphärischen '' Quadrates '' mit Seiten der Länge 2r bezeichnet. Mit dieser Bezeichnungsweise erhält die zugrundeliegende Ungleichung die Gestalt, wenn k wiederum die Anzahl der Dreiecke um einen Punkt bezeichnet:

$$\mathtt{regulierte \; Gesamtfl\uml {a}che} \geq 4 \cdot \Delta_r + (2k-10) \cdot \Delta^* + (6-k) \cdot \Delta'.$$

Durch Summation über alle Ecken folgt daraus:

$$(2n-4) \cdot \Delta_r + \frac{2}{3} \cdot (n-6) \cdot (\Delta^* -\Delta_r) + 4 \cdot (\Delta '-\Delta^*) \leq 4\pi,$$ (1.17)

eine Ungleichung, die auch für $n > 24$ gilt.
Ein zentraler Bestandteil der Ungleichung (2) ist die Tatsache, daß der Flächeninhalt $T_4$ eines regulären Vierecks stets $\geq 2\Delta_r$ ausfällt. Eine Verallgemeinerung dieser Ungleichung findet sich in [39], sowie [65]:
Besitzt ein reguläres n-Eck mit Seitenlänge $2r$ und Flächeninhalt $T_n$ die Eigenschaft, daß je zwei seiner Ecken voneinander einen Abstand $\geq 2r$ haben, dann ist $T_n \geq (n-2) \cdot \Delta_r$.
Da wir in zwei Fällen optimale Anordnungen in den Graphen Archimedischer Körper gefunden haben, wird man vermuten, daß auch die anderen halbregulären Körper gute, wenn nicht gar optimale Anordnungen liefern.
Neuere Arbeiten (z.B. [47]) zeigen aber, daß diese Vermutung im allgemeinen nicht zutrifft. Die Klasse der halbregulären Körper mit regulären Ecken ist für unsere Betrachtungen uninteressant, da im Graphen nur gleichseitige Flächen vorkommen können, die die Polyeder dieser Klasse jedoch nicht besitzen.
Die bisherigen Überlegungen können wir zusammenfassen in:
Ist ein System von n Punkten auf der Sphäre gegeben, bei dem je zwei Punkte Mindestabstabstand $2r_n$ haben, so gilt [70]:

$$n < 2\pi / \Delta_r + 2$$ (1.18)

$$n < 6 \cdot (\pi + \Delta^*) / (2\Delta_r + \Delta^*)$$ (1.19)

$$n < 6 \cdot (\pi + \Delta^* - \Delta) / (2\Delta_r + \Delta^*)$$ (1.20)

[ $\Delta_r$, $\Delta '$, $\Delta^*$ werden dabei wie oben verwendet]
Dadurch erhält man $n < \frac{ 4\pi }{\sqrt 3} \cdot \frac{1}{r_n} + C_0 + C_1 \cdot r_n^2 + ...$

mit $C_0 = \left \{ \begin{array}{ll} 2 - \pi/3 \approx 0.1862 & \quad f\uml {u}... .../sqrt{3} \approx -2.5416 & \quad f\uml {u}r \; (1.20) \end{array} \right.$

Wir können auch die sogenannten zonalen Anordnungen betrachten. Diese entstehen dadurch, daß man die Kugel durch äquidistante Parallelkreise in [z.B. m] Zonen einteilt. Die gewünschten Punktverteilungen entstehen dadurch, daß man eine ebene Verteilung der Ebene auf die Kugel abbildet [94].
Aus diesen zonalen Lagerungen erhält man [39, 76, 94]:

$$\frac{\sqrt{3}}{2\pi} \cdot n \leq 4/r^2_n \leq \frac{\s... ...i})^{ 2 \over 3 } + 4 \cdot (\frac{n}{4\pi})^{ 1 \over 3 }.$$ (1.21)