Inhalt

1 Einführung 4

2 Definitionen 5

3 Problemanalyse 6 3.1 Arbeitszeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Verkehrsgraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.2.1 ad hoc Berechnung des Zeitabstandes . . . . . . . . . . . . . . . . 10 3.2.2 Vorbehandelter Verkehrsgraph . . . . . . . . . . . . . . . . . . . . 12 3.2.3 Umwege von Fahrgemeinschaften . . . . . . . . . . . . . . . . . . . 16 3.2.4 Berücksichtigung weiterer Aspekte . . . . . . . . . . . . . . . . . . 17

3.3 Eine sinnvolle Einschränkung . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Stabilität von Fahrgemeinschaften . . . . . . . . . . . . . . . . . . . . . . 19

4 Geometrische Algorithmen 23 4.1 Algorithmus für δ-Paare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 k-D-Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3 Quad Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Das Grid File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.4.1 Funktionsweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.4.2 Aufwandsbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . 51

4.5 Grid-Quad-Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5 Systementwurf und Spezifikation 61 5.1 Operationen des FGM-Systems . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2 Aufwandsbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3 Optimierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Kontroll- und Datenfluß . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6 Ausblick 68 A Quellenangaben 70

A.1 Mobilitätszentrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 A.2 Verkehrssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 A.3 Digitale Karten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 A.4 Anschriften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 A.5 Ergebnisse aus der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . 72

Abbildungsverzeichnis

1 Umkehrung von Satz 2 gilt nicht. . . . . . . . . . . . . . . . . . . . . . . 11 2 Der maximale Fehler verringert sich auch durch größere Auf- und Abfahrts-

listen nicht. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Vorfahrtswartezeiten an Kreuzungen. . . . . . . . . . . . . . . . . . . . . 18 4 Die Start- und Zielorte der Personen {a, b, c, d} in der Ebene. . . . . . . . 19 5 Veranschaulichung zum Satz 8. . . . . . . . . . . . . . . . . . . . . . . . . 25 6 Der Körper K und die Hyperebene H aus Definition 29 im 2-dimensionalen

Raum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 7 Punktemenge mit zugehörigem 2-D-Baum. . . . . . . . . . . . . . . . . . 30 8 Veranschaulichung von |W_{k+2}| ≤ 2|W_{k}| . . . . . . . . . . . . . . . . . . . 33 9 Ausschnitt aus T′ zu Abb. 8 . . . . . . . . . . . . . . . . . . . . . . . . . 34 10 Der maximale Baum T′ nutzloser Knoten bei der Bereichsuche(U_{c}(s))… 39 11 Der maximale Baum T′′ nutzloser Knoten bei der Bereichsuche(U_{c}(s)). . 40 12 Zuordnung von Punkten aus U zur Directorymatrix D . . . . . . . . . . 42 13 Einfache Kollision beim Einfügen in die Directorymatrix D durch den

Punkt f. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 14 Mehrfache Kollision beim MEH. . . . . . . . . . . . . . . . . . . . . . . . 45 15 Mehrfache Kollision beim MDH. . . . . . . . . . . . . . . . . . . . . . . . 46 16 Verschiedene Splitstrategien (S1, S2). . . . . . . . . . . . . . . . . . . . . 46 17 Deadlock bei der Nachbarstrategie. . . . . . . . . . . . . . . . . . . . . . 47 18 Bruderstrategie im 2-dimensionalen Raum U . . . . . . . . . . . . . . . . 48 19 Deadlock im 3-dimensionalen mit der Bruderstrategie. . . . . . . . . . . . 48 20 Einfügen mit anschließendem Verschmelzen. . . . . . . . . . . . . . . . . 49 21 Bereichssuche((20,40),(40,75)) . . . . . . . . . . . . . . . . . . . . . . . . 49 22 2-Ebenen-Directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 23 partition(P) ist nicht eindeutig. . . . . . . . . . . . . . . . . . . . . . . . 62 24 Das Fahrgemeinschaftssystem. . . . . . . . . . . . . . . . . . . . . . . . . 65

1 Einführung

Immer größer werden die Konflikte bei der Befriedigung ständig wachsender Mobilitätsansprüche. Die Funktionsfähigkeit der Städte und Gemeinden wird während der Hauptverkehrszeiten zunehmend durch die hohen Verkehrsbelastungen eingeschränkt. Eine Lösung dieser Problematik ist nur über eine Reduzierung der Fahrzeugbewegungen zu erreichen. Dabei muß auch aus Gründen der steigenden Umweltbelastung die höhere Ausnutzung freier Platzkapazitäten der Verkehrsmittel im Vordergrund der Bemühungen stehen. Welche Probleme sind bei der Bildung von Fahrgemeinschaften zur Entlastung des Berufsverkehrs besonders zu beachten? Welche Methoden und Werkzeuge aus der Informatik können zur Lösung eingesetzt werden?

Nach den Ergebnissen aus dem EG Forschungsprojekt Carpooling System Management, das innerhalb des DRIVE Forschungsprogramms Anfang der 90’er Jahre zwischen Belgien und Deutschland durchgeführt wurde, läßt sich feststellen, daß wir im wesentlichen die Arbeitszeiten und -wege zu berücksichtigen haben.

Um Arbeitswege zu bestimmen, definieren wir einen Verkehrsgraphen und entwickeln einen Algorithmus zur Bestimmung kürzester Wege. Da diese Berechnungen relativ aufwendig sind, versuchen wir, eine Vorsortierung aller Personen vorzunehmen, so daß Personenpaare, die offensichtlich keine Fahrgemeinschaft bilden können, nicht in Betracht gezogen werden. Für die Durchführung der Vorsortierung sind geometrische Algorithmen geeignet. Wir diskutieren einige dieser Algorithmen und entwickeln daraus einen, der sich für unsere Anwendung am vielversprechendsten erweist.

2 Definitionen

Die wichtigen Definitionen werden in den Kapiteln, in denen sie benötigt werden, erst eingeführt. Einige Schreibweisen und gängige Bezeichnungen in der Informatik erläutern wir hier.

Wenn wir in dieser Arbeit vom Logarithmus sprechen, beziehen wir uns immer auf den Logarithmus zur Basis zwei und schreiben nur log.

Definition 1 Eine Zeichnung D von einem Graphen G in der Ebene heißt planar, wenn es keine zwei Kanten von G gibt, die sich kreuzen. Der Graph G heißt planar, wenn eine planare Zeichnung D von G in der Ebene existiert.

Definition 2 Für x ∈ IR^{+} heißt: ⌊x⌋ = max{n|n ∈ IN , n ≤ x} die untere Gaußklammer von x und ⌈x⌉ = min{n|n ∈ IN , x ≤ n} die obere Gaußklammer von x.

Definition 3 Gegeben sei ein euklidischer Raum IR^{d} und ein c ∈ (IR^{+})^{d}, dann heißt

U_{c}(s) = {x|x ∈ U, |x_{i} − s_{i}| ≤ c_{i} für i ∈ {1, 2, …, d}}

die c-Umgebung von s ∈ U,

R(x, y) = [x_{1}, y_{1}) × ⋯ [x_{d}, y_{d})

eine Region (für x, y ∈ IR^{d}) und

|R(x, y)| = Π_{i=1}^{d}|x_{i} − y_{i}|

die Größe der Region R(x, y).

Definition 4 Gegeben sei ein Baum T, dann bezeichnet |T | die Anzahl der Knoten, die T enthält. Die Höhe von T ist H(T), wobei gilt: falls |T | = 1, dann ist H(T) = 1. Den Folgeknoten von v ∈ T über den Zeiger x bezeichnen wir weiterhin mit v.x. Falls v.x = u gilt, dann heißt v der Vaterknoten von u. Den Vaterknoten von v bezeichnen wir als den Großvaterknoten von u. Ein Knoten heißt ein Blatt, wenn er keine Folgeknoten besitzt. Alle Knoten eines Baums, die keine Blätter sind, heißen innere Knoten.

Level(i) := {v|v ∈ T, Pfadlänge von v zur Wurzel ist i}

Definition 5 Gegeben sei eine Punktemenge S, die im Raum IR^{d} liegt. Wir bezeichnen für s ∈ S die Koordinaten als s_{1}, …, s_{d}. m ∈ S heißt der Median von S bzgl. der Koordinate i (m = Median(i, S)), wenn gilt:

\frac{|S|}{2} ≥ |\{s|s ∈ S\\{m\} , s_{i} ≥ m_{i}\}|
\frac{|S|}{2} ≥ |\{s|s ∈ S\\{m\} , s_{i} ≤ m_{i}\}|

Falls es mehrere Punkte m ∈ S gibt, die die Bedingungen erfüllen, wählen wir willkürlich einen davon aus.

3 Problemanalyse

Im EG Forschungsprojekt Carpooling System Management zwischen Belgien und Deutschland wurden Anfang der 90’er Jahre Grenzen und Möglichkeiten von Fahrgemeinschaften sowie die Einrichtung und Erprobung einer Mobilitätszentrale untersucht, die das bestehende öffentliche Verkehrsangebot transparenter macht. Der sozialwissenschaftliche Teil der Arbeit wurde an der Bergischen Universität GH Wuppertal von Dr.-Ing. N. Reinkober durchgeführt. Die informationstechnische Realisierung übernahm der belgische Partner, die Firma Taxistopp (s. Anhang A.4). Am Beispiel der Region Hameln wurde eine Mobilitätszentrale über einen Zeitraum von zwei Jahren erprobt. Es stellte sich dabei heraus, daß Fahrgemeinschaften für Betriebe und Arbeitnehmer aus folgenden Gründen bereits eine wesentliche Bedeutung besitzen:

• Parkplätze Es muß ein kleineres Parkplatzangebot für die Arbeitnehmer zur Verfügung gestellt werden, wodurch Betriebe erhebliche Fixkosten sparen.

• Pünktlichkeit Für Fahrgemeinschaften müssen genaue Zeitabsprachen zwischen den Teilnehmern getroffen werden. Folglich werden Verspätungen im Hinblick auf die Partner eher vermieden.

• Streßabbau Die Konzentration der Fahrgemeinschaftsteilnehmer ist nicht ausschließlich auf den Verkehr, sondern im wesentlichen auf die zwischenmenschliche Konversation gerichtet. Auch werden Probleme, die das Arbeitsleben betreffen, oft schon auf den Wegen besprochen.

• Finanzen Die Betriebskosten für das Fahrzeug erhöhen sich unwesentlich, verteilen sich aber auf die Fahrgemeinschaftsteilnehmer.

• Zweites Auto Durch eine Verringerung der nutzlosen Parkzeiten von Fahrzeugen an Arbeitsorten wird für viele Arbeitnehmer das zweite Auto überflüssig.

Welche Probleme stellen sich aber bei der Bildung von Fahrgemeinschaften? Die Schwierigkeiten teilen sich im Groben in zwei Bereiche: Akzeptanz- und Raum- /Zeitprobleme. Akzeptanzprobleme bei der Zusammenstellung von Fahrgemeinschaften wurden von Dr. Reinkober in Wuppertal ausführlichst untersucht [Reinkober 94], und es seien hier stellvertretend nur einige genannt:

• Durch Absprachen, die in einer Fahrgemeinschaft getroffen werden müssen, ist der Einzelne in seiner Flexibilität eingeschränkt (Einkaufen nach der Arbeit, etc.).

• Da für viele Menschen in der industrialisierten Gesellschaft das Auto mehr repräsentiert als ein Fortbewegungsmittel besteht keine Bereitschaft, dieses gemeinschaftlich zu nutzen.

• Jeder Teilnehmer einer Fahrgemeinschaft muß sich beim Ausleben der Eigenschaften einschränken (Raucher/Nichtraucher, Musikgeschmack, etc.).

• Betrieblicher Status kann durchaus die Bildung von Fahrgemeinschaften verhindern (Manager/Arbeiter).

• Soziale Gruppenzugehörigkeiten stellen ein weiteres Problem dar (Männer/Frauen, Homo-/Heterosexuelle, etc.).

Alle Punkte haben gemeinsam, daß sie extrem von der persönlichen Einstellung von Menschen zu Fahrgemeinschaften abhängig sind. Ist sie positiv, dann sind Menschen oft bereit sich einzuschränken. Wenn ein Raucher eine Fahrgemeinschaft bilden will, verzichtet er auf den Arbeitswegen auf die Zigarette. Wenn Besorgungen anliegen, kann man sich mit den Fahrgemeinschaftsteilnehmern absprechen, usw. Bei der Umsetzung der Mobilitätszentrale in der Region Hameln wurde daher besonderer Wert auf Öffentlichkeitsarbeit gelegt. Wir betrachten diesen Aspekt im weiteren nicht mehr und verweisen auf [Reinkober 94].

Die Raum-/Zeitprobleme sind die folgenden:

• Niemand ist bereit, auf den Arbeitswegen einen wesentlich längeren Weg zu fahren, um jemanden von zu Hause abzuholen.

• Es besteht keine Bereitschaft einen wesentlich längeren Zeitraum vor dem Arbeitsbeginn oder nach Arbeitsende am Arbeitsplatz zu verbringen.

Diese beiden Punkte werden nun ausführlicher behandelt. Dazu betrachten wir das vorhandene Verkehrswegenetz für die Bestimmung der Umwege und verschiedene Arbeitszeitmodelle für die Abweichungen der Arbeitszeiten.

3.1 Arbeitszeiten

Es gibt heute schon sehr viele verschiedenartige Arbeitszeitmodelle, deren Zahl sich in Zukunft aufgrund sich ändernder Wirtschaftsbedingungen noch wesentlich erweitern werden. Bei der Zusammenstellung von Fahrgemeinschaften müssen die Arbeitszeiten berücksichtigt werden, daher beschreiben wir einige wichtige Modelle:

• feste Arbeitszeiten

• Schichtdienst

• Gleitzeit

• 4-Tage-Woche

• kollektive Freischicht

• individuelle Regelungen

• täglich unterschiedliche Arbeitszeiten Bei den festen Arbeitszeiten handelt es sich um die übliche Fünf-Tage-Woche von Montag bis Freitag, wobei täglich die selben Arbeitszeiten vorliegen, die sich auch von Woche zu Woche nicht verändern. Für den Schichtdienst gibt es verschiedene Varianten: 2-Schicht-Betrieb, 2-Schicht-Betrieb mit vereinzelten Nachtschichtblöcken und den kontinuierlichen 3-Schicht-Betrieb. Jeder Person sind dann z.B. beim 2-Schicht-Betrieb zwei oder beim 3-Schicht-Betrieb drei Arbeitszeiten zugeordnet. Bei der Gleitzeit sind jeder Person zwei Anfangs- und zwei Endzeiten zugeordnet. Für die 4-Tage-Woche muß für jede Person festgelegt sein, an welchen Tagen und zu welchen Arbeitszeiten sie arbeitet. Das Modell kollektive Freischicht meint, daß Arbeitnehmer über einen bestimmten Zeitraum nicht arbeiten. Im Rahmen der Arbeitszeitverkürzung wurden auch solche individuelle Regelungen einbezogen, die sich darauf beziehen, daß jeder Arbeitnehmer z.B. nur vier Tage pro Woche arbeitet, aber den freien Tag selbst bestimmt. Im Pflegebereich ist es beispielsweise oft nicht möglich, Arbeitszeiten, die sich wöchentlich wiederholen, anzugeben. Es muß dann möglich sein, für eine bestimmte Anzahl von Tagen die Arbeitszeiten einer Person zuzuordnen. Uns interessiert letztendlich, ob alle Personen einer Fahrgemeinschaft möglichst an vielen Tagen bzgl. der Arbeitszeiten zusammen fahren können.

Die Auflistung dieser Modelle soll nur zeigen, wie vielschichtig die Betrachtung der Arbeitszeiten ist. Die Datenstrukturen für die einzelnen Modelle werden dabei nicht schwieriger, sondern nur immer größer. Wenn alle Personenmitglieder einer Personengruppe feste Arbeitszeiten haben, müssen wir feststellen, ob die Abweichungen der Arbeitszeiten unter einer zumutbaren Zeitschranke liegen.

Definition 6 Zu einer Personenmenge P sei eine Funktion A : P ⟶ (IR^{+})^{2} (A(p) = (A_{1}(p), A_{2}(p))) gegeben. Dann heißt für eine Fahrgemeinschaft f ⊆ P

AA(f) = max{|A_{i}(p) − A_{i}(p′)|| i ∈ {1, 2}, p, p′ ∈ f}

die Abweichung der Arbeitszeiten von f.

Für die Zeitschranke c_{Z} ∈ IR ist dann zu prüfen, ob AA(f) ≤ c_{Z} gilt.

3.2 Verkehrsgraphen

Jetzt geht es um die Frage: wovon hängt die Zeit ab, die benötigt wird, um von einem Punkt A in einem Straßennetz zu einem Punkt B zu gelangen? Möglich wäre:

1. Geschwindigkeit des eigenen Fahrzeugs

2. Vorfahrtsregelung auf dem Weg von A nach B

3. Tageszeitabhängiges Verkehrsaufkommen auf dem Weg von A nach B

4. Höchstgeschwindigkeiten auf den Straßenabschnitten

5. Länge des Weges von A nach B

Da wir in erster Linie am Berufsverkehr interessiert sind, wirkt sich eine höhere Geschwindigkeit des eigenen Fahrzeugs kaum auf die gesamte Fahrtzeit aus. Wir können diesen Punkt vernachlässigen. Die Vorfahrtsregelungen und das Verkehrsaufkommen lassen wir aus Gründen der Komplexität vorerst unberücksichtigt, zeigen aber später, wie auch dies zu modellieren ist.

Definition 7 Der Graph G = (V, E, K, γ, δ) mit den Knoten V, den gerichteten Kanten E, den Koordinaten K (K : V ⟶ IR × IR ist injektiv) und den positiven Gewichtsfunktionen γ, δ : E ⟶ IR^{+} für die Kantenlänge und die Durchfahrtsgeschwindigkeit, heißt ein Verkehrsgraph, wenn gilt:

γ((v_{1}, v_{2})) ≥ \sqrt{|K_{1}(v_{1}) − K_{1}(v_{2})|^{2} + |K_{2}(v_{1}) − K_{2}(v_{2})|^{2}}

Die Menge der Knoten V umfaßt dabei Kreuzungen und Auffahrten. Die Strassen werden durch die Kanten E repräsentiert. Aufgrund von Einbahnstraßen und unterschiedlichen Geschwindigkeiten bzgl. der Richtung benötigen wir gerichtete Kanten. Jedem Knoten ist mittels der Funktion K ein Punkt in der euklidischen Ebene zugeordnet (K(v) = (K_{1}(v), K_{2}(v))). Die Funktion γ ordnet jedem Straßenstück e = (v_{1}, v_{2}) eine Straßenlänge zu. Dies ist notwendig, da Straßen kurvig verlaufen und somit die Länge nicht dem euklidischen Abstand zwischen zwei Endpunkten entspricht. Die durchschnittliche Geschwindigkeit auf einem Straßenstück e wird durch die Funktion δ festgelegt. Dabei gilt, daß für die Durchfahrt von e genau \frac{γ(e)}{δ(e)} Zeiteinheiten notwendig sind.

Auf Verkehrsgraphen gibt es für uns drei Maße bzgl. aller Knotenpaare, die interessant sind.

Definition 8 Gegeben sei ein Verkehrsgraph G = (V, E, K, γ, δ), dann heißt ein Weg w = [x_{1}, x_{2}, x_{3}, …, x_{m}] existierend, wenn gilt:

∀_{i∈{1,2,...,m−1}} (x_{i}, x_{i+1}) ∈ E

Definition 9 Gegeben sei ein Verkehrsgraph G = (V, E, K, γ, δ) und ein existierender Weg w = [x_{1}, x_{2}, …, x_{m}], dann heißt:

• d_{e}(v_{1}, v_{2}) = \sqrt{|K_{1}(v_{1}) − K_{1}(v_{2})|^{2} + |K_{2}(v_{1}) − K_{2}(v_{2})|^{2}} der euklidische Abstand,

• d_{e}(w) = ∑_{i=1}^{m−1} d_{e}(x_{i}, x_{i+1}) die euklidische Länge,

• d_{l}(w) = ∑_{i=1}^{m−1} γ(x_{i}, x_{i+1}) die entfernungsbedingte Länge,

• d_{l}(v_{1}, v_{2}) = min{d_{l}(w′)|w′ = [v_{1}, …, v_{2}] ist ein existierender Weg in G} der Längenabstand,

• d_{z}(w) = ∑_{i=1}^{m−1} \frac{γ(x_{i},x_{i+1})}{(x_{i},x_{i+1})} die zeitliche Länge und

• d_{z}(v_{1}, v_{2}) = min{d_{z}(w′)| w′ = [v_{1}, y_{1}, y_{2}, …, y_{m}, v_{2}]

ist ein existierender Weg in G}

der Zeitabstand

vom Knotenpaar v_{1}, v_{2} bzw. vom Weg w.

Der euklidische-, der Längen- und der Zeitabstand erfüllen für alle Knotenpaare die △- Ungleichung. Die Wohn- und Arbeitsorte von Menschen liegen im Verkehrsgraphen G an den Knoten.

Zwar wohnen Menschen eigentlich an den Straßen, bei einem recht feinen Straßennetz können wir den dadurch entstehenden Fehler bei der Entfernungsberechnung vernachlässigen und benutzen den nächstliegenden Knoten.

Wie ist das Verhältnis von |V | zu |E| in Verkehrsgraphen?

Satz 1 In einem planaren Graphen G gilt: |E| ≤ 3|V | − 6.

Bew. Im triangulierten Graph G′ = (V′, E′) von G = (V, E) ist jedes Gebiet von drei Kanten umrandet, und die Anzahl der Gebiete ist durch |V |−2 beschränkt (E ⊆ E′) [Harary 74].

Wenn wir für einen Verkehrsgraphen G die bestehende Verkehrsführung, d.h. die Lage der Straßen und Kreuzungen in der Realität, als eine Zeichnung D von G auffassen, dann ist D meist nicht planar, z.B. wegen Brücken und Untertunnelungen. Da aber insgesamt doch nur recht wenige Brücken und Tunnel auftreten, können wir für Verkehrsgraphen G annehmen: |E| ≤ 3|V |.

Da das Verhältnis von Zeit- zu den euklidischen Abständen in Verkehrsgraphen sich in der Realität nicht willkürlich verhält, stellen wir durch die folgende Definition einen Zusammenhang her.

3.2.1 ad hoc Berechnung des Zeitabstandes

Definition 10 Gegeben sei ein Verkehrsgraph G. Für ein Knotenpaar (u, v) heißt \overline{δ}(u, v) = \frac{d_{e}(u,v)}{d_{z}(u,v)} die Durchschnittsgeschwindigkeit.

Man beachte, daß die Durchschnittsgeschwindigkeit nicht die tatsächliche durchschnittliche Geschwindigkeit ist, die gefahren wird, da sie aus dem euklidischen Abstand berechnet wird.

Satz 2 Es sei \overline{δ}(u, v) = \frac{d_{e}(u,v)}{d_{z}([u,w,v])} für einen Weg w. Für alle Knoten x ∈ w gilt dann:

\overline{δ}(u, v) ≤ \overline{δ}(u, x) ∨ \overline{δ}(u, v) ≤ \overline{δ}(x, v)

Bew. Annahme die Aussage gelte nicht, dann gilt:

\overline{δ}(u, v) > \overline{δ}(u, x) ∧ \overline{δ}(u, v) > \overline{δ}(x, v)  (1)

und wegen x ∈ w:

d_{z}(u, v) = d_{z}(u, x) + d_{z}(x, v)  (2)

Weiterhin folgt daraus:

\overline{δ}(u, v) ≤ \frac{d_{e}(u, x) + d_{e}(x, v)}{d_{z}(u, v)}
= \frac{d_{z}(u, x)}{d_{z}(u, v)}\overline{δ}(u, x) + \frac{d_{z}(x, v)}{d_{z}(u, v)}\overline{δ}(x, v)
\underbrace{<}_{Gl.1,2} \overline{δ}(u, v)

Die Annahme führt also zum Widerspruch.

Es gibt auf allen Wegen Teilwege, auf denen die Durchschnittsgeschwindigkeit höher ist, als auf dem Gesamtweg. Man könnte meinen, daß es folglich auch Teilwege mit einer niedrigeren Durchschnittsgeschwindigkeit geben müsse . Dies ist nicht unbedingt der Fall, wie wir am Beispiel in Abb. 1 erkennen.

Abbildung 1: Umkehrung von Satz 2 gilt nicht. Die Zeitabstände d_{z} sind an den dicken und die euklidischen Abstände d_{e} an den dünnen Linien angegeben. Die einzige fahrbare Verbindung vom Knoten u nach v führt über x. Es gilt dann: \overline{δ}(u, v) = \frac{1}{2}, \overline{δ}(u, x) = \overline{δ}(x, v) = 3.

Satz 3 Es sei d_{e}(u, v) = d_{l}([u, w, v]) für ein Knotenpaar (u, v) und einen Weg w, dann gilt:

∀_{x∈w} \overline{δ}(u, v) ≥ \overline{δ}(u, x) ∨ \overline{δ}(u, v) ≥ \overline{δ}(x, v)

Bew. Wir führen erneut einen Widerspruchsbeweis durch:

\overline{δ}(u, v) < \overline{δ}(u, x) ∧ \overline{δ}(u, v) < \overline{δ}(x, v)

Dann folgern wir einen Widerspruch:

\overline{δ}(u, v) ≥ \frac{d_{e}(u, v)}{d_{z}(u, x) + d_{z}(x, v)}
= \frac{d_{e}(u, v)}{\frac{d_{e}(u,x)}{\overline{δ}(u,x)} + \frac{d_{e}(x,v)}{\overline{δ}(x,v)}}

> \frac{d_{e}(u, v)\overline{δ}(u, v)}{d_{e}(u, x) + d_{e}(x, v)}
= \overline{δ}(u, v)

In der Realität gilt also die Umkehrung von Satz 2 fast immer, da sehr viele Straßen gerade verlaufen.

Definition 11 Gegeben sei ein Verkehrsgraph G = (V, E, K, γ, δ) und ein Grenzparameter g = (g_{0}, g_{1}, …, g_{k}) ∈ IR^{k} mit:

∀_{i∈{1,2,...,k}} g_{i−1} < g_{i} und g_{0} = 0, g_{k} > max{d_{e}(u, v)|u, v ∈ V }

dann heißt (für i ∈ {1, 2, …, k}):

ADG(g_{i}) = max\{|\overline{δ}(u, v) − \overline{δ}(u′, v′)| | u, v, u′, v′ ∈ V
g_{i−1} ≤ d_{e}(u, v) ≤ g_{i}, g_{i−1} ≤ d_{e}(u′, v′) ≤ g_{i}}

die Abweichung der Durchschnittsgeschwindigkeiten.

Durch den Grenzparameter g wird eine Äquivalenzklasseneinteilung auf allen Knotenpaaren geschaffen. Die Klasse K(g_{i}) enthält alle Knotenpaare, deren euklidischer Abstand zwischen g_{i−1} und g_{i} liegt. Innerhalb dieser Klasse weichen die Durchschnittsgeschwindigkeiten höchstens um ADG(g_{i}) voneinander ab. In realen Straßennetzen können wir erwarten, daß die Abweichung mit wachsendem euklidischen Abstand abnimmt.

Definition 12 Ein Verkehrsgraph G mit Grenzparameter g ∈ IR^{k} heißt ein monotoner Verkehrsgraph, wenn gilt:

ADG(g_{1}) > ADG(g_{2}) > ⋯ > ADG(g_{k})

Wenn wir die Abweichung der Durchschnittsgeschwindigkeiten für einen Grenzparameter g von einem Verkehrsgraphen und aus jeder Äquivalenklasse g_{i} eine Durchschnittsgeschwindigkeit δ(g_{i}) kennen, wissen wir für (u, v) ∈ K(g_{i}):

\begin{aligned}δ(g_{i}) − ADG(g_{i}) & ≤ & \overline{δ}(u, v) & ≤ & δ(g_{i}) + ADG(g_{i}) \\ \frac{d_{e}(u,v)}{δ(g_{i})−ADG(g_{i})} & ≥ & d_{z}(u, v) & ≥ & \frac{d_{e}(u,v)}{δ(g_{i})+ADG(g_{i})} \end{aligned}

Folglich können wir ad hoc einen ungefähren Zeitabstand d̃_{z}(u, v) berechnen:

d̃_{z}(u, v) := \frac{1}{2} (\frac{d_{e}(u, v)}{δ(g_{i}) − ADG(g_{i})} + \frac{d_{e}(u, v)}{δ(g_{i}) + ADG(g_{i})})
= \frac{δ(g_{i})d_{e}(u, v)}{δ^{2}(g_{i}) − D^{2}(g_{i})}

Für den Fehler F = |d̃_{z}(u, v) − d_{z}(u, v)| ergibt sich:

F ≤ \frac{ADG(g_{i})d_{e}(u, v)}{δ^{2}(g_{i}) − D^{2}(g_{i})}

Unabhängig von den speziellen Knotenpaaren gilt dann in der Klasse K(g_{i}):

F ≤ \frac{ADG(g_{i})g_{i}}{δ^{2}(g_{i}) − D^{2}(g_{i})}

Bem. Anstatt die Abweichung der Durchschnittsgeschwindigkeiten exakt zu berechnen, werden wir nur zu einigen Knotenpaaren aus jeder Klasse K(g_{i}) die Durchschnittsgeschwindigkeiten ausrechnen. Als Klassendurchschnittsgeschwindigkeit δ(g_{i}) nehmen wir das Mittel aus diesen Werten und als Abweichung der Durchschnittsgeschwindigkeiten die maximale Abweichung dieser Werte. Diese Berechnungen werden am Anfang einmal durchgeführt, während später ein ungefährer Zeitabstand mit konstantem Aufwand ermittelt wird.

3.2.2 Vorbehandelter Verkehrsgraph

Zur Bestimmung des Zeitabstandes von Knoten in Verkehrsgraphen können wir den Algorithmus von Dijkstra verwenden [Dijkstra 59]. Wenn für die Datenstrukturen in Dijkstras Algorithmus Heaps verwendet werden, benötigt die Berechnung des Zeitabstandes zwischen zwei Knoten höchstens O(|V | log |V |) Operationen, da die Minimumbildung oder das Einfügen in einen Heap höchstens log |V | Berechnungsschritte nach sich ziehen [Ottmann 93] (s. Anhang A.5). Wir haben dabei berücksichtigt, daß |E| ∈ O(|V |) gilt. Um den Zeitabstand d_{z}(u, v) zu bestimmen, werden dabei alle Knoten aus {w|w ∈ V, d_{z}(u, w) ≤ d_{z}(u, v)} betrachtet. Wenn wir diesen Algorithmus beidseitig einsetzen, d.h. vom Knoten u und vom Zielknoten v aus den günstigsten Weg suchen, haben wir fast nur die Knoten aus \{w|w ∈ V, d_{z}(u, w) ≤ \frac{1}{2}d_{z}(u, v) ∨ d_{z}(w, v) ≤ \frac{1}{2}d_{z}(u, v)\} zu betrachten. Es werden nur unwesentlich mehr Knoten in die Suche miteinbezogen, da es Knoten w mit d_{z}(u, w) = d_{z}(w, v) = \frac{1}{2}d_{z}(u, v) wahrscheinlich nicht gibt. Falls die Knoten von G relativ gleichmäßig in der Ebene verteilt sind und die Abweichungen der Durchschnittsgeschwindigkeiten gering sind, haben wir dadurch fast nur noch die Hälfte der Knoten zu betrachten. Eine andere Modifikation ist der A^{∗} Algorithmus, der den noch zurückzulegenden Weg mit einbezieht [Claus 93]. Für diesen restlichen Weg wird immer eine Maximalgeschwindigkeit angenommen und die Summe aus dem gefahrenen Weg und dem restlichen Weg minimiert, so daß mit Sicherheit der kürzeste Weg gefunden wird. Umso größer die Abweichung der Geschwindigkeiten in einem Verkehrsgraphen sind, umso weniger unterscheidet sich dieses Vorgehen von Dijkstras Algorithmus. Die Annahme einer Maximalgeschwindigkeit können wir umgehen, wenn wir für den Restweg die ad hoc Zeit aus dem letzten Abschnitt verwenden.

Da wir häufig die Zeitabstände beliebiger Knotenpaare zu berechnen haben, ist es sinnvoll eine einmalige Vorausberechnung durchzuführen, so daß der Zeitabstand zwischen zwei Knoten nahezu mit konstantem Aufwand zu berechnen ist.

Definition 13 Zu einem Verkehrsgraphen G = (V, E, K, γ, δ) heißt V G = (V′, E′, z) ein vorbehandelter Graph, wenn gilt:

• V′ ⊆ V

• E′ ist vollständig

• z(u, v) = d_{z}(u, v) für u, v ∈ V′

Die Berechnung des vorbehandelten Graphen V G = (V′, E′, z) benötigt im worst case mittels Dijkstras Algorithmus O(|V′||V | log |V |) Operationen. Dijkstras Algorithmus löst das Problem zur Bestimmung des minimalen Pfades zwischen zwei Knoten im worst case mit dem selben Aufwand wie die Berechnung aller kürzesten Pfade vom Knoten s zu allen anderen Knoten. Wir wenden Dijkstras Verfahren für jeden Knoten des vorbehandelten Graphen an. Es ist ein Speicheraufwand von |V′|(|V′| − 1) Einheiten zu reservieren.

Definition 14 Gegeben sei ein Verkehrsgraph G = (V, E, K, γ, δ), ein zugehöriger vorbehandelter Graph V G = (V′, E′, z) und ein k ∈ IN, dann heißen für u ∈ V die Mengen AU(u), AB(u) ⊆ V′ mit:

• |AU(u)| = |AB(u)| = k

• ∀_{v∈V′\AU(u)} ∀_{w∈AU(u)} d_{z}(u, v) > d_{z}(u, w)

• ∀_{v∈V′\AB(u)} ∀_{w∈AB(u)} d_{z}(v, u) > d_{z}(w, u) die Auf- und die Abfahrtslisten von u. Bei der Berechnung der Auf- und Abfahrtslisten werden gleichzeitig noch die Zeitabstände von u zu allen Knoten aus AB(u) ∪ AU(u) vermerkt. Definition 15 Gegeben sei ein vorbehandelter Graph und Auf- und Abfahrtslisten, dann heißt

d̃(u, v) := min{d_{z}(u, a) + z(a, b) + d_{z}(b, v)| a ∈ AU(u), b ∈ AB(v)}

der ungefähre Abstand und

F (u, v) := d̃(u, v) − d_{z}(u, v)

der Fehler von u nach v. Da die Zeitabstände bekannt sind, sind zur Berechnung von d̃(u, v) höchstens |AU(u)||AB(v)| Operationen nötig. Es ist allerdings der Fehler zu berücksichtigen, der von der Wahl der Knotenmenge des vorbehandelten Graphen und der Länge der Auffahrtslisten abhängt. Man beachte, daß d̃(u, v) ≥ d_{z}(u, v) immer gilt. Satz 4 Gegeben sei ein Verkehrsgraph G, ein zugehöriger vorbehandelter Verkehrsgraph V G, Auf- und Abfahrtslisten AU(), AB() und ein Weg w = [u, w′, v] mit:

• d_{z}(w) = d_{z}(u, v)

• K(w′) ∩ AU(u) ≠ ∅ ∧ K(w′) ∩ AB(v) ≠ ∅ dann gilt: d̃(u, v) = d_{z}(u, v) Bew. Da es Knoten x ∈ AU(u) und y ∈ AB(v) geben muß, die auf w′ liegen, gilt:

d̃(u, v) ≤ d_{z}(u, x) + z(x, y) + d_{z}(y, v) = d_{z}(w)

Satz 5 Für den Fehler F (u, v) = d̃(u, v) − d_{z}(u, v) in einem symmetrischen Verkehrsgraphen gilt:

F (u, v) ≤ 2 min{d_{z}(u, a) + d_{z}(b, v)|a ∈ AU(u) , b ∈ AB(v)} Bew. Es sei: min{d_{z}(u, a) + d_{z}(b, v)|a ∈ AU(u) , b ∈ AB(v)} = d_{z}(u, a) + d_{z}(b, v), dann

gilt:

d̃(u, v) − 2 min{d_{z}(u, a) + d_{z}(b, v)|a ∈ AU(u) , b ∈ AB(v)}

\begin{matrix}≤ & d_{z}(a, b) − d_{z}(u, a) − d_{z}(b, v) \\ ≤ & d_{z}(a, u) + d_{z}(u, v) + d_{z}(v, b) − d_{z}(u, a) − d_{z}(b, v) \\ = & d_{z}(u, v) \end{matrix}

Wir werden die Knotenmenge V′ des vorbehandelten Graphen V G möglichst gleichverteilt über den Raum U = [0, A]^{2}, in dem alle Knoten des ursprünglichen Verkehrsgraphen liegen, plazieren. U sei überdeckt mit l^{2} Zellen

z_{i,j} = [(i − 1)\frac{A}{l}, i\frac{A}{l}) × [(j − 1)\frac{A}{l}, j \frac{A}{l}) für i, j ∈ \{1, 2, …, l\}

Die Knoten aus V, die in einer Zelle z liegen, bezeichnen wir als K(z).

Weiterhin gelte für den Zeitabstand:

∀_{Zellen z} ∀_{u,v∈K(z)} d_{z}(u, v) ≤ \sqrt{2} \frac{A}{l} \frac{1}{K}  (3)

Die Konstante K gibt sozusagen eine Mindestgeschwindigkeit an, die überall gefahren werden kann. Es ist zu beachten, daß wir uns dabei aber auf den maximalen euklidischen Durchmesser einer Zelle und nicht auf einen Längenabstand bezogen haben. Die Knotenmenge V′ des vorbehandelten Graphen ist nun so zu wählen, daß in jeder Zelle mindestens ein Knoten aus V′ liegt.

Satz 6 In einem symmetrischen Verkehrsgraphen G = (V, E, γ) gilt unter Berücksichtigung von Gleichung 3 für den maximalen Fehler F = max{F (u, v)|u, v ∈ V }:

F ≤ 4 \sqrt{2} \frac{A}{l} \frac{1}{K}

Bew. Nach Satz 5 und Gleichung 3 folgt die Aussage, wenn einbezogen wird, daß in jeder Zelle ein Knoten aus der Knotenmenge des vorbehandelten Graphen liegt.

Wenn wir die Unterteilungen im Raum U feiner, z.B. l doppelt so groß wählen, wird der maximale Fehler zwar geringer, aber wir haben einen vierfachen Speicherbedarf für die Knotenmenge des vorbehandelten Graphen zu reservieren. Außerdem kann die Einteilung des Raums U nicht beliebig fein gewählt werden, da dann die Gleichung 3 nicht mehr oder nur noch mit einer zu kleinen Konstante K zugesichert werden kann. Wir haben eine weitere Einflußmöglichkeit auf den Fehler bei der Berechnung des Zeitabstandes über die Größe der Auf- und Abfahrtslisten. Dadurch kann zwar der Fehler im worst case nicht verbessert werden, wie wir anhand eines Beispiels (s.Abb. 2) zeigen, aber im Mittel wird man offensichtlich durch eine höhere Anzahl von Auf- und Abfahrtspunkten bessere Ergebnisse erzielen. Um effektivere Aussagen über den maximalen Fehler machen zu können, müßten wir unser Modell des Verkehrsgraphen stärker einschränken.

3.2.3 Umwege von Fahrgemeinschaften

Zu einer Personenmenge P = {p_{1}, …, p_{n}} ist eine Menge von Start- und Zielorten gegeben (S ⊆ V, Z ⊆ V). Jeder Person p_{i} ist ein Startort s_{i} und ein Zielort z_{i} zugeordnet.

[figure: A; A; i\frac{A}{l}; i′ \frac{A}{l}; (i′ − 1)\frac{A}{l}; a; b; v; j \frac{A}{l}; j′ \frac{A}{l}; (j − 1)\frac{A}{l}; (j′ − 1)\frac{A}{l}; (i − 1)\frac{A}{l}; u]

Abbildung 2: Der maximale Fehler verringert sich auch durch größere Auf- und Abfahrtslisten nicht.

Auch wenn AU(u) und AB(v) Knoten aus den umliegenden Zellen von u und v enthalten, kann gelten:

d_{z}(a, b) = d_{z}(a, u) + d_{z}(u, v) + d_{z}(v, b)
sowie: d̃(u, v) = d_{z}(u, a) + d_{z}(a, b) + d_{z}(b, v)
F = d̃(u, v) − d_{z}(u, v)
= 2(d_{z}(u, a) + d_{z}(b, v))

Definition 16 Gegeben sei eine Menge P, ein zugehöriger Verkehrsgraph G = (V, E, K, γ, δ) und eine Fahrgemeinschaft F = {p_{i_{1}} …, p_{i_{k}}} (F ⊆ P), dann heißt w = [x_{1}, x_{2}, …, x_{m}] ein möglicher Weg für F, wenn w ein existierender Weg in G ist, und es gilt:

∃_{j∈{i_{1},i_{2},...,i_{k}}}  s_{j} = x_{1} ∧ z_{j} = x_{m}
s_{i_{1}}, …, s_{i_{k}}, z_{i_{1}}, …, z_{i_{k}} liegen auf w
∀i ∈ {i_{1}, …, i_{k}}  l([w′, s_{i}]) ≤ l([w′′, z_{i}])

[w′, s_{i}] und [w′′, z_{i}] sind Anfangsstücke von w, und l ist eine Funktion auf allen Wegen, die die Länge, d.h. die Anzahl der Kanten des Weges angibt.

Ein möglicher Weg w einer Fahrgemeinschaft endet also mit dem Zielort des Fahrers, an dessen Startort der Weg w beginnt. Der Weg w beinhaltet alle Start- und Zielorte von Personen von F. Außerdem werden für alle Mitglieder von F die zugehörigen Startorte vor den Zielorten besucht.

Aufgrund der verschiedenen Abstandmaße definieren wir nun analog die Umwege.

Definition 17 Für einen Verkehrsgraphen G und eine Fahrgemeinschaft F heißt:

• U_{e}(F) = min{d_{e}(w) − d_{e}(s, z)|w = [s, …, z] ist ein möglicher Weg für F } der euklidische Umweg

• U_{l}(F) = min{d_{l}(w) − d_{l}(s, z)|w = [s, …, z] ist ein möglicher Weg für F } der entfernungsbedingte Umweg

• U_{z}(F) = min{d_{z}(w) − d_{z}(s, z)|w = [s, …, z] ist ein möglicher Weg für F } der zeitliche Umweg

von der Fahrgemeinschaft F.

Den Umweg berechnen wir immer aus dem möglichen Weg für die Fahrgemeinschaft F und dem günstigsten Weg für den Fahrer von F. Der Umweg entspricht also in natürlicher Weise den ’Mehrkosten’, die eine Person zu tragen hat, wenn sie nicht selbst auf dem ’billigsten’ Weg von ihrem Start- zu ihrem Zielort fährt. Entsteht aber dem Fahrer immer der größte Nachteil in einer Fahrgemeinschaft?

Lemma 1 Gegeben sei ein Verkehrsgraph G, eine Personenmenge P und eine Fahrgemeinschaft F = {p_{i_{1}}, …, p_{i_{k}}} mit einem möglichen Weg w = [s, w_{1}, s′, w′, z′, w_{2}, z], für den gilt: U_{e}(F) = d_{e}(w) − d_{e}(s, z). Es gilt dann für alle Personen p′ ∈ F mit Start- und Zielort s′, z′:

d_{e}([s′, w′, z′]) − d_{e}(s′, z′) ≤ U_{e}(F)

Bew. wegen der △-Ungleichung gilt :

\begin{matrix}d_{e}([s, w_{1}, s′])  ≥ & d_{e}(s, s′) \\ d_{e}([z′, w_{2}, z])  ≥ & d_{e}(z′, z) \\ d_{e}(s, s′) + d_{e}(s′, z′) + d_{e}(z′, z) ≥ & d_{e}(s, z) \end{matrix}

dies ergibt:

\begin{matrix}U_{e}(F) = d_{e}(w) − d_{e}(s, z) ≥ & d_{e}(s, s′) + d_{e}([s′, w′, z′]) + d_{e}(z′, z) − d_{e}(s, z) \\ ≥ & d_{e}([s′, w′, z′]) − d_{e}(s′, z′) \end{matrix}

Korollar 1 Da die △-Ungleichung auch für den Längen- und den Zeitabstand (d_{l}, d_{z}) bzgl. aller Knotenpaare in Verkehrsgraphen gilt, ist das Lamma 1 ebenso für entfernungsbedingte und zeitliche Umwege (U_{l}, U_{z}) korrekt.

3.2.4 Berücksichtigung weiterer Aspekte

Da im Straßenverkehr viel Zeit im Stillstand vergeht, entweder durch Vorfahrtswartezeiten oder aufgrund eines erhöhten Verkehrsaufkommens, kann es wichtig sein, den Verlauf von Vorfahrtsstraßen, Ampelphasen und das Verkehrsaufkommen zu kennen.

• Tageszeitabhängiges Verkehrsaufkommen läßt sich durch eine Menge von Gewichtsfunktionen im Verkehrsgraphen G = (V, E, K, γ, δ_{1}, δ_{2}, δ_{3}) darstellen. Dabei bestimmt z.B. δ_{1} die Durchschnittsgeschwindigkeit morgens, δ_{2} abends und δ_{3} die Durchschnittsgeschwindigkeiten am Rest des Tages.

• Zeit In unserem Modell des Verkehrsgraphen vergeht die Zeit sozusagen nur auf den Straßen. Die Zeit, die wir an der Kreuzung v ∈ V warten müssen, hängt davon ab, von welcher Straße wir kommen und in welche Straße wir einbiegen. Eine Funktion V F W : V × V × V ⟶ IR^{+} kann diesen Sachverhalt darstellen. Es heißt dann V F W (v_{1}, v_{2}, v_{3}) die Vorfahrtswartezeit, die an der Kreuzung v_{2} über die Einfahrt (v_{1}, v_{2}) ∈ E und die Ausfahrt (v_{2}, v_{3}) ∈ E anfällt. Der Zeitabstand aller Knotenpaare (v_{1}, v_{2}) ∈ V × V muß dann wie folgt modifiziert werden:

d′_{z}(v_{1}, v_{2}) = min{d_{z}(w) + V F W (v_{1}, x_{1}, x_{2}) + ∑_{i=1}^{m−2} V F W (x_{i}, x_{i+1}, x_{i+2})
+V F W (x_{m−1}, x_{m}, v_{2})|

w = [v_{1}, x_{1}, x_{2}, …, x_{m}, v_{2}] ist ein existierender Weg in G}

Mittels der Funktion V F W lassen sich außerdem spezielle Verkehrsverbote an Kreuzungen realisieren (s.Abb. 3).

[figure: A; B; C; D]

Abbildung 3: Vorfahrtswartezeiten an Kreuzungen.

Es gelte für die Zeitabstände und die Vorfahrtswartezeiten:

V F W (A, B, C) = 0, V F W (A < BD) = ∞, V F W (C, B, D) = 2,
d_{z}(A, B) = d_{z}(C, B) = d_{z}(B, C) = d_{z}(B, D) = 1,
d′_{z}(A, D) = ∞ , d′_{z}(A, C) = 2 , d′_{z}(C, D) = 4

Durch V F W (A, B, D) = ∞ wird das Rechtsabbiegen an der Kreuzung B für von A kommende Fahrzeuge verboten.

• Ampeln Wartezeiten an Ampeln lassen sich im Prinzip ebenfalls mit der Funktion V F W berücksichtigen. Da Ampeln aber oft in Reihe geschaltet sind, und somit ”grüne Phasen” entstehen, sind die Wartezeiten an Ampeln nicht nur davon abhängig, welche Kreuzung, sondern welche Ampeln vorher passiert wurden. Datenstrukturen, die diese Informationen enthalten, müssen wesentlich komplexer sein, daher verzichten wir hier darauf, ’mit Kanonen auf Spatzen zu schießen’.

3.3 Eine sinnvolle Einschränkung

Personen einer Fahrgemeinschaft sollen eine ’lange’ gemeinsame Fahrtzeit haben!

Bei der bisherigen Betrachtung des Umweges spielte diese Bedingung keine Rolle. Wir hätten beispielsweise für die Anordnung der Start- und Zielorte von Personen, wie sie in Abb. 4 dargestellt ist, durchaus die Partitionierung F = {{a, b}, {c, d}} gewählt, wenn die zeitlichen Umwege für die Fahrgemeinschaften unter einer zumutbaren Umwegschranke c_{u} ∈ IR^{+} liegen (U_{z}({a, b}) ≤ c_{u} ∧ U_{z}({c, d}) ≤ c_{u}). Wir wollen aber die Einteilung F = {{a, c}, {b, d}}, wenn die zeitlichen Umwege ebenfalls unter den Umwegschranken liegen, vorziehen.

[figure: s[a]; z[a]; s[b]; z[b]; s[c]; z[d]; s[d]; z[c]]

Abbildung 4: Die Start- und Zielorte der Personen {a, b, c, d} in der Ebene.

In der Realität ist die Bereitschaft, eine andere Person p mitzunehmen, sicherlich höher, wenn der Arbeitsweg von p eine ähnliche Länge wie der eigene Arbeitsweg besitzt. Wenn es für eine Person keinen Partner gibt, der die obige Bedingung erfüllt, dann werden wir sie nicht beachten oder weniger streng einsetzen. Grundsätzlich wird durch die Bedingung eine Suchrichtung festgelegt. Dieses Vorgehen ist auch für die Reduzierung des Gesamtweges offensichtlich günstiger. Die Bedingung zieht folgende Konsequenzen nach sich. Für alle Personen einer Fahrgemeinschaft muß gelten, daß die Wohnorte, die Arbeitsorte und die Arbeitszeiten nahe beieinanderliegen. Wenn für jede Person die Wohn- und die Arbeitsorte in der Ebene durch zwei Koordinaten und die Arbeitszeiten durch zwei Parameter gegeben sind, dann werden wir in einem 6-dimensionalen euklidischen Raum Gruppen von nah beieinanderliegenden Punkten suchen (W_{1}(p), W_{2}(p), A_{1}(p), A_{2}(p), AA_{1}(p), AA_{2}(p) ∈ IR). Folgende Operation dazu muß effizient beantwortet werden (c ∈ (IR^{+})^{6}).

Bereich(p, c) : {p′| p′ ∈ P , W_{1}(p) − W_{1}(p′)| ≤ c_{1}, |W_{2}(p) − W_{2}(p′)| ≤ c_{2},
|A_{1}(p) − A_{1}(p′)| ≤ c_{3}, |A_{2}(p) − A_{2}(p′)| ≤ c_{4},
|AA_{1}(p) − AA_{1}(p′)| ≤ c_{5}, |AA_{2}(p) − AA_{2}(p′)| ≤ c_{6}}

Den Verkehrsgraphen haben wir beim Übergang obiger Bedingung zu den Konsequenzen vernachlässigt. Dieser Fehler führt aber nur dazu, daß das Angebot von möglichen Mitfahrern von p in Bereich(p, c) zuviele Personen umfasst, wenn wir c ∈ (IR^{+})^{6} geeignet wählen. Bei einer maximalen Durchschnittsgeschwindigkeit von ca. 60\frac{km}{h} in Wohnund Industriegebieten können z.B. in drei Minuten höchstens drei Kilometer zurückgelegt werden, so daß c_{1} = c_{2} = c_{3} = c_{4} = 3 gesetzt werden kann, wenn die Einheiten in Kilometern angegeben werden. In Bereich(p, (3, 3, 3, 3, ,)) liegen dann evtl. auch Personen p′ mit U_{z}({p, p′}) > 6, wenn die Zeiteinheiten in Minuten angegeben werden.

3.4 Stabilität von Fahrgemeinschaften

Definition 18 Gegeben sei eine Fahrgemeinschaft f ⊆ P, die Abweichung der Arbeitszeiten und der Umweg von f, dann heißt

C(f) = (AA(f), U_{z}(f), |f|)

die Charakteristik von f.

Ausgehend von der Fragestellung, wie ’gut’ eine Fahrgemeinschaft ist, werden wir ein Gütemaß für Fahrgemeinschaften aufgrund der Charakteristik einer Fahrgemeinschaft festlegen. Basierend auf der Stabilität einer Fahrgemeinschaft bestimmen wir daraus die Stabilität einer Partition von einer Personenmenge P. Welche Anforderungen stellen wir dabei an die Stabilität?

1. Es soll ein sogenannter Maximalparameter berücksichtigt werden, der eine maximale Abweichung der Arbeitszeiten, einen maximalen Umweg und eine maximale Personenanzahl für eine Fahrgemeinschaft angibt.

2. Es soll eine Bewertung der einzelnen Charakteristikparameter möglich sein.

3. Durch die Stabilität soll eine totale Ordnung auf allen Fahrgemeinschaften und allen Partitionen entstehen.

4. Genau dann, wenn die Fahrgemeinschaft f möglich ist, soll die Stabilität von f größer als Null sein, d.h. ST (f) > 0 gelten. gelten.

5. Falls ST (f) > ST (f′) gilt, dann soll die Qualität der Fahrgemeinschaft f größer sein als die Qualität von f′.

6. Falls ST (F) > ST (F′) gilt, dann soll die Qualität der Partition F größer sein als die Qualität von F′.

Definition 19 Gegeben sei eine Fahrgemeinschaft f ⊆ P (|f| ≥ 1), ein Maximalparameter M = (c_{A}, c_{U}, c_{P}) ∈ (IR^{+})^{3} und ein Bewertungsparameter B = (b_{A}, b_{U}, b_{P}) ∈ (IR^{+})^{3}, dann heißt

ST (f) = \{ \begin{matrix}b_{A}(c_{A} − AA(f)) + b_{U}(c_{U} − U_{z}(f)) + b_{P} |f| & falls & C(f) ≤ M \\ 0 & sonst \end{matrix}

die Stabilität von f.

Definition 20 Gegeben sei ein Maximal-, ein Bewertungsparameter (M, B) und eine Partition F = {f_{1}, f_{2}, …, f_{m}} von P, dann heißt

ST (F) = ∑_{i=1}^{m} ST (f_{i})^{2}

die Stabilität von F.

Bem. • Die obigen Anforderungen 1 - 4 ergeben sich direkt aus den Definitionen für

die Stabilität der Fahrgemeinschaften und der Partitionen.

• Falls die Fahrgemeinschaft f größer als die Fahrgemeinschaft f′ ist, eine geringere Abweichung der Arbeitszeiten und einen geringeren Umweg besitzt, ist die Stabilität größer, wie aus der Definition hervorgeht (ST (f) > ST (f′)).

• Durch das Quadrat in der Definition 20 sichern wir zu, daß die Personenanzahl der einzelnen Fahrgemeinschaften bei der Beurteilung von zwei Partitionen (F = {f_{1}, f_{2}, …, f_{m}}, F′ = {f′_{1}, …, f′_{m′}}) eine Rolle spielt. Hätten wir die Stabilität einer Partition F als ST′(F) = ∑_{i=1}^{m} ST (f_{i}) definiert, hätte gegolten:

ST′(F) = b_{P} |P | + ∑_{i=1}^{m} (b_{A}(c_{A} − AA(f_{i})) + b_{U}(c_{U} − U(f_{i})))

Die Maximierung der Stabilität von Partitionen hätte dann immer zur trivialen Partition F = {{p_{1}}, {p_{2}}, …, {p_{|P |}}} geführt. Für den Bewertungsparameter B = (0, 0, 1) gilt:

ST (F) > ST (F′) ⟺ ∑_{i=1}^{m} |f_{i}|^{2} > ∑_{i=1}^{m′} |f′_{i}|^{2}

Zur Veranschaulichung betrachten wir das Beispiel in Abbildung 23 auf Seite 62. Für den Maximalprameter M = (0, 2, 2) und den Bewertungsparameter B = (0, 1, 6) ergeben sich folgende Stabilitäten für die Partitionen F_{0} = {{a}, {b}, {c}, {d}}, F_{1} = {{a, b}, {c, d}} und F_{2} = {{a}, {b, c}, {d}}:

\begin{matrix}ST (F_{0}) = & 4ST^{2}(\{a\})  = & 256, \\ ST (F_{1}) = & 2ST^{2}(\{a, b\})  = & 288, \\ ST (F_{2}) = & 2ST^{2}(\{a\}) + ST^{2}(\{b, c\}) = & 272 \end{matrix}

Definition 21 Eine Partition F′ = {f′_{1}, …, f′_{m′}} läßt sich durch eine Personenumsetzung aus F = {f_{1}, …, f_{m}} bilden, falls

• m = m′

\begin{matrix}∃_{f_{i},f_{j}∈F;|f_{i}|>1} ∃_{f′_{k},f′_{l}∈F′} & f_{i}\\{p\} = f′_{k} ∧ f_{j} ∪ \{p\} = f′_{l} \\ ∀_{k∈\{1,2,...,m\}\\{i,j\}} ∃_{f′∈F′} & f_{k} = f′ \end{matrix}

• m′ = m + 1

\begin{matrix}∃_{f_{i}∈F;|f_{i}|>1} ∃_{f′_{k},f′_{l}∈F′} & f_{i}\\{p\} = f′_{k} ∧ \{p\} = f′_{l} \\ ∀_{k∈\{1,2,...,m\}\\{i\}} ∃_{f′∈F′} & f_{k} = f′ \end{matrix}

• m′ = m − 1

\begin{matrix}∃_{f_{i},f_{j}∈F;|f_{i}|=1} ∃_{f′_{k}∈F′} & f_{i} ∪ f_{j} = f′_{k} \\ ∀_{k∈\{1,2,...,m\}\\{i,j\}} ∃_{f′∈F′} & f_{k} = f′ \end{matrix}

Definition 22 Eine Folge von Partitionen F_{1}, F_{2}, …, F_{m} heißt eine Partitionenfolge, wenn gilt:

∀_{i∈{1,...,m}} F_{i+1} läßt sich durch eine Personenumsetzung aus F_{i} bilden

Definition 23 Für zwei Partitionen F, F′ von P heißt

d(F, F′) = min{k|∃ eine Partitionenfolge F, F_{1}, F_{2}, …, F_{k−1}, F′}

der Abstand von F und F′. Falls F = F′, ist der Abstand Null (d(F, F) = 0).

Bem. F_{0} = {{p_{1}}, {p_{2}}, …, {p_{n}}} sei eine Partition von P = {p_{1}, …, p_{n}} , dann gilt für alle anderen Partitionen F von P: d(F_{0}, F) ≤ |P |. Dies macht man sich sofort klar, wenn man die einzelnen Fahrgemeinschaften von F nur sukzessive durch Personenumsetzungen aus F_{0} aufbaut. Da der Abstand von Partitionen symmetrisch ist, gilt somit für alle Paare von Partitionen F, F′:

d(F, F′) ≤ 2|P |

Definition 24 Eine Partitionenfolge F_{1}, F_{2}, …, F_{m} heißt monoton steigend, wenn gilt:

∀_{i∈{2,3,...,m}} ST (F_{i−1}) ≤ ST (F_{i})

und streng monoton steigend, wenn gilt:

∀_{i∈{2,3,...,m}} ST (F_{i−1}) < ST (F_{i})

Eine Partition F heißt maximal, wenn gilt:

∀_{Partitionen F′,F′≠F} ST (F′) ≤ ST (F)

Satz 7 Für eine maximale Partition F_{max} von P gibt es nicht unbedingt eine monoton steigende Partitionenfolge F_{1}, F_{2}, …, F_{k−1}, F_{max} für F_{1} = {{p_{1}}, {p_{2}}, …, {p_{|P |}}}.

Bew. Wir zeigen die Aussage an einem kleinen Beispiel. Gegeben sei P = {a, b, c}, ein Maximalparameter M = (0, 2, 3) und ein Bewertungsparameter B = (0, 1, 3). Für die Umwege gelte:

U({a, b, c}) = 2,
U({a, b}) = U({a, c}) = U({b, c}) = 1,

Es ergeben sich dann für die Stabilitäten folgende Werte:

ST ({{a, b, c}}) = 81,
ST ({a}, {b}, {c}}) = 75,
ST ({{a, b}, {c}} = ST ({{a, c}, {b}}) = ST ({{a}, {b, c}}) = 74,

Folglich gibt es keine monotone Partitionenfolge von F_{1} = {{a}, {b}, {c}} nach F_{max} = {{a, b, c}}.

Es gibt also maximale Partitionen, die nicht durch Personenumsetzungen und sukzessive Verbesserungen der Stabilität erreicht werden können.

4 Geometrische Algorithmen

Gegeben sei eine Punktemenge S in einem euklidischen Raum IR^{d}. Für p ∈ S sollen folgende Anfragen effizient beantwortet werden:

• Einfügen(p)

• Löschen(p)

• Suche(p)

• Bereichsuche(x, y) : {q| q ∈ S, x, y ∈ IR^{d} , ∀_{i∈{1,2,...,d}} x_{i} ≤ q_{i} ≤ y_{i}}

• c-Paare : {(p′, q)| p′, q ∈ S, p′ ∈ U_{c}(q)}

Wir unterscheiden bei dem Aufwand der einzelnen Operationen zwischen dem Suchaufwand und dem Wiedergabeaufwand, die zusammen den Aufwand zur Berechnung einer Operation bestimmen (SA() + W A() = A()). Dies ist sinnvoll, da der Aufwand zur Berechnung der Bereichsuche() mindestens von der Größe der Menge S′ ⊆ S, die im entsprechenden Bereich liegt, ist. Für die folgenden Algorithmen gilt, daß der Wiedergabeaufwand immer von der Größe der berechneten Menge ist. Wir berechnen den Aufwand in Abhängigkeit der Größe von S und der Anzahl der Dimensionen [Preparata 85] [Mehlhorn(3) 84].

Da wir häufig Bedingungen an die Verteilung der Punktemengen S ⊆ IR^{d} stellen können, definieren wir den Aufwand auch in Abhängigkeit der speziellen Punktemenge.

Definition 25 Gegeben sei eine Menge S ⊆ IR^{d} und eine Operator op(). Die Anzahl von Berechnungsschritten, die op() zur Berechnung einer Menge S′ ⊆ S mit |S′| = k durchführt, heißt: A(S, d, op()) = SA(S, d, op()) + k, wobei mit SA() der Suchaufwand bezeichnet ist. Der maximale Aufwand ist nur noch abhängig von der Größe der Menge S und d.

A(N, d, op()) := max{A(S, d, op())|S ⊇ IR^{d} , |S| = N}  (4)
SA(N, d, op()) := max{SA(S, d, op())|S ⊇ IR^{d} , |S| = N}  (5)

Definition 26 Eine Punktemenge S im euklidischen Raum IR^{d} hat die Spärlichkeit c ∈ IN für δ > 0, wenn alle d-dimensionalen Würfel mit Kantenlänge 2δ höchstens c Punkte aus S enthalten.

4.1 Algorithmus für δ-Paare

In [Preparata 85] wird der folgende Algorithmus als Fixed Radius Nearest Neighbour Report in Sparse Set vorgestellt. Wir werden ihn im weiteren NN nennen.

geg. Eine Punktemenge S ⊂ IR^{d} mit Spärlichkeit c für δ. ges. Alle δ-Paare aus S.

Algorithmus NN:

1. Bestimme die Schnittebene l und teile die Punktemenge S in drei Mengen S_{1}, S_{2} und S_{δ} mit: S = S_{1} ˙∪S_{2}.

2. Löse NN für S_{δ} in d − 1 Dimensionen.

3. Löse NN für S_{1} und S_{2} in d Dimensionen.

Definition 27 l sei eine d − 1 dimensionale Hyperebene, die im Raum IR^{d} senkrecht zur Koordinate K durch den Punkt l_{k} verläuft. Dann heißt

U_{δ}(l) = {x|x ∈ IR^{d}, |x_{k} − l_{k}| ≤ δ}

die δ-Umgebung von l.

Die Existenz der Hyperebene l, die obige Bedingung erfüllt, wird durch Satz 8 nachgewiesen.

Satz 8 Für eine Menge S ⊂ IR^{d} von N Punkten mit Spärlichkeit c für δ gibt es eine Hyperebene l senkrecht zu einer Koordinatenachse, für die folgendes gilt:

1. Beide Mengen S_{1} und S_{2}, die jeweils auf einer Seite von l liegen, beinhalten mindestens \frac{N}{4d} Punkte aus S.

2. In der δ-Umgebung von l liegen höchstens dcN^{\frac{d−1}{d}} Punkte aus S.

Bew. Wir beweisen die Aussage nur für 2 Dimensionen. Durch Induktion ergibt sich das allgemeine Resultat.

• Suche in beiden Dimensionen ein Intervall [x_{1}, x_{2}], [y_{1}, y_{2}], so daß N/8 Punkte aus S größer als x_{2} und y_{2} und N/8 Punkte kleiner als x_{1} und y_{1} sind.

• Suche innerhalb der beiden Intervalle das längste Intervall [x′_{1}, x′_{2}] oder [y′_{1}, y′_{2}], das 2cN^{1/2} Punkte aus S enthält.

• Von diesen längsten Intervallen sei γ = x′_{2} −x′_{1} o.B.d.A. die Länge des längsten Intervalls.

C_{x} ⊆ S enthalte alle Punkte, deren X-Koordinaten innerhalb von [x_{1}, x_{2}] liegen. Die Hyperebene l, die senkrecht auf der X-Achse steht und durch den Punkt \frac{x′_{1}+x′_{2}}{2} verläuft, erfüllt obige Bedingungen (s. Abb. 5).

Widerspruchsbeweis: Annahme γ < 2δ. Dies bedeutet, daß jeder horizontale oder vertikale Streifen der Breite 2δ, der innerhalb von [x_{1}, x_{2}] oder [y_{1}, y_{2}] liegt, mehr als 2cN^{1/2} Punkte enthält. Wenn dies nicht so wäre, hätten wir γ größer gewählt.

⌊\frac{(x_{2} − x_{1})}{2δ}⌋2cN^{1/2} < |C_{x}| = 3/4N

Somit ergibt sich:

⌊\frac{(x_{2} − x_{1})}{2δ}⌋ < \frac{3}{8c}N^{1/2}

Dasselbe gilt auch für (y_{2} − y_{1}). Im Rechteck R gibt es höchstens ⌈\frac{(x_{2}−x_{1})}{2δ}⌉⌈\frac{(y_{2}−y_{1})}{2δ}⌉ Quadrate der Seitenlänge 2δ. Jedes dieser Quadrate enthält höchstens c Punkte.

[figure: Y; X; R; C_{x}; S_{δ}; \frac{N}{8} Punkte; S_{1}; S_{2}; y_{2}; l; \frac{N}{8} Punkte; x_{1}; x′_{1}; x′_{2}; x_{2}; y_{1}; 2δ]

Abbildung 5: Veranschaulichung zum Satz 8.

⌈\frac{(x_{2} − x_{1})}{2δ}⌉ ⌈\frac{(y_{2} − y_{1})}{2δ}⌉ c ≤ (⌊\frac{(x_{2} − x_{1})}{2δ}⌋ + 1)(⌊\frac{(y_{2} − y_{1})}{2δ}⌋ + 1)c
< \frac{3}{8c}N^{1/2} + 1)^{2}c

Das Maximum wird für c = 1 erreicht. Folglich enthält R höchstens 2(3/8)^{2}N Punkte (|R| ≈ 0.28N). Da N/4 Punkte außerhalb vom Intervall [x_{1}, x_{2}] und N/4 Punkte außerhalb vom Intervall [y_{1}, y_{2}] liegen, können höchstens N/2 Punkte außerhalb von R liegen. Dies führt zum Widerspruch. Wegen γ ≥ 2δ, enthält die δ-Umgebung von der Hyperebene l höchstens 2cN^{1/2} Punkte.

1. Berechnung der Hyperebene l und der Mengen S_{1}, S_{2} und S_{δ}.

• Vorsortierung von S bzgl. aller d Koordinaten mittels Quicksort [Ottmann 93] in die Felder F_{i} (i ∈ {1, …, d}).

A(N, d, Vorsortierung) ∈ O(dN log N)

• Bilde eine Menge M von d Intervallen [u_{i}, o_{i}] (i ∈ {1, …, d), so daß auf jeder Seite außerhalb des Intervalls mindestens \frac{N}{4d} Punkte liegen.

A(N, d, Bildung von M) ≤ d

• Suche aus allen Intervallen aus M das längste Teilintervall [u′_{i}, o′_{i}], so daß genau ⌊cdN^{\frac{d−1}{d}} ⌋ darin liegen.

A(N, d, Längstes Intervall aus M) ≤ dN

• Wenn das längste Intervall [u, o] bzgl. der Koordinate K gewählt wurde, verläuft die Hyperebene l senkrecht zur Koordinate K durch den Punkt \frac{u+o}{2} auf der Koordinatenachse K.

• Mittels der d sortierten Felder F_{i} (i ∈ {1, …, d}) für S werden jeweils d neue Felder F_{i}^{1}, F_{i}^{2} und F_{i}^{δ} für die Mengen S_{1}, S_{2} und S_{δ} gebildet.

A(N, d, Bilde (S_{1}, S_{2}, S_{δ})) ≤ dN

2. Berechnung von S_{δ} in d-1 Dimensionen. Angenommen die Hyperebene l verläuft genau senkrecht zur Koordinate K durch den Punkt l_{k}, dann sind nicht alle Punkte p, q ∈ δ-Umgebung(l) mit: |p_{i} − q_{i}| ≤ δ für i ∈ {1, …, d}\K δ-Paare. Die δ-Umgebung hat die Breite 2δ, daher bilden wir für alle Punkte s ∈ S_{δ} eine Projektionsliste P (s): trage l_{k} − s_{k} auf P (s) ein. Dann löse NN für S_{δ} in den restlichen Dimensionen.

3. Rekursionsabruch

(a) d = 1 Die Menge S′ ⊂ S sei im Feld F′ bzgl. der Koordinate k sortiert und der Operator ≈ vergleiche zwei Projektionslisten miteinander und gebe TRUE aus, wenn die beiden Punkte in einer δ-Umgebung liegen. Er benötigt höchstens d−1 Berechnungsschritte, da die Projektionslisten höchstens diese Länge haben.

FOR i := 1 TO |S′| DO j := i + 1;

WHILE F′[j]_{k} − F′[i]_{k} ≤ δ DO

IF P (F′[j]) ≈ P (F′[i]) THEN (F′[j], F′[i]) ist ein δ-Paar ENDIF; j := j + 1);

ENDWHILE; ENDFOR;

A(|S′|, 1, Rekursionsabruch) ≤ cd|S′|

(b) |S′| < K für 8 < K < 100. Wenn die Teilmenge S′, die auf δ-Paare zu überprüfen ist, zu klein wird, wird der Overhead durch Organisationsmaßnahmen beim angegebenen Verfahren für NN zu groß. Eine Trivialstrategie, die lediglich alle Punktepaare aus S′ miteinander vergleicht, benötigt schließlich auch nur d\frac{|S′|(|S′|−1)}{2} Operationen.

4. Aufwandsabschätzung Den Geamtaufwand für den Algorithmus NN bezeichnen wir als A(N, d), wenn es sich um eine Punktemenge der Größe N im d-dimensionalen Raum handelt. Für \frac{1}{4d} ≤ α ≤ \frac{4d−1}{4d} gilt:

\begin{matrix}A(N, d) = & A(αN, d) + A((1 − α)N, d) + dN + A(cdN^{\frac{d−1}{d}} , d − 1) \\ A(N, 1) = & cdN \\ A(1, d) = & 1 \end{matrix}

O.B.d.A. sei N = (\frac{1}{α(1−α)})^{\frac{n}{2}} (n ∈ IN). Wir führen nur den Fall d = 2 durch. Die Verallgemeinerung folgt durch Induktion.

A(N, 2) = A(αN, 2) + A((1 − α)N, 2) + 2N + \underbrace{A(c2\sqrt{N}, 1)}_{c^{2}2^{2}\sqrt{N}}

= A(α^{2}N, 2) + 2A(α(1 − α), 2) + A((1 − α)^{2}, 2) + 4N

+2^{2}c^{2}\sqrt{N}(1 + \sqrt{α} + \sqrt{1 − α})

⋮

= ∑_{k=0}^{n} \binom{n}{k}A(α^{n−k}(1 − α)^{k}N, 2) + 2(n + 1)N  (6)

+ ∑_{k=0}^{n−1} ∑_{i=0}^{k} c^{2}2^{2}\sqrt{N}\binom{k}{i}\sqrt{α^{k−i}(1 − α)^{i}}

< \underbrace{∑_{k=0}^{n} \binom{n}{k}}_{=2^{n}<N} +2(n + 1)N + 2^{2}c^{2}\sqrt{N} \underbrace{∑_{k=0}^{n−1}(\sqrt{α} + \sqrt{1 − α})^{k}}_{<\sqrt{N}}  (7)

∈ O(2N log N + 2^{2}c^{2}N)
A(N, d) ∈ O(dN log N + d^{d}c^{d}N)

Man beachte in Zeile 6:

α^{n−k}(1 − α)^{k} ≤ (α(1 − α))^{\frac{n}{2}} = \frac{1}{N}

sowie in Zeile 7:

\begin{aligned}& \frac{(\sqrt{α}+\sqrt{1−α})^{n}−1}{\sqrt{α}+\sqrt{1−α}−1} & < & 4\sqrt{N} = 4(\frac{1}{α(1−α)})^{\frac{n}{4}} \\ ⟹ & \frac{1}{4}(\underbrace{(\sqrt{α} + \sqrt{1 − α})(α(1 − α))^{\frac{1}{4}}}_{≤1 für α∈(0,1)})^{n} & < & \underbrace{\sqrt{α} + \sqrt{1 − α} − 1}_{>1/4 für α∈(1/8,7/8)} \end{aligned}

4.2 k-D-Bäume

k-D-Bäume sind trinäre Bäume, die Punkte aus dem k-dimensionalen Raum enthalten. Es besteht eine bijektive Beziehung zwischen den Knoten eines k-D-Baums und den Punkten, die darin gespeichert sind.

Definition 28 Jedem Knoten v in einem k-D-Baum ist durch die bijektive Funktion P genau ein Punkt p ∈ S zugeordnet (P (v)). Wir schreiben für die einzelnen Koordinaten von dem zugeordneten Punkt auch P_{1}(v), …, P_{k}(v).

Wir gehen aus vom 2-dimensionalen Fall und werden zeigen, daß die Verallgemeinerung auf den k-dimensionalen Fall keine Probleme bereitet.

Wie wird die Operation Bereichsuche(x, y) im 1-dimensionalen Raum effizient realisiert? Wir ordnen die Punkte aus S in einem binären Suchbaum an und suchen einen der beiden Randpunkte des Intervalls [x, y]. Dann geben wir alle Punkte, die zwischen diesen Randpunkten liegen aus. Die Effizienz dieses Verfahrens hängt wesentlich davon ab, wie ausgeglichen der Suchbaum ist. Wenn wir von einem vollständig ausgeglichenen Suchbaum ausgehen, und annehmen, daß Bereichsuche(x, y) eine Menge der Grösse k berechnet, ergibt sich für den Such- und Wiedergabeaufwand: SA(|S|, 1, Bereichsuche(x,y)) ∈ O(log |S|) , W A(N, 1, Bereichsuche(x,y)) ∈ Θ(k). Der Gesamtaufwand ist also: A(|S|, 1, Bereichsuche(x,y)) ∈ O(log |S| + k). Diese Methode der Zweiteilung der gegebenen Menge S versuchen wir nun im 2-dimensionalen Fall einzusetzen. Im 1-dimensionalen Fall ist die Wurzel eines jeden Teilbaums des vollständig ausgeglichenen binären Suchbaums der Median aller Knoten dieses Teilbaums.

Wir unterscheiden beim Aufbau des 2-D-Baums T, der alle Punkte aus S enthält, abwechselnd von Level zu Level des Baums nur eine Koordinate. Auf dem 2i−ten Level werden alle Punkte nur nach X-Koordinate und auf dem (2i+1)-ten Level nach der Y-Koordinate unterschieden (i ∈ \{1, 2, …, ⌊\frac{H(T)}{2}⌋\}). Die Wurzel eines jeden Teilbaums T′ von T ist also je nach dem Level der Median(1, T′) oder der Median(2, T′).

Definition 29 Gegeben sei ein k-dimensionaler Würfel K = [a_{1}, b_{1})×⋯ [a_{k}, b_{k}) und eine (k-1)-dimensionale Hyperebene H = [a_{1}, b_{1}) × ⋯ × [a_{i−1}, b_{i−1}) × h × [a_{i+1}, b_{i+1}) × ⋯ × [a_{k}, b_{k}), wobei gilt: H ⊆ K. Dann ist:

> (H, K) := {x ∈ K|x_{i} > h}
< (H, K) := {x ∈ K|x_{i} < h}
= (H, K) := H

Zur Veranschaulichung dieser Definition siehe Abb. 6.

[figure: H; K; > (H, K); < (H, K)]

Abbildung 6: Der Körper K und die Hyperebene H aus Definition 29 im 2-dimensionalen Raum.

Definition 30 Jedem Knoten v eines k-D-Baums T ist eine Region R(v), die das kartesische Produkt von i Intervallen ist, zugeordnet (i ∈ {1, …, k}). Falls v die Wurzel von T ist, gilt: R(v) := IR^{k}. Die Folgeknoten von w ∈ T bezeichnen wir als w. >, w. <, w. =.

\begin{matrix}F alls v = w. > : & R(v) := > (l(w), R(w)) \\ F alls v = w. < : & R(v) := < (l(w), R(w)) \\ F alls v = w. = : & R(v) := = (l(w), R(w)) \end{matrix}

Jedem Knoten v ist durch l(v) eine i-dimensionale Hyperebene, die senkrecht zu k − i Koordinatenachsen verläuft, zugeordnet (i ∈ {1, …, k − 1}). Wenn gilt: R(v) = [a_{1}, b_{1}) × ⋯ × [a_{i+1}, b_{i+1}) × a_{i+2} × ⋯ × a_{k}, und im Level vom Knoten v wurde der Median(j,) (j ∈ {1, …, i + 1}) berücksichtigt, dann ist:

l(v) := [a_{1}, b_{1}) × ⋯ × P_{j}(v) × ⋯ × [a_{i+1}, b_{i+1}) × a_{i+2} × ⋯ × a_{k}

die Splitlinie von v.

Es ist zu beachten, daß für alle Knoten v ∈ Level(i) zuerst eine Region R(v) und erst dann eine Splitlinie l(v) existiert, so werden sukzessive von Level(0) bis Level(H(T)) die Regionen und Splitlinien aller Knoten bestimmt. Wir geben nun einen Algorithmus zum Aufbau eines 2-D-Baums aus einer Menge S ⊆ IR^{2} an.

NS := S; L := 0; v := Median(1, S); R(v) := IR^{2}; l(v) := P_{1}(v) × IR; S(v) := S; NS := S(v)\{P (v)}; WHILE |NS| > 0 DO

L := L + 1;

FOR v ∈ Level(L) DO
IF |S(v)| > 1
THEN Bilde Nachfolger v. <, v. >, v. =

R(v. <) :=< (l(v), R(v));

S(v. <) := S(v) ∩ {s ∈ S|s ∈ R(v. <)};

analog für v. > und v. =

IF L ist gerade und es gelte: R(v) = (u_{1}, o_{1}) × (u_{2}, o_{2})

THEN P (v. <) := Median(2, S(v. <)); l(v. <) := (P_{1}(v), o_{1}) × P_{2}(v. <); P (v. >) := Median(2, S(v. >)); l(v. >) := (u_{1}, P_{1}(v)) × P_{2}(v. >); P (v. =) := Median(2, S(v. =)); l(v. =) := P_{1}(v) × P_{2}(v. =);

ELSE analog für Median(1,) ENDIF; NS := NS\{P (v. <), P (v. >), P (v. =)};

ENDIF; ENDFOR;

ENDWHILE;

Für 1-dimensionale Regionen R(v) müssen in der innersten IF-Schleife gesonderte Abfragen unternommen werden, die sich aber prinzipiell nicht unterscheiden. In Abb. 7 ist für ein Beispiel ein 2-D-Baum dargestellt.

Die Mengen S(v) werden durch Felder der Länge |S(v)| dargestellt. Wenn v ∈ Level(i) gilt, dann bezeichnen wir das zugehörige Feld als F (i, v). Wenn i gerade ist, enthält F (i, v)

[figure: a; b; c; d; e; f; g; h; >; >; <; <; <; >; d; e; c; a; b; =; h; g; f; =; =]

Abbildung 7: Punktemenge mit zugehörigem 2-D-Baum.

alle Knoten aus S(v) bzgl. der Y-Koordinate sortiert, im anderen Fall sind die Knoten bzgl. der X-Koordinate sortiert. Es ist also der Median(l, S(v)) (für l ∈ {1, 2}) durch einen Zugriff auf F (i, v) zu berechnen. F (i, v) selbst berechnen wir aufgrund vorher berechneter Felder F (i−2,) in |S(v)| Schritten. Wir spezifizieren die Berechnungen im einzelnen: O.B.d.A. sei |S| = 2^{n}−1 und für alle Punktepaare (p, q) ∈ S gelte: p_{i} ≠ q_{i}(i ∈ {1, 2}). D.h. der aufzubauende 2-D-Baum kann ein binärer Baum sein, da keine =-Zeiger nötig sind. Die Verallgemeinerung ist nicht schwieriger, sondern nur aufwendiger zu formalisieren. Es gilt weiterhin:

• |Level(i)| = 2^{i−1}

• Die Anzahl aller Punkte aus Feldern des Levels i ist: |S| − ∑_{j=0}^{i−2} 2^{j} = 2^{n} − 2^{i−1}.

• Jedes Feld F (i, v) enthält \frac{2^{n}−2^{i−1}}{2^{i−1}} = 2^{n−i+1} − 1 Punkte.

Jedes Feld F (i, v) wird durch das Feld F (i−2, w) und den Median(l, S(u)) gebildet, wenn w der Großvaterknoten und u der Vaterknoten von v ist (l ∈ {1, 2}). Wir benutzen den Median(1, S(u)), falls i gerade ist, ansonsten den Median(2, S(u)).

Es gelte: w. < = u; u. < = v1; u. > = v2, dann wird F (i, v1) und F (i, v2) wie folgt berechnet.

Median(l, S(u)) := F (i − 1, u)[2^{n−i+2}]; z1 := 1; z2 := 1; FOR t := 1 TO 2^{n−i+2} DO

IF F (i − 2, w)[t] < Median(l, S(u))

THEN F (i, v1)[z1] := F (i − 2, w)[t]; z1 := z1 + 1;
ELSE F (i, v2)[z2] := F (i − 2, w)[t]; z2 := z2 + 1;

ENDIF; ENDFOR;

Da für den Aufbau der Felder F (i,) nur die Felder F (i−2,) benötigt werden, ist es ausreichend zu jedem Zeitpunkt nur die Felder von drei aufeinanderfolgenden Leveln im Speicher zu halten. Zu Beginn des Aufbaus des 2-D-Baums muß die Menge S bzgl. der X- und der Y-Koordinate sortiert werden. Dies benötigt mittels Quicksort weniger als O(2|S| log |S|) Operationen [Ottmann 93]. Da in jedem Level mit obigem Verfahren höchstens |S| Operationen durchgeführt werden, ergibt sich für den Aufwand bei log |S| Leveln:

A(|S|, 2, Aufbau 2-D-Baum) ∈ O((2 + 1)|S| log |S|)

Definition 31 Ein k-D-Baum heißt ein idealer Baum, wenn gilt: H(T) ≤ ⌈log |T |⌉.

Korollar 2 Für eine Menge S ⊂ IR^{k} gilt für den Aufwand zum Aufbau eines idealen k-D-Baums:

A(|S|, k, Aufbau k-D-Baum) ∈ Θ((k + 1)|S| log |S|)

Weiterhin gilt dann:

A(|S|, k, Suche(p)) ≤ log |S|
A(|S|, k, Einfügen(p)) ≤ log |S| + 1
A(|S|, k, Löschen(p)) ≤ log |S| + (k + 1)|S(p)| log |S(p)|

Bew. Bei der Suche wird nur der Baum von der Wurzel bis zum entsprechenden Knoten durchlaufen, während beim Einfügen noch der entsprechende Knoten eingetragen wird. Beim Löschen haben wir eine Suche mit anschließendem Neuaufbau vom gesamten Unterbaum vom jeweiligen Knoten durchzuführen.

Bereichsuche(x, y)  wird  durch  den

Aufruf der untenstehenden Funktion Überdeckung(w, R) berechnet, wobei w die Wurzel des k-D-Baums T und R = [x_{1}, y_{1}] × [x_{2}, y_{2}] ist.

Überdeckung (v: Knoten; R : Region) IF P (v) ∈ R THEN gebe P (v) aus ENDIF; IF |S(v)| > 1 THEN

IF R(v. >) ∩ R ≠ ∅ THEN Überdeckung(v. >, R) ENDIF; IF R(v. <) ∩ R ≠ ∅ THEN Überdeckung(v. <, R) ENDIF; IF R(v. =) ∩ R ≠ ∅ THEN Überdeckung(v. =, R) ENDIF;

ENDIF; ENDÜberdeckung;

Beim Aufbau eines k-D-Baums werden die k Koordinaten zyklisch unterschieden, so daß von k aufeinanderfolgenden Leveln k verschiedene Koordinaten bei der Bildung des Medians berücksichtigt wurden.

Die Idee zu folgendem Theorem findet man in [Lee 77], [Preparata 85] und [Mehlhorn(3) 84].

Theorem 1 T sei ein idealer d-D-Baum für S ⊆ IR^{d} (|S| = n). Es gilt dann:

A(|S|, d, Bereichsuche()) ∈ O(d4^{d}n^{1−1/d} + d|S′|)

Bew. Wir beweisen den Sachverhalt aus Gründen der Anschauung vorerst für den 2dimensionalen Fall und verallgemeinern das Resultat. Es sei R = [l_{0}, h_{0}] × [l_{1}, h_{1}] die befragte Region, und T′ der Teilbaum von T, der alle Knoten enthält, die während der Beantwortung der Anfrage Bereichsuche(R) besucht werden müssen.

v ∈ T′ ⟺ R(v) ∩ R ≠ ∅

Wir unterscheiden bzgl. T′ zwei Knotenmengen X und Y:

\begin{aligned}X & = & \{v|v ∈ T′, R(v) ⊆ R\} \\ Y & = & \{v|v ∈ T′, R(v) ∩ R ≠ ∅ ∧ R(v) − R ≠ ∅\} \end{aligned}

Die beiden Knotenmengen sind disjunkt. Für alle Knoten v ∈ X gilt, daß die Söhne von v ebenfalls in X liegen. Da alle Knoten von X ausgegeben werden, gilt |X| ≤ |S′|. Wegen der Berechnung aller Koordinaten sind für die Menge X maximal d|S′| Operationen auszuführen.

Um |Y | nach oben abzuschätzen, zählen wir nun alle Knoten v, so daß R(v) entweder R enthält oder mindestens einmal den Rand von R schneidet.

Definition 32 Gegeben sei der d-dimensionale Würfel R = [l_{0}, h_{0}] × [l_{1}, h_{1}] × ⋯ × [l_{d−1}, h_{d−1}], eine Koordinate k ∈ {0, 1, …, d − 1} und ein c ∈ {l_{k}, h_{k}}, dann heißt

\begin{aligned}L & = & \{x = (x_{0}, x_{1}, …, x_{d−1}) ∈ R| x_{k} = c, \\ & & ∀_{m∈\{0,1,...,k−1,k+1,...,d−1\}} l_{m} ≤ x_{m} ≤ h_{m}\} \end{aligned}

ein Rand von R.

Bem. Wir machen uns die Definition am Beispiel deutlich. Gegeben sei der Würfel R = [1, 3] × [2, 4] × [4, 6] im 3-dimensionalen Raum IR^{3}. Dann gibt es sechs Ränder von R, beispielsweise

L = {x ∈ R| x_{1} = 3, 2 ≤ x_{2} ≤ 4, 4 ≤ x_{3} ≤ 6}

Es sei:

t_{max} = max_{L ist ein Rand von R} |{v ∈ Y |R(v) ∩ L ≠ ∅ ∧ R(v) − L ≠ ∅}|

Den Rand von L von R, der das Maximum erzeugt, bezeichnen wir als L_{max}. Im 2-dimensionalen Fall besteht der Rand von R aus vier Strecken.

O.B.d.A. sei L_{max} = {(x, y)|x = l_{0}, l_{1} ≤ y ≤ h_{1}}. Dann gilt:

|Y | ≤ 4t_{max} + log n  (8)

Den Term log n müssen wir berücksichtigen, da es maximal log n Knoten v geben kann, mit: R(v) ⊃ R. Wir unterscheiden innerhalb von Y die Knoten, die L schneiden, ohne L zu überdecken, nach ihrer Dimensionalität:

W = {v|v ∈ Y, R(v) ∩ L ≠ ∅, R(v) − L ≠ ∅,

R(v) ist 2-dimensional }

Z = {v|v ∈ Y, R(v) ∩ L ≠ ∅, R(v) − L ≠ ∅,

R(v) ist nicht 2-dimensional }

t_{max} = |W | + |Z|

Auf dem Pfad von der Wurzel zu einem Knoten aus W kommt also kein =-Zeiger vor, während auf einem Pfad von der Wurzel zu einem Knoten aus Z mindestens ein =-Zeiger vorkommt. Wir betrachten die Menge W nun bzgl. jedes Levels des Baumes T, und W_{k} bezeichnet die Teilmenge von W, die alle Knoten auf dem Level k enthält (W = ⋃_{0≤k≤log n} W_{k}). Für jeden Knoten v ∈ W_{k} gibt es auf dem Level k + 2 höchstens zwei Söhne aus W, wie in der Abbildung 8 verdeutlicht wird. Wir erhalten also eine Rekursionsgleichung: |W_{k+2}| ≤ 2|W_{k}|, mit der Anfangsbedingung: |W_{0}| ≤ |W_{1}| ≤ 2.

[figure: Reg(b); Reg(a); R; Reg(c); Reg(d); Reg(e); Reg(g); Reg(h); h_{0}; h_{1}; l_{o}; l_{1}; Reg(f); L; X; Y]
Abbildung 8: Veranschaulichung von |W_{k+2}| ≤ 2|W_{k}|
|W_{k}| ≤ 2|W_{k−2}| ≤ ⋯ ≤ 2^{k/2}|W_{0}| ≤ 2 · 2^{k/2}

Nun zählen wir die Knoten z ∈ Z, die Nachfolger der Knoten aus W sein müssen. Angenommen z sei der Nachfolger von w ∈ W_{k}, dann gilt: S(z) ⊆ S(w) und folglich |S(z)| ≤ |S(w)| ≤ \frac{n}{2^{k}}. Wir werden nun zeigen, daß es höchstens log |S(z)| Nachfolger von z geben kann, die L schneiden. Reg(z) entspricht einer horizontalen oder einer vertikalen Linie. Da L eine vertikale Linie ist, liegen im ersten Fall alle Nachfolger von z, deren Region L schneiden, auf einem Pfad im Baum T. Im zweiten Fall schneiden nur die Regionen der Nachfolger von z die Linie L, die einen der Endpunkte ((l_{0}, l_{1}), (l_{0}, h_{1})) enthalten. Siehe in Abb. 9 die Region von Knoten g. Daraus folgt die Behauptung.

[figure: a; b; c; d; e; f; g; h; <; <; <; =; >; >; >; Level k; Level k + 2; Level k + 1]

Abbildung 9: Ausschnitt aus T′ zu Abb. 8

Für die einzelnen Knoten aus T′ gilt:

\begin{matrix}a, c, f, g ∈ & W \\ b, d, e  ∈ & X \\ g  ∈ & Z \end{matrix}

Für die gesamte Menge der Knoten, die L schneiden gilt dann:

|W | + |Z| ≤ ∑_{k=0}^{log n} \underbrace{2 2^{k/2}}_{W_{k}} log \frac{n}{2^{k}}

= 2 ∑_{k=0}^{log n} 2^{k/2} (log n − k)

= 2\sqrt{n} ∑_{k=0}^{log n} 2^{\frac{k−log n}{2}} (log n − k)

= 2\sqrt{n} ∑_{k=0}^{log n} (\frac{1}{\sqrt{2}})^{k} k ∈ O(2\sqrt{n})  (9)

Für die Gesamtzahl der Knoten in T′ erhalten wir:

|T′| ∈ O(2 · 4 · \sqrt{n} + 2|A|)

Wir verallgemeinern dieses Resultat von zwei auf d Dimensionen. Dazu sei R = [l_{0}, h_{0}] × [l_{1}, h_{1}] × ⋯ × [l_{d−1}, h_{d−1}]. Wir betrachten wieder den Teilbaum T′ von T und die Knotenmengen X und Y wie oben. Analog wie im 2-dimensionalen Fall ergibt sich: |X| ≤ d|A|

Zur Abschätzung von |Y | hatten wir den Rand von R betrachtet. Da R ein ddimensionaler Körper im Raum IR^{d} ist, gibt es 2d (d − 1)-dimensionale Ränder von R.

Es gilt analog zur Gleichung (8): |Y | ≤ 2dt_{max} + log n.

Wir unterscheiden zur Berechnung von t_{max} wieder die Knoten nach der Dimensionalität der Regionen, die ihnen entsprechen.

W = {v ∈ Y |R(v) ∩ L_{max} ≠ ∅, R(v) − L_{max} ≠ ∅,

R(v) ist d-dimensional }

Z = {v ∈ Y |R(v) ∩ L_{max} ≠ ∅, R(v) − L_{max} ≠ ∅,

R(v) ist nicht d-dimensional }

Die Knotenmenge W betrachten wir wieder bzgl. jedes einzelnen Levels vom Baum T (W = ⋃_{k=0}^{log n} W_{k}). Für einen Knoten v ∈ W_{k} kann es höchstens 2^{d−1} Knoten in W_{k+d} geben, d.h. höchstens die Hälfte aller Nachfolgerknoten von v aus den nächsten d Ebenen können d-dimensionalen Regionen entsprechen, die L schneiden. Mit der Anfangsbedingung |W_{0}| ≤ |W_{1}| ≤ ⋯ ≤ |W_{d−1}| ≤ d, ergibt sich:

|W_{k}| ≤ 2^{d−1} (2^{k})^{\frac{d−1}{d}}  (10)

Wir beweisen |Y | ≤ d 4^{d}n^{\frac{d−1}{d}} c(d) durch Induktion über d, wobei c(d) einen von n unabhängigen Anteil angibt. Beim Induktionsanfang stützen wir uns auf den bereits berechneten 2-dimensionalen Fall, und beim Induktionsschluß lassen wir die Rekursionsgleichung (10) und die Induktionsbehauptung einfließen.

Induktionsschluß d − 1 ⟼ d

|Y | ≤ 2dt_{max} + log n
t_{max} = |W | + |Z|

Für alle Knoten v ∈ Z benutzen wir die Induktionsbehauptung für |Y |. Diese Knoten müssen Nachfolger von Knoten w ∈ W sein. Da ein Knoten w ∈ W_{k} höchstens \frac{n}{2^{k}} Nachfolger besitzt, ergibt sich:

t_{max} ≤ ∑_{k=0}^{log n} \underbrace{2^{d−1}(2^{k})^{\frac{d−1}{d}}}_{Gl. (10)} \underbrace{(d − 1)2^{2(d−1)} (\frac{n}{2^{k}} )^{\frac{d−2}{d−1}} c(d − 1)}_{Ind.Beh.}

= (d − 1)2^{3(d−1)}n^{\frac{d−1}{d}} c(d − 1) ∑_{k=0}^{log n} (2^{log n})^{\frac{1−d}{d}} (2^{k})^{\frac{d−1}{d}} (2^{log n−k})^{\frac{d−2}{d−1}}

= (d − 1)2^{3(d−1)}n^{\frac{d−1}{d}} c(d − 1) ∑_{k=0}^{log n}(2^{k−log n})^{\frac{1}{d(d−1)}}

= (d − 1)2^{3(d−1)}n^{\frac{d−1}{d}} c(d − 1) \underbrace{∑_{k=0}^{log n} (\frac{1}{2^{\frac{1}{d(d−1)}}} )^{k}}_{≤c}

Die Konstante c sei eine beliebig große Zahl, da für festes d die Reihe

∑_{k=0}^{∞} (_{\frac{1}{2^{\frac{1}{d(d−1)}}}} )^{k} konvergiert.

Damit gilt für die Menge Y:

|Y | ≤ d4^{d}n^{\frac{d−1}{d}} \underbrace{c(d − 1)2^{d−2}(d − 1)c}_{c(d)} + log n

Korollar 3 Wenn für eine Punktemenge S ⊆ IR^{d} (|S| = n) gilt:

∀_{p,q∈S} ∀_{i∈{1,...,d}} p_{i} ≠ q_{i}  (11)

dann folgt für den Aufwand der Bereichsuche() mittels eines d-D-Baums T, wenn S′ ⊆ S die gefundene Menge ist:

A(n, d, Bereichsuche()) < 4d2^{d}n^{\frac{d−1}{d}} + d|S′|

Bew. Wegen Bedingung 11 ist T ein binärer Baum.

Wir beziehen uns auf die Begriffsbildung im Beweis von Theorem 1 und folgen dem selben Prinzip. Es ist nun nicht nötig, innerhalb der Knotenmenge Y die Knoten v, deren Region R(v) den Rand von L_{max} schneiden, nach ihrer Dimensionalität zu unterscheiden, da allen Knoten eine d-dimensionale Region aufgrund der Bedingung 11 zugeordnet ist. Es gilt: |Y | ≤ 2dt_{max} + log n und |X| ≤ d|S′|

t_{max} ≤ |W |
= ∑_{k=0}^{log n} |W_{k}|

\underbrace{≤}_{Gl. 10} ∑_{k=0}^{log n} 2^{d−1}(2^{k})^{\frac{d−1}{d}}

= 2^{d−1}n^{\frac{d−1}{d}} ∑_{k=0}^{log n}(2^{k−log n})^{\frac{d−1}{d}}

= 2^{d−1}n^{\frac{d−1}{d}} \underbrace{∑_{k=0}^{log n}(2^{\frac{1−d}{d}})^{k}}_{<∑_{k=0}^{∞}( \frac{1}{\sqrt{2}} )^{k} <4}

Somit folgt: |Y | < 4d2^{d}n^{\frac{d−1}{d}} für d ≥ 2.

Definition 33 Gegeben sei eine Menge S, die in einem 2-D-Baum T gespeichert ist, und ein c > 0, dann heißt für den Knoten v ∈ T :

SP_{c}(v) = {s|s ∈ S , l(v) ∩ U_{c}(s) ≠ ∅}

die Splitmenge.

Satz 9 Gegeben ist eine Menge S mit |S| = N = 2^{m} − 1 Punkten aus U = IR^{2}, die in einem vollständig ausgeglichenen 2-D-Baum T gespeichert ist, und ein c > 0. Es gelte für j ∈ \{0, 1, …, ⌈\frac{m}{2}⌉ − 1\}:

∑_{v∈Level(2j)} |SP_{c}(v)| ≤ 2^{j}\sqrt{N} ∧ ∑_{v∈Level(2j+1)} |SP_{c}(v)| ≤ 2^{j}\sqrt{N}  (12)

Es folgt dann für den Aufwand zur Berechnung von c-Paare:

A(N, 2, c-Paare) ∈ O(N log N)

Bew. Um für eine Umgebung U_{c}(s) (s ∈ S) zu testen, welche Punkte s′ ∈ S in U_{c}(s) liegen, müssen alle Knoten v ∈ T untersucht werden, die mit einem Rechteck R(v) korrespondieren, so daß gilt: U_{c}(s)∩R(v) ≠ ∅. Wir zählen also die Überschneidungen aller Rechtecke, die den Knoten aus T zugeordnet sind, mit den c-Umgebungen aller Punkte aus S.

\begin{matrix}AU(s) = & |\{v|R(v) ∩ U_{c}(s) ≠ ∅, v ∈ T \}| \\ AR(v) = & |\{s|R(v) ∩ U_{c}(s) ≠ ∅, s ∈ S\}| \\ ALR(j) = & ∑_{v∈Levelj} AR(v) \end{matrix}

ASS = ∑_{s∈S} AU(s) = ∑_{v∈T} AR(v) = ∑_{j=0}^{m−1} ALR(j)

Für die Wurzel v von T gilt: R(v) = U. Folglich werden alle c-Umgebungen von ihr überdeckt: ALR(0) = N. Für die weiteren Level gilt:

ALR(0)  = N
ALR(1)  ≤ ALR(0) + ∑_{v∈Level(0)} |SP_{c}(v)|
≤ N + \sqrt{N}
ALR(2)  ≤ ALR(1) + ∑_{v∈Level(1)} |SP_{c}(v)|
≤ N + 2\sqrt{N}
⋮
ALR(2j)  ≤ ALR(2j − 1) + ∑_{v∈Level(2j−1)} |SP_{c}(v)|
≤ ALR(2j − 1) + 2^{j}\sqrt{N}
≤ N + 2\sqrt{N} ∑_{i=0}^{j} 2^{i} − 2^{j}\sqrt{N}
ALR(2j + 1) ≤ ALR(2j) + ∑_{v∈Level(2j)} |SP_{c}(v)|
≤ ALR(2j) + 2^{j}\sqrt{N}
≤ N + 2\sqrt{N} ∑_{i=0}^{j} 2^{i}
≤ N + 2^{j+2}\sqrt{N}

Wir können nun ASS wie folgt nach oben abschätzen:

ASS = ∑_{j=0}^{m−1} ALR(j)
≤ ∑_{j=0}^{m−1}(N + 2^{j/2+2}\sqrt{N})
= mN + 4\sqrt{N} ∑_{j=0}^{m−1} 2^{j/2}
≤ mN + 4\sqrt{N} \frac{2^{m/2}−1}{\sqrt{2}−1}
≤ mN + 16N
∈ O(N log N)

Bem. Die Voraussetzung, die wir in Satz 9 gemacht haben (Gleichung 12), erscheint sehr konstruiert und ebenso schwer zu überprüfen. Anschaulich spiegelt sie eine ’gleichmäßige’ Verteilung aller Punkte aus S wieder, wobei es durchaus vorkommen kann, daß Häufungen von Punkten auftreten. Entscheidend ist, daß jeder vollständige Schnitt durch den Raum im 2-dimensionalen Fall sich nur mit \sqrt{|S|} Rechtecken schneidet, die den Knoten aus dem zugehörigen 2-D-Baum zugeordnet sind. Die Aussage von Satz 9 ist optimal, wenn die Punkte in einem 2-D-Baum organisiert und die Operationen zur Berechnung aller Punkte s′ ∈ U_{c}(s) für jeden Punkt s ∈ S atomar sind, d.h. unabhängig voneinander durchgeführt werden. Dies ergibt sich durch die Aufsummierung aller Pfadlängen.

Beim bisherigen Aufbau eines k-D-Baums haben wir die Knoten in aufeinanderfolgenden Leveln zyklisch nach den k Koordinaten unterschieden. Dies ist nicht immer sinnvoll, da es günstig ist, durch die Splitlinien auch eine starke räumliche Trennung der Punkte zu erreichen.

Splitverfahren: Vorzug In einem k-D-Baum T sei die Menge S(v) und die Region R(v) für einen Knoten v betimmt, dann wird der zugehörige Punkt s ∈ S mit P (v) = s wie folgt berechnet:

sp := max; FOR i := 1 TO kDO

IF |SP_{c}(Median(i, S(v)) ∩ S(v)| < sp THEN P (v) := Median(i, S(v));

sp := |SP_{c}(Median(i, S(v)) ∩ S(v)|;

ENDIF; ENDFOR;

Beim Aufbau eines k-D-Baums für eine Menge S sind folglich an jedem Knoten k Koordinaten zu berücksichtigen. Die Splitmengen lassen sich mittels der Felder F (i,) für alle Knoten eines Levels durch höchstens |S| Operationen berechnen, so daß sich folgender Aufwand ergibt:

A(|S|, k, Aufbau k-D-Baum) ∈ O(2(k + 1)|S| log |S|)

Satz 10 Gegeben sei eine Punktemenge S aus dem Raum IR^{2}, die in einem 2-D-Baum T gespeichert ist, wobei beim Eintragen der Punkte das Splitverfahren Vorzug verwendet wurde. Für alle Punktepaare (s, s′) ∈ S und ein c > 0 gelte: U_{c}(s) ∩ U_{c}(s′) = ∅ (s ≠ s′). Dann gilt für den Aufwand der Bereichsuche:

A(|S|, 2, Bereichsuche(U_{c}(s))) ∈ O(log^{2} |S|)

Bew. Wir führen eine worst case Analyse durch, die der von [Lee 77] zum Beweis von Theorem 1 sehr ähnlich ist. Für eine beliebige c-Umgebung eines Punktes zählen wir im Baum T die Anzahl der Schritte, die notwendig sind, um festzustellen, daß kein anderer Punkt in dieser c-Umgebung liegt. Solange diese c-Umgebung vollständig innerhalb eines Rechtecks liegt, das mit einem Knoten von T korrespondiert, steigen wir im Baum T nur abwärts. Wenn die c-Umgebung von einer Splitlinie durchschnitten wird, müssen im weiteren beide Teilbäume durchsucht werden. Wir berechnen die Größe des maximalen Teilbaums T′ von T, der zu durchsuchen ist. In Abb. 10 ist dies anhand der Splitlinie l(a) dargestellt.

Im weiteren gibt es im worst case für die Splitlinie l(b) zwei Möglichkeiten, die in den Abb. 10 und Abb. 11 dargestellt sind. Im rechten Teilbaum vom Knoten b in Abb. 10 und im rechten Teilbaum vom Knoten c in Abb. 10 kann es keine weiteren Teilungen der c-Umgebung durch Splitlinien geben, da jede Splitlinie, die die c-Umgebung schneidet, ebenfalls alle anderen c-Umgebungen von Punkten schneidet, die innerhalb dieses Rechtecks liegen. Dies verhindern wir durch das Splitverfahren Vorzug

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; m − 1; m − 2; m; Level; a; b; c; m − 1; T′(m − 2); a; c; b; l(a); l(b); l(c)]

Abbildung 10: Der maximale Baum T′ nutzloser Knoten bei der Bereichsuche(U_{c}(s)).

Links ist die Aufspaltung der angefragten c-Umgebung mit möglichen Zerschneidungen der Splitlinien gezeigt, und rechts ist der zugehörige 2-D-Baum dargestellt.

und obige Voraussetzung. Es ergeben sich die folgenden Rekursionsgleichungen:

Abb. 10  \begin{aligned}T′(m − 1) & = & m − 1 + 1 + T′(m − 2) \\ & = & ∑_{i=1}^{m−1} i \\ & = & \frac{(m−1)m}{2} \\ & ∈ & O(\frac{m^{2}}{2} ) \end{aligned}

Abb. 11  \begin{aligned}T′′(m − 2) & = & m − 2 + 1 + T′′(m − 3) \\ & = & ∑_{i=1}^{m−1} i \\ & = & \frac{(m−1)m}{2} \\ T′′(m − 1) & ∈ & O(\frac{m^{2}}{2} ) \end{aligned}

Daraus resultiert für den gesamten Baum von nutzlosen Knoten eine maximale Größe von der Ordnung O(log^{2} |S|).

Satz 11 Gegeben sei eine Punktemenge S aus dem euklidischen Raum IR^{2}, die in einem 2-D-Baum T gespeichert ist, wobei beim Eintragen der Punkte das Splitverfahren Vorzug verwendet wurde. Wenn folgende Einschränkung für c > 0 und ein e ∈ IN gilt:

∀_{S′⊆S,|S‘|>e} ∃_{p,q∈S′} U_{c}(p) ∩ U_{c}(q) = ∅  (13)

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; m − 1; m − 2; m; Level; T′′(m − 3); T′′(m − 3); m − 2; m − 2; a; b; d; c; a; d; b; c]

Abbildung 11: Der maximale Baum T′′ nutzloser Knoten bei der Bereichsuche(U_{c}(s)).

Links ist die Aufspaltung der angefragten c-Umgebung mit möglichen Zerschneidungen der Splitlinien gezeigt, und rechts ist der zugehörige 2-D-Baum dargestellt.

dann gilt für den Aufwand:

A(|S|, 2, Bereichsuche(U_{c}(s))) ∈ O((log^{2} |S|) + e log)

Bew. Wir führen eine ähnliche worst case Analyse wie im Satz 10 durch. Diesmal besagt die Einschränkung, daß es höchstens e Punkte in S gibt, deren c-Umgebungen sich alle schneiden. Für den maximalen Teilbaum T′ von T, den wir zu durchsuchen haben, um festzustellen, welche Punkte in einer c-Umgebung liegen, gilt dann fast die gleiche Rekursionsgleichung wie oben. Anstatt im rechten Teilbaum vom Knoten c in Abb. 11 nur noch abzusteigen, müssen wir diesmal allerdings e weitere Schritte einkalkulieren. Wenn wir einen Split in waagerechter Richtung durchführen, kann es nur noch weniger als e weitere Knoten in S(c) geben, da wir sonst aufgrund des Splitverfahrens Vorzug einen vertikalen Split durchgeführt hätten. Wenn wir einen vertikalen Split durch die c-Umgebung durchführen, können auf beiden Seiten jeweils nur e Punkte liegen, da es sonst ebenfalls einen Widerspruch zum Splitverfahren Vorzug oder zur obigen Gleichung 13 gibt. Es ergibt sich also folgende Rekursionsgleichung:

T′(m − 2) = m − 2 + 1 + e + T′(m − 3)
= ∑_{i=1}^{m−1}(i + e)
= \frac{(m−1)m}{2} + (m − 1)e
T′(m − 1) ∈ O(\frac{m^{2}}{2} + me)

Korollar 4 Gegeben sei eine Punktemenge S aus dem euklidischen Raum IR^{2}, die in einem 2-D-Baum T gespeichert ist, wobei beim Eintragen der Punkte das Splitverfahren Vorzug verwendet wurde. Wenn folgende Einschränkung für c > 0 gilt:

∀_{S′⊆S,|S‘|>log |S|} ∃_{p,q∈S′} U_{c}(p) ∩ U_{c}(q) = ∅  (14)

dann gilt für den Aufwand:

A(|S|, 2, c − P aare) ∈ O(|S| log^{2} |S|)

Bew. Die Aussage folgt sofort, wenn man in Satz 11 e = log |S| setzt, und zur Berechnung von c-Paare |S|-mal Bereich(p, c) berechnet.

4.3 Quad Trees

Quad Trees stellen wie die k-D-Bäume eine Datenstruktur zur Speicherung von Punkten aus dem mehrdimensionalen euklidischen Raum dar, die effiziente Bereichsanfragen unterstützt. Während k-D-Bäume trinäre Bäume waren, handelt es sich nun um 2^{k}-Bäume, wenn Punkte aus dem k-dimensionalen euklidischen Raum gespeichert werden sollen. Im weiteren beziehen wir uns nur auf den 2-dimensionalen Fall, da sich die Verallgemeinerung sofort ergibt. Da Punkte und Knoten direkt miteinander korrespondieren, beziehen sich alle Operatoren im weiteren auf beides. Eine formale Darstellung von Quad Trees findet man in [Bentley 74].

Gegeben sei ein euklidischen Raum U = IR^{2}. Jedem Knoten v vom Quad Tree T entspricht wie beim k-D-Baum ein Rechteck R(v). Allerdings gibt es nun nicht nur eine sondern zwei Splitlinien l_{1}(v) und l_{2}(v), die das Rechteck R(v) in vier Rechtecke r_{00}, r_{01}, r_{10} und r_{11} teilen. Jeder Knoten v ∈ T hat vier Folgeknoten v.00, v.01, v.10 und v.11, die eben diesen vier Rechtecken entsprechen (R(v.i) = r_{i}, i ∈ {00, 01, 10, 11}). Ein Operator VGL(a,b) gibt für den Punkte b ∈ IR^{2} an, in welchem ’Folgerechteck’ vom Knoten a der Punkt b liegt:

V GL(a, b) = \{ \begin{matrix}a.00 falls & b_{1} < a_{1} ∧ & b_{2} < a_{2} \\ a.01 falls & b_{1} < a_{1} ∧ & b_{2} ≥ a_{2} \\ a.10 falls & b_{1} ≥ a_{1} ∧ & b_{2} < a_{2} \\ a.11 falls & b_{1} ≥ a_{1} ∧ & b_{2} ≥ a_{2} \end{matrix}

Das Einfügen von einem Punkte p ∈ IR^{2} in einen Quad Tree T mit der Wurzel w könnte mittels der folgenden Funktion durch den Aufruf Einfügen(w, p) erfolgen.

Einfügen ( v : Knoten; p : Punkt); IF VGL(v,p) = NOT NULL

THEN Einfügen (p, VGL(v,p)); ELSE VGL(v,p) := p;

ENDIF; EndEinfügen;

Bem. Für eine Menge S ⊂ IR^{2}, die in einer beliebigen Reihenfolge mittels obiger Funktion Einfügen in einem Quad Tree gespeichert T wird, ist der Aufwand für alle Einfügeoperationen im worst case von der Ordnung O(N^{2}).

Da keine Vorkehrungen beim Einfügen getroffen werden, die das ’Entarten’ des Baums T zu einer Liste verhindern, könnten maximal \frac{N(N−1)}{2} Operationen notwendig sein.

Bentley und Finkel untersuchen einige gleichverteilte Punktemengen im 2-dimensionalen euklidischen Raum und zeigen anhand von Tests, daß im Mittel weniger als n log n Operationen zum Einfügen von |S| = n Punkten nach obigem Verfahren bei beliebiger Reihenfolge in einem Quad Tree notwendig sind [Bentley 74]. Unter Benutzung der Median-Strategie, wie wir sie bei k-D-Bäumen beschrieben haben, entstehen beim Einfügen ideale Quad Bäume. Der Median bzgl. einer Koordinate wird dabei immer als Wurzel verwendet, so daß im nächsten Level mindestens die Hälfte aller Knoten in verschiedenen Teilbäumen liegen. Ein Quad Baum ist aber ein 2^{k}-Baum, wenn Punkte aus dem k-dimensionalen euklidischen Raum gespeichert werden sollen, so daß sich auch dadurch im Vergleich zu k-D-Bäumen keine Verbesserung ergibt.

4.4 Das Grid File

Ein Grid File ist eine dynamische Datenstruktur zur Speicherung mehrdimensionaler Schlüssel und zum effizienten Zugriff darauf.

Wir führen einige grundlegende Begriffe ein:

U  : d-dimensionaler euklidischer Raum IR^{d}, wobei U_{i}
: die i-te Dimension ist (i ∈ {1, …, d}).
S  : Eine Menge von N Punkten aus U.
Gridzelle  : Kartesisches Produkt von d Intervallen aus U.
Datenblock : Ein Datenblock B enthält maximal b Punkte aus S.
Blockregion : Alle Gridzellen, die dem selben Datenblock zugeordnet sind.
D  : d-dimensionale Matrix, die jeder Gridzelle einen
: Datenblock zuordnet.
Scales  : d eindimensionale dynamische Hashverfahren.

Eindimensionale Hashverfahren sind ausführlich in [Larson 83] und [Ottmann 93] beschrieben.

Der Raum U ist überdeckt von disjunkten Gridzellen. Jeder Gridzelle ist dabei ein Datenblock zugeordnet, der höchstens b Punkte enthält. Ein Datenblock kann durchaus mehreren Gridzellen zugeordnet sein. Alle Gridzellen, die demselben Datenblock zugeordnet sind, nennen wir eine Blockregion. Die Directorymatrix D enthält die Information, welcher Gridzelle welcher Datenblock zugeordnet ist. Dabei werden die einzelnen Dimensionen durch eindimensionale Hashfunktionen, sogenannte Scales, adressiert. Diese Zuordnung machen wir uns am Beispiel deutlich: Gegeben sei ein 2-dimensionaler Raum U mit fünf Punkten {a, b, c, d, e} und einer maximalen Blockkapazität b = 2 (s. Abb. 12).

Die Blockregionen sind im 2-dimensionalen Raum U immer Rechtecke, im 3-dimensionalen Raum U immer Quader usw.

[figure: a; b; c; d; e; a; b; c; d; e; D; 1; 2; 0; 1; 1; 0; 2; 3; U; U_{1} = X; X-Scale; U_{2} = Y; Y-Scale; y; x]

Abbildung 12: Zuordnung von Punkten aus U zur Directorymatrix D Der Raum U ist von vier Gridzellen überdeckt. D enthält Verweise von den Gridzellen auf die drei Datenblöcke, die die Punkte enthalten. Im weiteren werden wir den Raum U und die Zuordnung zu den Datenblöcken übereinanderzeichnen.

4.4.1 Funktionsweise

Wir demonstrieren das Grid File anhand der einzelnen Operationen.

Suche(p)

Beispiel: Suche(d) mit d = (x, y) s.Abb. 12.

1. Es wird der X-Scale(x) = 0 und der Y-Scale(y) = 0 berechnet.

2. Es wird die Blocknummer 3 aus D[0, 0] gelesen.

3. Es wird der Datenblock 3 nach d durchsucht.

Einfügen(p)

Es werden die Punkte eins und zwei von Suche(p) ausgeführt. Angenommen p soll in den Datenblock B eingefügt werden, dann wird p in diesen Datenblock eingetragen, falls weniger als b Punkte in B enthalten sind. Ansonsten ist eine sogenannte Kollision (s. Hashing in [Ottmann 93]) aufgetreten, bei der verschiedene Strategien, die sich in der Anzahl zu speichernder Gridzellen und damit der Größe der Directorymatrix D vehement unterscheiden, angewendet werden.

1. MEH - Multiply Extendible Hashing Alle Gridzellen in U besitzen zu jedem Zeitpunkt die gleiche Größe.

Bei einer Kollision werden die b + 1 Punkte entsprechend der Lage in der Blockregion auf den Datenblock B und einen neuen Datenblock B′ verteilt. Die Gridzellen r_{1}, r_{2}, …, r_{i}, die auf den Datenblock B verweisen, werden den Datenblöcken B und B′, entsprechend der Lage der b + 1 Punkte, zugeordnet, falls die b + 1 Punkte nicht alle in derselben Gridzelle liegen (s.Abb. 13).

[figure: a; b; c; d; e; f; 1; 1; 2; 2; 2; 2; 3; 4; 00; 01; 10; 11; 0; 1]

Abbildung 13: Einfache Kollision beim Einfügen in die Directorymatrix D durch den Punkt f.

Wir gehen aus von der Lage der Punkte in Abb. 12 und fügen den Punkt f ein. Da der Datenblock drei schon zwei Punkte enthält, wird ein neuer Datenblock vier kreiert und es kommt zur Teilung aller Gridzellen bzgl. der X-Scale.

Falls jedoch b + 1 Punkte in einer Gridzelle r liegen, werden alle Gridzellen aufgesplittet, so daß sich die Anzahl der Gridzellen verdoppelt.

FOR ALL r = [x_{1}, x_{2}) × [y_{1}, y_{2}) IF Teilung entlang X-Koordinate

THEN r_{1} := [x_{1}, \frac{x_{1}+x_{2}}{2} ) × [y_{1}, y_{2}) ; r_{2} := [\frac{x_{1}+x_{2}}{2} , x_{2}) × [y_{1}, y_{2})

ELSE r_{1} := [x_{1}, x_{2}) × [y_{1}, \frac{y_{1}+y_{2}}{2} ) ; r_{2} := [x_{1}, x_{2}) × [\frac{y_{1}+y_{2}}{2} , y_{2}) ENDIF;

Angenommen die Gridzelle r wurde dabei in r_{1} und r_{2} geteilt, die nun beide auf den selben Datenblock B verweisen, dann wird verfahren wie im ersten Fall. Die b + 1 Punkte werden entsprechend ihrer Lage in r_{1} und r_{2} auf die Blöcke B und B′ verteilt, falls sie nicht alle in derselben Gridzelle liegen. Wenn das der Fall ist, werden rekursiv solange alle Regionen aufgesplittet, bis die b + 1 Punkte sich in verschiedenen Gridzellen befinden (s.Abb. 14).

Für den Fall d = 1 entspricht dieses Vorgehen genau Extendible Hashing [Regnier 84].

2. MDH - Multikey dynamic Hashing MDH verhält sich analog zu MEH, falls keine Kollisionen auftreten und auch, wenn bei einer Kollision nicht alle b + 1 Punkte in einer Gridzelle liegen. Wenn aber b + 1 Punkte in einer Gridzelle liegen, werden nicht alle Gridzellen aufgesplittet, so daß sich die Anzahl der Gridzellen verdoppelt, sondern es werden nur alle Gridzellen entlang einer Dimension gesplittet.

Falls b + 1 Punkte in der Gridzelle r = [x_{1}, x_{2}) × [y_{1}, y_{2}) enthalten sind, dann werden alle Gridzellen r′, die entlang der X-Scale im Streifen [x_{1}, x_{2}) oder entlang der Y-Scale im Streifen [y_{1}, y_{2}) liegen, in zwei Gridzellen r′_{1} und r′_{2} aufgespalten. Falls immer noch mehr als b Punkte in einer Gridzelle liegen, wird dieses Verfahren

[figure: a; b; c; d; e; 1; 1; 2; 2; 2; 2; 00; 01; 10; 11; f; 1; 1; 2; 2; 2; 2; 3; 3; 4; 00; 01; 10; 11; 4]

Abbildung 14: Mehrfache Kollision beim MEH.

Wir gehen aus von der Lage der Punkte in Abb. 12 und fügen den Punkt f ein. Da der Datenblock drei schon zwei Punkte enthält, wird ein neuer Datenblock vier kreiert, und es kommt zur Teilung aller Gridzellen bzgl. der X-Scale, die die Punkte f, d und e allerdings nicht trennt. Folglich werden nochmals alle Gridzellen geteilt und zwar bzgl. der Y-Scale.

rekursiv solange durchgeführt, bis die b+1 Punkte in verschiedenen Gridzellen liegen (s.Abb. 15).

Für den Fall d = 1 ergibt sich wiederum das Dynamische Hashing [Regnier 84].

Für die Entscheidung, bzgl. welcher Dimension bei einer Kollision die Teilung durchgeführt wird, gibt es verschiedene Strategien. In [Ottmann 93] wird folgende Splitstrategie S1 vorgeschlagen: Wenn eine Kollision in Blockregion B auftritt, wird die erste zutreffende der folgenden Regeln angewendet.

(a) Teile die längste Seite von B.

(b) Teile B gemäß einer vorhandenen Einteilung in Gridzellen.

(c) Teile B in der Dimension, in der die kleinste Gesamtzahl von Einteilungen vorhanden ist.

(d) Teile B in einer beliebigen Dimension.

Aufgrund der Regel 2a werden die Seiten einer Blockregion in der Tendenz alle die gleiche Länge besitzen. Die Directorymatrix kann unter Umständen dadurch anwachsen, obwohl dies vermeidbar gewesen wäre, wenn man die Regel 2b vorgezogen hätte. Da für unsere Anwendung die Größe der Directorymatrix eine wichtige Rolle spielt, schlagen wir für das Auftreten einer Kollision in Datenblockregion B folgende Splitstrategie S2 vor:

(a) Teile B gemäß einer vorhandenen Einteilung in Gridzellen.

(b) Teile die längste Seite von B.

(c) Teile B in einer beliebigen Dimension.

[figure: a; b; c; d; e; 1; 1; 2; 00; 01; f; 2; 3; 3; 4; 00; 01; 2; 1; 1; 4]

Abbildung 15: Mehrfache Kollision beim MDH.

Wir gehen aus von der Lage der Punkte in Abb. 12 und fügen den Punkt f ein. Da der Datenblock drei schon zwei Punkte enthält, wird ein neuer Datenblock vier kreiert und es kommt zur Teilung der Gridzellen (0, 0) und (0, 1). Da die Punkte d, e und f dann in der Gridzelle (00, 0) liegen, wird nochmals gesplittet, so daß die dargestellte Anordnung von Gridzellen entsteht.

[figure: 2; a; b; c; 1; 2; 1; 3; 2; 3; 2; U; a; b; c; 1; 2; 1; 2; U; 3; 3]

Abbildung 16: Verschiedene Splitstrategien (S1, S2).

Der Unterschied ist am Beispiel in Abb. 16 dargestellt. Es werden die Punkte a, b und c in dieser Reihenfolge in das Grid File eingetragen, wobei die maximale Datenblockkapazität eins ist. Die linke Darstellung zeigt die Aufteilung in Blockregionen bei Verwendung der Splitstrategie S1 und die rechte Darstellung bei Verwendung der Splitstrategie S2. Bei Verwendung unserer Strategie sind anstatt von acht nur sechs Verweise von Gridzellen auf Datenblöcke notwendig.

Löschen(p)

Es wird eine Suche nach p durchgeführt und dann p aus dem entsprechenden Datenblock entfernt. So wie beim Einfügen das Splitten von weiteren Gridzellen notwendig war, werden wir beim Löschen, um eine bessere Speicherplatzauslastung zu erreichen, verschiedene Verschmelzungsstrategien einsetzen. Dazu testen wir zum einen, ob der entsprechende Datenblock B tatsächlich nur relativ gering besetzt ist, denn nur dann besteht auch die Wahrscheinlichkeit, daß eine Verschmelzung möglich ist (c_{min}). Von den möglichen Partnerblöcken wird dann derjenige Datenblock B′ mit der geringsten Besetzung ausgewählt und mit B verschmolzen, falls der Besetzungsgrad unter einer bestimmten Maximalgrenze (c_{max}) liegt.

Definition 34 Die Anzahl der Punkte, die in einem Datenblock B enthalten sind, wird durch A(B) ∈ IN_{0} angegeben.

Der Besetzungsgrad ergibt sich dann durch \frac{A(B)}{b}, wobei die maximale Anzahl von Punkten in einem Datenblock durch b gegeben ist.

Voraussetzungen für die Durchführung einer Verschmelzung:

\begin{matrix}a) & \frac{A(B)}{b} ≤ & c_{min} \\ b) & \frac{A(B)+A(B′)}{b} ≤ & c_{max} \end{matrix}

Durch die Festlegung der Werte c_{min} und c_{max}, die in der Praxis ca. bei 0.3 und 0.7 liegen, ist sichergestellt, daß sich bei der Verwaltung mittels des Grid Files nicht dauernd Splits und Verschmelzungen aufheben.

Wir geben zur Veranschaulichung zwei Verschmelzungsstrategien an:

Nachbarstrategie Hierbei können im 2-dimensionalen Fall immer nur Rechtecke beim Verschmelzen entstehen. Im 3-dimensionalen Fall sind es Quader usw. Verschmolzen werden können alle Nachbarregionen. In jeder Dimension gibt es zu einer Region zwei Nachbarregionen. Es kann durch dieses Vorgehen zu einem Deadlock kommen, d.h. die Speicherauslastung kann auf Null sinken (in allen Datenblöcken B gilt A(B) = 0), es können aber trotzdem keine Verschmelzungen mehr durchgeführt werden (s.Abb. 17).

1  2 213  3 4  4 U b_{2,3} b_{2,4}  b_{3,3}

Abbildung 17: Deadlock bei der Nachbarstrategie.

Der 2-dimensionale Raum U ist unterteilt in 16 Regionen b_{i,j} i, j ∈ {1, 2, 3, 4}. Die Region b_{2,3} besitzt die vier Nachbarn b_{2,2}, b_{3,3}, b_{2,4} und b_{1,3}. Es gibt fünf Blockregionen, die dick umrandet sind, aber keine zwei dieser Blockregionen lassen sich miteinander verschmelzen, da das Resultat nicht rechteckig wäre.

Bruderstrategie Auch hierbei können durch die Verschmelzung nur Rechtecke, Quader etc. (entsprechend der Anzahl der Dimensionen) entstehen, allerdings sind Verschmelzungen prinzipiell nur zwischen Blockregionen erlaubt, die durch eine letzte Teilung entstehen konnten. Diese Blockregionen heißen dann Brüder. In Abb. 17 besitzt die Region b_{2,3} die Brüder b_{2,4} und b_{1,3}, da die Trennung zwischen den Regionen b_{2,3} und b_{3,3} vor der Trennung zwischen b_{2,3} und b_{1,3} stattgefunden haben muß und analog in der anderen Dimension. Dies hängt damit zusammen, daß wir beim Einfügen von Punkten, wenn es zum Teilen von Gridzellen kommt, immer in der Mitte der Gridzelle teilen. Bzgl. jeder Dimension gibt es für jede Region genau einen Bruder.

Satz 12 Bei der Verwendung der Bruderstrategie kommt es im 2-dimensionalen Fall nie zu einem Deadlock.

Bew. Unter allen Blockregionen muß es eine bzgl. der Fläche kleinste Blockregion b_{min} geben. Diese Blockregion ist entweder quadratisch oder rechteckig. Angenommen b_{min} bestehe aus einer quadratischen Blockregion b_{1} s. Abb. 18.

U l_{1}  l_{2} l_{3} l_{4}  c d  b_{2} b_{4} b_{1} b_{3}

Abbildung 18: Bruderstrategie im 2-dimensionalen Raum U

Die Teilungen entlang der Linien l_{1}, l_{2}, l_{3} und l_{4} haben früher stattgefunden als die Teilungen entlang der Linien c und d, so daß die Blockregion b_{1} die Brüder b_{2} und b_{3} besitzt. Da b_{2} und b_{3} die Brüder b_{1} und b_{4} besitzen, muß eine von ihnen, o.B.d.A sei dies b_{3}, einer Blockregion entsprechen. Damit liegt kein Deadlock vor, da b_{1} und b_{3} verschmolzen werden können. Angenommen b_{min} bestehe aus einer rechteckigen Blockregion. O.B.d.A. sei b_{min} = b_{1} ∪ b_{3}, dann müssen b_{2} und b_{4} eine gemeinsame Blockregion b = b_{2} ∪ b_{4} bilden, da sonst b_{min} im Widerspruch zur Annahme nicht die kleinste Blockregion wäre. Folglich liegt ebenfalls kein Deadlock vor, da die Blockregionen b_{min} und b verschmolzen werden können.

Im 3-dimensionalen Fall kann allerdings auch mit der Bruderstrategie ein Deadlock auftreten (s.Abb. 19).

[figure: .; .; .; .]

Abbildung 19: Deadlock im 3-dimensionalen mit der Bruderstrategie.

Zu beachten ist, daß direkt nach Einfügeoperationen Verschmelzungen notwendig werden können.

[figure: a; b; c; d; e; f; 1; 2; 3; 4; 5; g; h; a; b; c; d; e; f; 1; 2; 3; 4; g; h; ⟹; Verschmelzen]

Abbildung 20: Einfügen mit anschließendem Verschmelzen.

In das Grid File, das in Abb. 13 dargestellt ist, wurden zwei weitere Punkte g und h eingefügt (Abb. 20). Für c_{min} = 0.55 und c_{max} = 1 ist direkt nach dem Einfügen eine Verschmelzoperation zwischen den Blockregionen vier und fünf durchzuführen, wenn als Verschmelzstrategie die Nachbarstrategie verwendet wird.

Die Wahrscheinlichkeit für das Vorkommen von Deadlocks wird zwar durch Anwendung der Bruderstrategie anstatt der Nachbarstrategie vermindert, aber die Speicherplatzauslastung muß nicht unbedingt besser sein. In der Situation in Abb. 20 hätten wir z.B. bei Benutzung der Bruderstrategie keine Verschmelzung durchführen können.

Bereichssuche(x, y)

Zuerst wird eine Suche(x) durchgeführt und der gefundene Datenblock B nach allen Punkten aus der Region R(x, y) durchsucht. Im Falle von zwei Dimensionen werden dann nach rechts und nach oben solange über weitere Blockregionen mittels der Directorymatrix D Blöcke durchsucht, bis die ganze Region R(x, y) durchsucht wurde (s. Abb. 21).

Die Directorymatrix D, die wegen ihrer Größe zumeist auf Externspeicher ausgelagert ist,

[figure: 0; 50; 100; 0; 50; 100; 20; 40; 75; 40; a; b; c; d; e; 1; 1; 2; 4; 3; 4; f; g; h]

Abbildung 21: Bereichssuche((20,40),(40,75)) Durch Suche(20,40) wird der Datenblock drei und dann mittels der Directorymatrix D nach rechts und oben noch die Datenblöcke vier und eins durchsucht.

muß also eine Operation unterstützen, bei der benachbarte Gridzellen eine Rolle spielen. Das Grid File unterstützte die Anfragen bzgl. benachbarter Datenpunkte, dieses Prinzip werden wir nun im Mehr-Ebenen-Directory wiederverwenden.

Definition 35 Gegeben sei ein Raum U = [x_{1}, y_{1}) × ⋯ × [x_{d}, y_{d}) und eine mögliche Aufteilung von U in Gridzellen, dann besteht ein Blockdirectory B aus Verweisen von diesen Gridzellen auf andere Blockdirectories oder auf Datenblöcke. Jedes Blockdirectory ist als Matrix organisiert. Eine Funktion U ordnet jedem Blockdirectory den Raum zu, der von ihm überdeckt wird: U(B) = U.

Definition 36 Ein k-Ebenen-Directory besteht aus einem Wurzeldirectory D(0), k − 1 Directoryebenen D(1), …, D(k − 1) und einem Kapazitätsparameter B = (b_{1}, b_{2}, …, b_{k}). Jede Directoryebene D(i) besteht aus Blockdirectories B, die maximal b_{i} Verweise enthalten, wir schreiben dann B ∈ D(i) (i ∈ {1, 2, …, k − 1}). Das Wurzeldirectory D(0) enthält Verweise auf die Blockdirectories von Directoryebene D(1), alle Blockdirectories B ∈ D(i) enthalten Verweise auf Blockdirectories B′ ∈ D(i + 1) (i ∈ {1, 2, …, k − 2}) und die Blockdirectories B ∈ D(k − 1) enthalten Verweise auf Datenblöcke mit maximaler Datenblockkapazität b_{k}. Außerdem gilt:

U(B) ⊇ U(B[i_{1}, …, i_{d}]) für B ∈ D(i) i ∈ {1, 2, …, k − 2}
U(D(0)) ⊇ U(B) für B ∈ D(1)

Bem. Wenn das Wurzeldirectory D(0) nur einen Eintrag enthält, werden in einem k-Ebenen-Directory maximal Π_{i=1}^{k}b_{i} Punkte gespeichert. Da das Wurzeldirectory aber unbegrenzt anwachsen kann, können in jedem k-Ebenen-Directory beliebig viele Punkte gespeichert werden. Die bisher beschriebene Directorymatrix stellt genau ein 1-Ebenen-Directory dar.

In Abb. 22 ist die Situation aus Abb. 21 für ein 2-Ebenen-Directory mit einem Kapazitätsparameter B = (2, 2) dargestellt.

Bei der Operation Suche(d) wird im ersten Schritt auf das Wurzeldirectory zugegriffen und dann auf das Blockdirectory B. Im Blockdirectory B findet man den Verweis auf den

1 2 3 4 B A  Blockdirectories A B  Wurzeldirectory

Abbildung 22: 2-Ebenen-Directory

entsprechenden Datenblock drei und lädt diesen in den Hauptspeicher. Die Blockdirectorykapazität wird im allgemeinen so groß gewählt, daß das Wurzeldirectory im Hauptspeicher gehalten werden kann. Dann sind weiterhin meist nur zwei Zugriffe auf den Externspeicher notwendig (Laden vom Blockdirectory und vom Datenblock). Dies hängt natürlich davon ab, ob der gesuchte Bereich auch von einem Blockdirectory überdeckt wird. Bei der Bereichsanfrage aus Abb. 21 werden in dem 2-Ebenen-Directory aus Abb. 22 nun die Blockdirectories A und B und die Datenblöcke eins, drei und vier geladen. Es sind nun also fünf Zugriffe und nicht, wie bei der Verwaltung mit einem 1-Ebenen-Directory, sieben Zugriffe auf den Externspeicher notwendig, da dann vier Zugriffe auf die Directorymatrix erfolgt wären. Den Vorteil der einfacheren Bereichsanfrage erkauft man sich durch einen aufwendigeren Mechanismus des Einfügens und Löschens, der nun notwendig wird. Prinzipiell verläuft beides analog, wie beim 1-Ebenen-Directory, nur daß das Einfügen nun nicht nur zum Teilen von Gridzellen, sondern auch von Blockdirectories führen kann. Genauso werden beim Löschen Verschmelzoperationen nicht nur für Datenblöcke, sondern auch für Blockdirectories notwendig.

4.4.2 Aufwandsbetrachtungen

Speicheraufwand

Wenn wir eine der Splitstrategien benutzen, die wir auf Seite 44 beschrieben haben, ist die Directorymatrix D auch, wenn nur Einfügeoperationen vorkommen, nicht nur abhängig von der Lage der Punkte im Raum U, sondern auch von der Reihenfolge des Einfügens. In [Regnier 84] werden Einfügestrategien für MEH und MDH vorgeschlagen, die zusichern, daß es eine eindeutige Zuordnung zwischen Punkteanordnung und Directorymatrix gibt, die unabhängig von der Reihenfolge der Einfügungen ist. Für [Regnier 84] spielt diese Eigenschaft eine wichtige Rolle, da so theoretische Untersuchungen bzgl. des Zusammenhangs zwischen der Lage der Punkte und der Directorygröße einfacher durchzuführen sind. Die Größe der Directorymatrix steigt durch diese Strategien eventuell unnötig an, daher benutzen wir sie nicht.

Definition 37 Die Größe einer d-dimensionalen Directorymatrix D ergibt sich als Multiplikation aus der Anzahl der einzelnen Intervalle (i_{1}, …, i_{d}) in jeder Dimension:

G(D) = Π_{k=1}^{d}i_{k}

Definition 38 Gegeben sei ein euklidischer Raum [0, 2^{l}]^{d} und eine Punktemenge S mit einer Spärlichkeit von c für δ = \frac{1}{2} und N Punkte, die durch N Einfügeoperationen in einem 1-Ebenen-Directory D mit einer Directorygröße von G(D) gespeichert sind. Wenn insgesamt k Datenblöcke mit jeweils einer Blockkapazität von b benötigt werden, heißt

S(N, d, l, c, b) = G(D) + kb

der Speicheraufwand und

MS(N, d, l, c, b) = max{S(N, d, l, c, b)| für eine beliebige Reihenfolge

der Einfügungen der Punktemenge S}

der maximale Speicheraufwand.

Der Speicheraufwand beinhaltet zwei Teile: die Größe der Directorymatrix und die Auslastung der Datenblöcke. Wenn die Datenblockkapazität b zu hoch ist, wird die Auslastung der Datenblöcke niedrig sein, aber die Größe der Directorymatrix ebenfalls. Wenn allerdings die Datenblockkapazität zu niedrig ist, wird die Auslastung der Datenblöcke recht hoch sein, aber die Directorymatrix recht groß. Die Datenblockkapazität stellt also den Parameter dar, den wir beeinflussen, um einen geringen Speicheraufwand zu erreichen.

Es gilt stets: S(N, d, l, c, b) ≥ N. Dies ergibt sich aus kb ≥ N, da in den Datenblöcken die N Punkte gespeichert werden müssen.

Der maximale Speicheraufwand ist abhängig vom Verfahren zur Adressierung der Scales (MEH, MDH), der verwendeten Strategie zur Kollisionsauflösung (S1, S2) und der maximalen Blockkapazität. Wir betrachten im weiteren den Speicheraufwand im worst case und bei einer vorgegebenen Verteilung der Punkte im Raum.

Satz 13 Wenn bei Kollisionen das MEH-Verfahren angewendet wird, gilt für c ≤ b und N > b im 2-dimensionalen Raum:

MS(N, 2, l, c, b) = 2^{2l} + (N − b)b + b.

Bew. Der worst case für den Speicheraufwand wird im Raum U = [0, 2^{l}]^{2} erreicht, wenn dieser vollständig mit Gridzellen der Größe eins überdeckt ist. Da der Raum U die nach Voraussetzung die Spärlichkeit c mit δ = \frac{1}{2} besitzt, wissen wir, daß N ≤ 2^{2l}c gilt. Die Größe der Directorymatrix D läßt sich für die Blockkapazität b = 1 schon durch das Einfügen von zwei Punkten maximieren. O.B.d.A. werden die Punkte a = (0; 0) und b = (0; 1, 1) in das 1-Ebenen Directory eingefügt. Dann werden beim Teilen der Regionen abwechselnd bzgl. der X-Koordinate und der Y-Koordinate solange diese geteilt, bis a und b in verschiedenen Blockregionen liegen, da die Blockkapazität nur eins ist. Es wird 2^{l} −1 mal bzgl. der X-Koordinate und 2^{l} − 1 mal bzgl. der Y-Koordinate eine Teilung durchgeführt, bis a und b in den verschiedenen Gridzellen r_{1} = [0, 1) × [0, 1) und r_{2} = [0, 1) × [1, 2) liegen. Es gibt dann 2^{l} Intervalle bzgl. jeder Dimension und damit 2^{2l} verschiedene Gridzellen, die zwei verschiedenen Datenblöcken zugeordnet sind. Dies ergibt auch die Größe der Directorymatrix G(D) = 2^{2l}. Da der Raum U nicht weiter aufgeteilt werden muß, aufgrund der Spärlichkeit, ergibt sich der erste Summand. Im worst case sind alle Datenblöcke bis auf einen mit einem Punkt belegt, so daß der zweite Summand folgt.

Korollar 5 Wenn bei Kollisionen das MEH-Verfahren angewendet wird, gilt für c ≤ b im d-dimensionalen Raum: MS(N, d, l, c, b) = 2^{dl} + (N − b)b + b.

Bew. In jeder einzelnen Dimension kann es ebenfalls maximal 2^{l} Teilungen geben, so daß sich eine maximale Größe der Directorymatrix von G(D) = 2^{dl} ergibt. Wiederum wird für eine maximale Datenblockkapazität b = 1 und das Eintragen von zwei Punkten dieser worst case erreicht. O.B.d.A. seien dies die Punkte a = (0; 0; …; 0) und b = (0; 0; …; 0; 1, 1).

Satz 14 Wenn bei Kollisionen das MDH-Verfahren angewendet wird, gilt für c ≤ b: MS(b + 1, 2, l, c, b) = (l + 1)^{2} + 2.

Bew. Analog zum Beweis von Satz 13 kann es mit dem MDH-Verfahren ebenfalls höchstens zu 2l Kollisionen beim Eintragen von b + 1 Punkten kommen. Bei jedem Aufsplitten einer Koordinate käme allerdings immer nur ein weiteres Intervall in dieser Koordinate hinzu, so daß nach l Aufteilungen in jeder Koordinate l + 1 Intervalle bestehen. Es ergibt sich die Größe der Directorymatrix D zu G(D) = (l+1)^{2}. Außerdem können nicht mehr als zwei Datenblöcke gebildet werden.

Korollar 6 Bei Verwendung des MDH-Verfahrens gilt für c ≤ b im d-dimensionalen Raum:

MS(b + 1, d, l, c, b) = (l + 1)^{d} + 2

Bew. Im Falle von d Dimensionen werden beim Eintragen von b + 1 Punkten alle Koordinaten in l + 1 Intervalle geteilt. Demzufolge ergibt sich für die Directorymatrix G(D) = (l + 1)^{d}.

Satz 15 Bei Verwendung des MDH-Verfahrens gilt für c ≤ b und N > b + 1:

MS(N, d, l, c, b) < min(⌈\frac{N}{b + 1}⌉ ((l + 1)^{d} + 2) , 2^{dl} + (N − b)b + b)

Bew. Den maximalen Speicheraufwand für N Punkte können wir durch \frac{N}{b+1}MS(b + 1, d, l, c, b) grob nach oben abschätzen. Wenn wir also für \frac{N}{b+1} Gruppen von jeweils b + 1 Punkten immer den maximalen Speicheraufwand für c ≤ b annehmen. Andererseits wissen wir durch die Spärlichkeit, daß G(D) ≤ 2^{dl} für c ≤ b gilt, da es höchstens soviele Gridzellen geben kann.

Bem. Das MDH-Verfahren ergibt, wie zu erwarten war, im Gegensatz zum MEH-Verfahren i.A. einen wesentlich günstigeren Speicheraufwand. Trotzdem bleibt ein noch erheblicher Speicheraufwand im Falle des worst case, dies hängt damit zusammen, daß wir unter Umständen Kollisionen erst durch sehr viele ’unnötige’ Teilungen im Raum U auflösen können. Wenn die Anzahl der eingefügten Punkte gering ist, macht sich dieser Nachteil stark bemerkbar. Wir untersuchen daher nun einige maximal gefüllte Räume U.

Satz 16 Gegeben sei eine Punktemenge S mit |S| = 2^{dl}c im Raum U = [0, 2^{l}]^{d} und einer Spärlichkeit von c für δ = \frac{1}{2}, wenn wir die Splitstrategie S2 zur Kollisionsauflösung verwenden, folgt für den Speicheraufwand für d, l, c ∈ IN:

MS(2^{dl}c, d, l, c, c) = 2^{dl}(c + 1)

Bew. Beim Einfügen der Punkte aus S wird bei einer Kollision in einem Datenblock zuerst eine vorhandene Einteilung des Raums U benutzt, erst wenn das zu keiner Auflösung der Kollision führt, wird die längste der Seiten der entsprechenden Blockregion geteilt. Der gesamte Raum U wird genau in 2^{dl} d-dimensionalen Würfel mit der Kantenlänge eins geteilt. In kleinere Würfel kann er nicht geteilt werden, da es in jedem Würfel höchstens c Punkte aufgrund der Spärlichkeit von c geben kann. In größere Würfel wird der Raum nicht geteilt, da er maximal mit Punkten gefüllt ist. Nachdem alle Punkte eingefügt wurden, gibt es in jedem Datenblock genau c Punkte. Die Gesamtanzahl aller Datenblöcke stimmt genau mit der Größe der Directorymatrix überein:

G(D) = \frac{|S|}{c} = 2^{dl}

Dieses Ergebnis ist unabhängig davon, ob wir bei der Verwaltung der Scales für das Grid File das MEH- oder das MDH-Verfahren verwenden, da der Raum maximal mit Punkten ausgefüllt ist.

Korollar 7 Wenn wir die Splitstrategie S2 zur Kollisionsauflösung verwenden, folgt für den Speicheraufwand für d, l, k ∈ IN(l > k):

MS(2^{dl}, d, l, 1, 2^{dk}) = 2^{d(l−k)} + 2^{dl}

Bew. Die Aussage ergibt sich analog zum Beweis von Satz 16, allerdings wird der Raum U nun durch d-dimensionale Würfel mit Kantenlänge 2^{k} überdeckt. In jedem dieser Würfel liegen genau 2^{dk} Punkte, weil die Punktemenge S den Raum U vollständig überdeckt.

Korollar 8 Für eine beliebige Punktemenge S gilt, wenn wir die Splitstrategie S2 zur Kollisionsauflösung verwenden, für den maximalen Speicheraufwand (d, l, k ∈ IN):

MS(|S|, d, l, 1, 2^{dk}) ≤ 2^{d(l−k)} + (|S| − 2^{dk})2^{dk} + 2^{dk}

Bem. Die Auslastung der Datenblöcke war bzgl. der letzten beiden Korollare immer optimal (\frac{A(B)}{b} = 1) aufgrund der speziellen Anordnung der Punkte und der Wahl von b = 2^{dk}. Um so größer wir also die maximale Blockkapazität b = 2^{dk} wählen, um so geringer wird letztlich auch der Speicheraufwand. Dieser positiven Eigenschaft steht allerdings ein erhöhter Aufwand für Anfrageoperationen gegenüber, da dabei immer die gesamten Datenblöcke durchsucht werden müssen.

Definition 39 Gegeben sei ein Blockdirectory B mit U(B) ⊆ IR^{d} und i_{j} Intervallen in der Dimension j ∈ {1, 2, …, d}, dann heißt: G(B) = Π_{j=1}^{d}i_{j} die Größe von B. Für ein k-Ebenen-Directory D heißt:

G(D(i)) = ∑_{B∈D(i)} G(B)  für i ∈ {1, …, k − 1}

die Größe von Directoryebene i und

G(D) = ∑_{i=0}^{k−1} G(D(i))

die Größe von D.

Bem. Da in einem k-Ebenen-Directory D mit Kapazitätsparameter B = (b_{1}, b_{2}, …, b_{k}) für jeden Eintrag im Wurzeldirectory D(0) höchstens Π_{i=1}^{k}b_{i} Punkte gespeichert werden können, gilt im Vergleich zum 1-Ebenen-Directory D′, wenn in beiden die gleiche Punktemenge gespeichert wird:

G(D′) Π_{i=1}^{k}b_{i} ≤ G(D)

Satz 17 Wenn für eine Punktemenge S, die in einem k-Ebenen-Directory D mit Kapazitätsparameter B = (b_{1}, …, b_{k}) gespeichert werden soll, gilt:

|S| < ∑_{i=1}^{k} b_{i}

Dann kommt man mit einem Eintrag im Wurzeldirectory aus (G(D(0)) = 1).

Bew. Jede Kollision, die zu einer Teilung von Blockdirectory B ∈ D(i) führt, setzt eine Kollision mit anschließender Teilung in den Directoryebenen D(i + 1), …, D(k − 1) und einem Datenblock voraus. Die erste Teilung eines Datenblocks wird notwendig, wenn mindestens b_{k} +1 Punkte eingetragen wurden. Die erste Teilung eines Blockdirectories B ∈ D(i) wird notwendig, wenn mindestens ∑_{j=i+1}^{k} b_{j} Punkte eingetragen worden sind. Im worst case ist also ein Datenblock mit b_{k} Punkten gefüllt, während alle anderen ∑_{j=1}^{k−1} b_{j} Datenblöcke genau einen Punkt enthalten.

Weitere Analysen zum Zusammenhang zwischen der Anordnung von Punkten im mehrdimensionalen Raum und der Größe der zugehörigen Directorymatrix findet man in [Regnier 84], [Nievergelt 84], [Mendelson 82] und [Tamminen 82].

Aufwand für die einzelnen Operationen

Das Grid File wurde schon in den 70’er Jahren entwickelt. Damals arbeitete man mit wesentlich kleineren Hauptspeichern, so daß davon ausgegangen wurde, daß die Directorymatrix und die Datenblöcke auf Externspeicher gehalten werden. Wenn die Scales im Hauptspeicher verwaltet werden, müssen wir also beim Suchen nur beim Zugriff auf die Directorymatrix und beim Zugriff auf den Datenblock auf den Sekundärspeicher zugreifen. Somit sichert dieses Verfahren das Zwei-Zugriffs-Prinzip zu. Wir gehen im weiteren von einem k-Ebenen-Directory D mit Kapazitätsparameter P aus, das ebenso wie die Datenblöcke im Hauptspeicher gehalten werden kann.

Definition 40 Gegeben sei ein Blockdirectory B, das als d-dimensionale Matrix organisiert ist, mit i_{k} Intervallen in Dimension k ∈ {1, …, d} und p, q ∈ IR^{d}. Der Teilraum U′ ⊆ U(B), der von den Matrixzellen

[x_{1}, y_{1}) × ⋯ × [x_{d}, y_{d}) x_{k}, y_{k} ∈ {1, 2, …, i_{k}} für k ∈ {1, …, d}

überdeckt wird, heißt U(B[x, y]). Die Überdeckungszahl ist dann:

Ü(B, R(p, q)) = \{ \begin{matrix}Π_{k=1}^{d}i_{k} & falls & R(p, q) ⊇ U(B) \\ Π_{k=1}^{d}(y_{i} − x_{i} + 1) & falls & R(p, q) ⊉ U(B)∧ \\ & & R(p, q) ∩ U(B) ≠ ∅ ∧ \\ & & Gleichungen 15, 16 gelten \\ 0 & sonst \end{matrix}

x, y ∈ i_{1} × i_{2} × ⋯ × i_{d}:

U(B[x, y]) ⊇ (R(p, q) ∩ U(B))  (15)

∀x′, y′ ∈ i_{1} × ⋯ × i_{d} ∧ x ≠ x′, y ≠ y′:

U(B[x′, y′]) ⊃ U(B[x, y]) ∨ U(B[x′, y′]) ⊉ (R(p, q) ∩ U(B))  (16)

Die Überdeckungszahl gibt für ein Blockdirectory B und eine Region R(p, q) genau die Anzahl der Gridzellen in B an, die überprüft werden müssen, um festzustellen, ob in der Region R(p, q) Punkte liegen, die in B gespeichert sind. S sei die Punktemenge aus dem d-dimensionalen euklidischen Raum, die im Grid File gespeichert ist.

• A(S, d, Suchen(p)) ≤ kd + b_{k} Wir haben für jede Directoryebene die d Scales zu berechnen und einen Datenblock zu durchsuchen.

• A(S, d, Bereichsuche(R(p, q))) ≤ w + rb_{k} + ∑_{i=1}^{k−1} ∑_{B∈D(i)} Ü(B, R(p, q)) Der Aufwand für die Bereichsuche ist davon abhängig, wieviele Gridzellen im Wurzeldirectory und in jedem Blockdirectory von der Region R(p, q) überdeckt werden. Wenn im Wurzeldirectory w Gridzellen überdeckt werden und insgesamt r Datenblöcke durchsucht werden müssen, ergibt sich die obige Aussage. In der Bereichsuche in Abb. 21 überdeckt die Region R((20,40),(40,75)) w = 4 Gridzellen im Wurzeldirectory, und es müssen r = 3 Datenblöcke durchsucht werden. Wenn das 1-Ebenen-Directory nicht im Hauptspeicher gehalten werden kann, muß eventuell w mal auf den Externspeicher zugegriffen werden. Diese Eigenschaft führte zur Entwicklung des k-Ebenen-Directories. Wenn für das k-Ebenen-Directory das Wurzeldirectory im Hauptspeicher gehalten wird, und nur die restlichen Directoryebenen auf Externspeicher ausgelagert sind, reichen k − 1 Zugriffe auf den Externspeicher aus, falls ein Blockdirectory B ∈ D(k − 1) existiert, mit:

U(B) ⊇ R(p, q)

• Wenn es beim Einfügen zu keiner Kollision kommt, d.h. in dem entsprechenden Datenblock ist die maximale Blockkapazität noch nicht erreicht, gilt: A(S, d, Einfügen(p)) = A(S, d, Suchen(p)). Falls allerdings eine Kollision auftritt, die eine Teilung der Blockdirectories notwendig macht, hängt der entstehende Aufwand von der Implementierung der Blockdirectories ab. Wenn tatsächlich eine Matrix verwendet wird, entsteht beim Einfügen ein hoher Aufwand, aber die Zugriffsoperationen bleiben effizient. Umgekehrt verhält es sich, wenn Listenstrukturen verwendet werden. Analoges Verhalten ergibt sich beim Löschen [Nievergelt 84].

4.5 Grid-Quad-Bäume

Einfügen und Löschen in k-D-Bäumen führt, solange man dies mit einfachen Verfahren realisiert, unter Umständen zu sehr unausgeglichenen Bäumen. Bereichsanfragen sind dann nicht mehr effizient zu realisieren. Beim Grid File führen diese Operationen zu einem wesentlich höheren Speicheraufwand wegen dem Matrixprinzip, der durch das k-Ebenen-Directory auch nur um einen konstanten Faktor vermindert wurde. Wir stellen nun ein kombiniertes Verfahren die Grid-Quad-Bäume vor.

Der allgemeine Fall für d Dimensionen ergibt sich direkt aus dem 2-dimensionalen Fall. Gegeben sei eine Punktemenge S in U = [0, 2^{l}]^{2}. Wie beim Grid File gibt es Datenblöcke mit einer maximalen Kapazität b, in denen die Punkte aus S gespeichert werden. Wir bauen einen 4-Baum T auf, wobei nur den Blättern Datenblöcke entsprechen. Jedem Knoten v ist außerdem eine Region R(v) zugeordnet. Wenn der Knoten u ein Vaterknoten von v ist und R(u) = [u_{1}, o_{1}] × [u_{2}, o_{2}], dann folgt für R(v):

falls u.00 = v, R(v) = [u_{1}, \frac{u_{1}+o_{1}}{2} ] × [u_{2}, \frac{u_{2}+o_{2}}{2} ]
falls u.01 = v, R(v) = [u_{1}, \frac{u_{1}+o_{1}}{2} ] × [\frac{u_{2}+o_{2}}{2} , o_{2}]
falls u.10 = v, R(v) = [\frac{u_{1}+o_{1}}{2} , o_{1}] × [u_{2}, \frac{u_{2}+o_{2}}{2} ]
falls u.11 = v, R(v) = [\frac{u_{1}+o_{1}}{2} , o_{1}] × [\frac{u_{2}+o_{2}}{2} , o_{2}]

Für die Wurzel w vom Grid-Quad-Baum T gilt: R(w) = U.

Es folgt hieraus für die Größe von Regionen:

∀_{v∈Level(i)} |R(v)| = 2^{2(l−i+1)}

Wir benutzen wieder den Operator VGL(), den wir im Abschnitt 4.3 über Quad Trees definiert hatten, zur Bestimmung der Folgeknoten. Da dem inneren Knoten v ∈ T kein Punkt aus S entspricht, benutzen wir den Mittelpunkt von R(v).

Definition 41 Für eine Region R = [u_{1}, o_{1}] × [u_{2}, o_{2}] × ⋯ × [u_{d}, o_{d}] heißt M(R) := (\frac{u_{1}+o_{1}}{2} , \frac{u_{2}+o_{2}}{2} , …, \frac{u_{d}+o_{d}}{2} ) der Mittelpunkt von R.

Das Einfügen der Punkte aus S in einen Grid-Quad-Baum T erfolgt dann durch Aufrufe der folgenden Funktion Einfügen(w, s), wenn w die Wurzel von T und s ∈ S ist. Alle Punkte aus einem Datenblock B bezeichnen wir als P (B).

Einfügen (v : Knoten, s : Punkt); IF v entspricht einem Datenblock B THEN IF A(B) < b

THEN s in B eintragen;

ELSE Tieferhängen(v, P (B) ∪ {s}); ENDIF;

ELSE Einfügen(V GL(M(R(v)), s), s); ENDIF; ENDEinfügen;

Tieferhängen (v : Knoten, P : Punktemenge); IF A(B) ≤ b

THEN erzeuge einen neuen Datenblock B und setze v := B;

Trage die Menge P in B ein; ELSE erzeuge neue Knoten v.ij für i, j ∈ {0, 1};

Teile P in P_{00}, P_{01}, P_{10}, P_{11}, so daß gilt

∀_{s∈P_{ij}} V GL(v, s) = v.ij für i, j ∈ {0, 1}
Tieferhängen(v.ij, P_{ij}) für i, j ∈ {0, 1}

ENDIF; ENDTieferhängen;

Das Löschen im Grid-Quad-Baum T wird durch einen Aufruf der folgenden Funktion Löschen(w, s) vorgenommen, wenn w die Wurzel von T ist.

Löschen (v : Knoten, s : Punkt); IF v entspricht einem Datenblock B

THEN IF s ∈ B

THEN B := B\{s};

Höherhängen(v, B); ELSE s ist nicht vorhanden

ENDIF; ELSE Löschen(V GL(M(R(v)), s), s);

ENDIF; ENDLöschen;

Höherhängen (v : Knoten, P : Punktemenge) w sei der Vater von Knoten v IF ∀_{i,j∈{0,1}} w.ij entspricht einem Datenblock B

THEN IF ∑_{i,j∈{0,1}} A(w.ij) ≤ b

THEN P := ⋃_{i,j∈{0,1}} P (w.ij); trage P in einen Datenblock B ein w := B; lösche w.ij für i, j ∈ {0, 1}; Höherhängen(w, B);

ENDIF;

ENDIF; ENDHöherhängen;

Bem. Wenn wir eine Folge von Einfüge- und Löschoperationen in einem Grid-Quad-Baum T betrachten, dann spielt offensichtlich die Reihenfolge der Operationen für die Struktur von T keine Rolle. Wenn wir alle möglichen Punktemengen S als S^{∗} und alle möglichen Grid-Quad-Bäume als T^{∗} bezeichnen, dann gibt es folglich eine

Funktion: GQB : S^{∗} ⟶ T^{∗}.

Satz 18 Gegeben sei ein euklidischer Raum U = [0, 2^{l}]^{d}, eine Punktemenge S aus U mit Spärlichkeit c für δ = \frac{1}{2}, dann gilt für eine Datenblockkapazität b ≥ c: H(GQB(S)) ≤ l.

Bew. Im worst case hat die Menge S maximale Größe, d.h. der Raum U ist maximal mit Punkten aus S angefüllt: |S| = 2^{dl}c. Wäre H(MS(S)) = l + 1, dann gäbe es im Grid-Quad-Baum GQB(S) einen Knoten v ∈ Level(l), der ein innerer Knoten ist mit:

∑_{i,j∈{0,1}} A(v.ij) > b

Wegen |R(v)| = 1 kommt es zum Widerspruch zur Spärlichkeit c.

Satz 19 Gegeben sei ein Raum U = [0, 2^{l}]^{d}, eine Punktemenge S aus U mit Spärlichkeit c für δ = \frac{1}{2}, eine maximale Datenblockkapazität b ≥ c, eine Region R = [u_{1}, o_{1}]×⋯×[u_{d}, o_{d}] mit k_{i} = o_{i} − u_{i} (i ∈ {1, 2, …, d}) und ein Grid-Quad-Baum T, in dem S gespeichert ist. S′ ⊆ S sei die Menge der gefundenen Punkte in der Bereichsuche, dann gilt:

A(S, d, Einfügen()) ≤ (b + 1)dl
A(S, d, Löschen()) ≤ l + 2^{d}l
A(S, d, Bereichsuche(U_{1}())) ≤ 2^{d}(l + c)
A(S, 2, Bereichsuche(R)) ≤ 2l (⌈\frac{|S′|}{b + 1}⌉ + 1) + |S′| + \frac{8(⌈k_{1}⌉ + ⌈k_{2}⌉)}{3} c
A(S, d, Bereichsuche(R)) ≤ d l (⌈\frac{|S′|}{b + 1}⌉ + 1) + |S′|
+ 2 (Π_{i=1}^{d}(⌈k_{i}⌉ + 1) − Π_{i=1}^{d}(⌈k_{i}⌉ − 1)) c

Bew. Beim Einfügen muß in jedem Level der Operator VGL(), der d Berechnungsschritte durchführt, ausgewertet werden. Falls alle b + 1 Punkte in einer Region liegen, passiert dies für jeden Punkt. Wegen der maximalen Baumhöhe l folgt die erste Aussage. Beim Löschen kann im worst case ein Knoten v ∈ Level(l) gelöscht werden, der ’Verschmelzungen’ bis zur Wurzel nach sich zieht. Es müssen jeweils 2^{d} Folgeknoten bestimmt werden. Die 1-Umgebung U_{1}() kann nur c Punkte enthalten und höchstens 2^{d} Regionen R(v) für v ∈ Level(l) überdecken. Wir unterscheiden für die Aufwandsbetrachtung der Bereichsuche, ähnlich wie in Theorem 1, die Knoten des Grid-Quad-Baums T, die durchsucht werden müssen:

\begin{aligned}X & = & \{v|v ∈ T, R(v) ⊆ R\} \\ Y & = & \{v|v ∈ T, R(v) ∩ R ≠ ∅ ∧ R(v) − R ≠ ∅\} \end{aligned}

Man beachte, daß nicht jedem Knoten von T ein Punkt aus S entspricht. b+1 Punkte können im worst case in zwei Datenblöcken gespeichert sein, die zwei Knoten aus Level l entsprechen. Daraus folgt: |X| ≤ l (⌈\frac{|S′|}{b+1}⌉ + 1). Außerdem muß beim Absteigen im Baum T der Folgeknoten ausgewählt werden, was zwei weitere Operationen für jeden Knoten benötigt. Die Knoten aus Y unterscheiden wir nach dem Level (i ∈ {1, 2, …, l}):

Y_{i} = {v|v ∈ Y, v ∈ Level(i)}

Da |R(v)| = 1 für die Knoten v ∈ Level(l) gilt, wissen wir:

|Y_{l}| ≤ 2(⌈k_{1}⌉ + ⌈k_{2}⌉)

Da T ein 4-Baum ist, gilt für i ∈ {1, 2, …, l − 1}:

|Y_{i}| ≤ \frac{|Y_{i+1}|}{4}  (17)
≤ |Y_{l}|(1/4)^{l−i}
|Y | ≤ ∑_{i=1}^{l} |Y_{i}|

≤ |Y_{l}| ∑_{i=0}^{l−1}(1/4)^{i}

= |Y_{l}|\frac{(1/4)^{l} − 1}{−3/4}
< |Y_{l}|4/3
≤ \frac{8(⌈k_{1}⌉ + ⌈k_{2}⌉)}{3}

Für die Bereichsuche im d-dimensionalen euklidischen Raum ergibt sich die Abschätzung für |X| analog wie im 2-dimensionalen Fall, während die Knotenmenge Y_{l} aus (Π_{i=1}^{d}(⌈k_{i}⌉ + 1) − Π_{i=1}^{d}(⌈k_{i}⌉ − 1)) Knoten v bestehen kann, mit

|R(v)| = 1. Da T ein 2^{d}-Baum ist, gilt analog zu Gleichung 17: |Y_{i}| ≤ \frac{|Y_{i+1}|}{2^{d}} für i ∈ {1, 2, …, l − 1}. Die Summation ergibt: |Y | < 2|Y_{l}|.

5 Systementwurf und Spezifikation

5.1 Operationen des FGM-Systems

Welche Fragen sollen zu einer gegebenen Personenmenge P = {p_{1}, …, p_{n}} durch das FGM-System beantwortet werden? Gegeben sei uns ein Maximal- und ein Bewertungsparameter M, B ∈ (IR^{+})^{3}.

1. partner(P) : Liste von Personenpaaren Es wird eine maximale Relation P ART NER ⊆ P × P gebildet, so daß ∀(p, p′) ∈ P ART NER gilt:

C({p, p′}) ≤ M

2. fgm(p,F) : Liste von Fahrgemeinschaften Für eine Person p ∈ P und Fahrgemeinschaften F = {f_{1}, …, f_{m}} wird eine maximale Menge von Fahrgemeinschaften F′ ⊆ F berechnet, so daß ∀_{f∈F′} gilt:

C(f ∪ {p}) ≤ M

3. partitionMaxST(P) : Partition von P Es wird eine Partition F von P gebildet, so daß gilt:

∀_{Partitionen F′ von P} ST (F) ≥ ST (F′)

4. partitionMonMaxST(P) : Partition von P Es wird ausgehend von der Partition F_{0} = {{p_{1}}, {p_{2}}, …, {p_{n}}} von P eine Partition F gebildet, für die gilt:

(a) Es gibt eine streng monoton wachsende Partitionenfolge von F_{0} nach F.

(b) ∀_{Partitionen F′ von P mit d(F,F′)=1} ST (F′) ≤ ST (F)

5. partition(P) : Partition von P Es wird eine Partition F = {f_{1}, …, f_{m}} von P berechnet, so daß ∀_{f,f′∈F} gilt:

(a)  C(f) ≤ M
(b)  C(f ∪ f′) > M

Der Operator partner(P) berechnet für alle Personen p ∈ P eine Liste von Personen, die aufgrund der Arbeitszeiten und -wege mit p eine Fahrgemeinschaft bilden können. Für bereits bestehende Fahrgemeinschaften F und eine Person p werden durch die Operation fgm(p,F) aus F genau die Fahrgemeinschaften ausgewählt, die mit p aufgrund der Arbeitszeiten und -wege und der Personenanzahl eine Fahrgemeinschaft bilden können. Das Ergebnis beider Operatoren ist eindeutig, da wir verlangt haben, daß es bzgl. der Kardinalität maximal sein soll. Der Operator partition(P) berechnet kein eindeutiges Ergebnis, sondern es wird duch die zweite Bedingung nur sichergestellt, daß sich aus F nicht durch einfache Zusammenfassung zweier Fahrgemeinschaften eine kleinere Partition von P berechnen läßt, die Bedingung 5a erfüllt.

Bem. Es gibt Partitionen F_{1} und F_{2} von P mit |F_{1}| < |F_{2}|, die die Bedingungen aus 5a und 5b erfüllen (s. Abb. 23).

[figure: s[a]; z[a]; s[b]; z[b]; s[c]; z[c]; s[d]; z[d]]

Abbildung 23: partition(P) ist nicht eindeutig.

Die Knoten s[i], z[i] bezeichnen den Start- und den Zielort von Fahrer i ∈ {a, b, c, d}. Alle Knotenpaare (u, v), zwischen denen eine Kante eingezeichnet ist, besitzen den Zeitabstand d_{z}(u, v) = 1. Die restlichen Knotenpaare haben den Zeitabstand zwei. Für den Maximalparameter M = (0, 2, 2) erfüllen die Partitionen F_{1} = {{a, b}, {c, d}} und F_{2} = {{a}, {b, c}, {d}} die Bedingungen 5a und 5b.

5.2 Aufwandsbetrachtungen

Wie hoch ist der maximale Aufwand zur Beantwortung der vorgestellten Operatoren? Die Anzahl von Berechnungsschritten, die in konstanter Zeit durchzuführen sind, um den Operator op zu berechnen, bezeichnen wir als A(). Wir gehen davon aus, daß folgende Abfrage für die Charakteristik C() und den Maximalparameter M in konstanter Zeit durchgeführt werden kann:

• C(f) ≤ M

Im Worst Case gilt:

A(partner(P)) ≤ |P |(|P | − 1)
A(fgm(p, F)) ≤ |F | ≤ |P |
A(partition(P)) ≤ (|P | − 1)^{2}

Um partner(P) zu berechnen, werden alle |P |(|P | − 1) Personenpaare getestet. Man beachte, daß transitive Eigenschaften für die Charakteristik einer Fahrgemeinschaft nicht bestehen. Um fgm(p,F) zu berechnen, ist die Charakteristik von |F | Fahrgemeinschaften zu bestimmen. Zur Berechnung von partition(P) könnten wir die einzelnen Fahrgemeinschaften sukzessive aufbauen. Solange es eine Person p gibt, die in eine Fahrgemeinschaft f bzgl. der Charakteristik eingefügt werden kann, wird dies getan, ansonsten wird die nächste Fahrgemeinschaft aufgebaut. Es kann so nicht passieren, daß zwei Fahrgemeinschaften f_{1}, f_{2} nacheinander aufgebaut werden, die auch zusammen die Bedingungen 5a und 5b erfüllen, denn dann müßte sich in f_{2} eine Person befinden, um die f_{1} beim Aufbau vergrößert worden wäre. Da sich die Kardinalität der Partition jedesmal um eins verringert, werden höchstens |P | − 1 Partitionen gebildet.

Satz 20 Das Problem, den Operator partitionMaxST(P) zu berechnen, ist NP − hart.

Bew. Wir führen folgende Reduktion durch:

EFGM-3-IR^{2} ≤^{p} partitionMaxST()

Eine Eingabe von EFGM-3-IR^{2} besteht aus einer Personenmenge P, einem euklidischen FGM-Graph G = (V, E, γ) und einer Umwegschranke c ∈ IR. Die Knoten von G entsprechen den Start- und Zielorten aller Personen von P und die Gewichtsfunktion γ gibt den euklidischen Abstand zwischen zwei Knoten an. Die Koordinaten eines Knotens v ∈ V sind als (v_{1}, v_{2}) angegeben. Gesucht ist eine Partition F = {F_{1}, …, F_{|P |/3}} von P, für die folgendes gelten soll:

• ∀_{f∈F} |f| = 3

• ∀_{f∈F} U(f) ≤ c

Für den Nachweis, daß EFGM-3-IR^{2} NP − hart ist, siehe [Buchholz 94]. Den FGM-Graph G = (V, E, γ) benutzen wir direkt als Verkehrsgraph G′ = (V, E, K, γ, 1) mit: K_{1}(v) = v_{1}, K_{2}(v) = v_{2}. Die Durchschnittsgeschwindigkeit sei für alle Kanten eins, so daß d_{z}(u, v) = γ(u, v) ∀_{u,v∈V} gilt.

Durch die Wahl des Maximalparameters M = (0, c, 3) ist zugesichert, daß die Fahrgemeinschaften höchstens einen Umweg von c Einheiten machen und höchstens drei Personen beinhalten. Durch die Wahl des Bewertungsparameters B = (0, 0, 1) ergibt sich die Stabilität von einer Partition F zu:

ST (F) = ∑_{f∈F} ST (f)^{2} = ∑_{f∈F} |f|^{2}

Das Maximieren von ST (F) über alle möglichen Partitionen erzeugt also Fahrgemeinschaften der Größe drei.

ST (F) = 3|P | ⟺ EFGM-3-IR^{2} hat eine Lösung

Der Operator partitionMonMaxST(P) läßt sich durch folgenden Algorithmus berechnen:

F := F_{0} ; F_{h} := F_{0} ; WHILE TRUE DO

max := 0 ;

FOR p ∈ P DO

FOR f ∈ F DO

h := ST (F) − ST (F′) ;
IF h > max THEN max := h; F_{h} := F′; ENDIF;

ENDFOR; ENDFOR; IF max > 0 THEN F := F_{h}; ELSE ” F ist maximal! ” ENDIF; ENDWHILE;

F′ in der innersten FOR-Schleife sei die Partition, die aus F durch die Personenumsetzung von p nach f entsteht. Wenn es tatsächlich keine Personenumsetzung mehr gibt, die die Stabilität vergrößert, bricht der Algorithmus mit ” F ist maximal! ” ab. Da es eine maximale Stabilität gibt und die Stabilität bei jedem Schleifendurchlauf echt vergrößert wird, terminiert das Verfahren. Zwar benötigen die inneren beiden FOR-Schleifen höchstens |P |^{2} Berchnungsschritte, aber es bleibt offen, wie oft die WHILE-Schleife durchlaufen wird.

5.3 Optimierungen

Bei den Aufwandsbetrachtungen haben wir immer sehr einfache Verfahren angenommen, die sich aber tatsächlich kaum verbessern lassen, da die Umwege und die Abweichungen der Arbeitszeiten von Fahrgemeinschaften sich nicht transitiv verhalten (∃p_{1}, p_{2}, p_{3} ∈ P U({p_{1}, p_{2}}) ≤ c ∧ U({p_{2}, p_{3}}) ≤ c ∧ U({p_{1}, p_{3}}) > c für c ∈ IR+). Daher können wir aus bereits vorgenommenen Berechnungen nur wenig für noch durchzuführende Berechnungen schließen. Da die Charakteristik und die Stabilität von Fahrgemeinschaften die Umwege und die Abweichungen der Arbeitszeiten beinhalten, gelten auch für sie keine transitiven Eigenschaften. Wir nehmen die Strategie aus Abschnitt 3.3 wieder auf und vergleichen nur Personen miteinander, deren Wohn- und Arbeitsorte sowie die Arbeitszeiten nahe beieinander liegen. Die Operation Bereich(p, c) für ein geeignetes c ∈ (IR^{+})^{6} wird durch geometrische Algorithmen (s. Kapitel 4) effizient durchgeführt. Die genannten Anfragen werden dann für einen Maximalparameter M wie folgt gelöst:

partner(P); FOR p ∈ P DO

FOR p′ ∈Bereich(p, c) DO

IF C({p, p′} ≤ M THEN (p, p′) ∈ P ART NER; ENDIF; ENDFOR;

ENDFOR;

fgm(p,F); FOR p′ ∈Bereich(p, c) DO

IF ” f_{p′} ∈ F ist noch nicht getestet ”

THEN IF C(f_{p′}) ∪ {p}) ≤ M THEN F′ := F′ ∪ {{p}}; ENDIF; ENDIF;

ENDFOR;

f_{p′} sei die Fahrgemeinschaft in F, zu der p′ gehört. Da es mehrere Personen im Bereich(p, c) geben kann, die in einer Fahrgemeinschaft f fahren, braucht C(f_{p′} ∪ {p}) ≤ M nur einmal getestet zu werden. Analog vereinfachen wir die anderen Anfragen. Im durchschnittlichen Laufzeitverhalten werden wir durch die Strategie, für jede Person p nur alle Personen aus Bereich(p, c) zu testen, einen günstigeren Aufwand erzielen.

5.4 Kontroll- und Datenfluß

Das Fahrgemeinschaftssystem umfasst drei Typen von Daten: Verkehrsdaten, Personendaten und temporäre Daten, die in einzelnen Modulen verwaltet werden. Für jedes Modul gibt es ein Interface, das bestimmte Operationen zur Verfügung stellt. Die Algorithmen beispielsweise zur Suche kürzester Wege sowie zur Verwaltung des Grid Quad Baumes sind dadurch abgekapselt (s. Abb. 24).

[figure: Verkehrsinterface; Personen und; Eigenschaften; Umwege; Partitionen; Zeitabstände; etc.; Verkehsnetz; Auf- und; Abfahrtslisten; Vorbehandelter; Verkehrsgraph; Fahrgemeinschaften; Verkehrsgraph; Grid Quad Baum; Verkehrsdaten; Personendaten; Temporäre Daten; Transformation; Personeninterface; FGM System Interface; Überführung; T-Dateninterface]

Abbildung 24: Das Fahrgemeinschaftssystem.

• Verkehrsdaten Das real existierende Verkehrsnetz wird in einen Verkehrsgraph überführt. Da es bereits einige kartographische Informationssyteme gibt, ist es nicht mehr nötig, die Daten per Hand einzugeben, sondern man kann diesen Schritt automatisieren. Eine einheitliche Schnittstelle zumindest auf der Ebene von Landesvermessungs- und Straßenbauämtern ist das EDBS-Format [Stöppler 91]. Leider umfassen die von diesen Ämtern erfassten Daten nicht alle für uns wichtigen Informationen, aber vermutlich kann man in Zukunft davon ausgehen, daß die entsprechenden Informationen in digitaler Form vorliegen. Der Verkehrsgraph selbst wird als Adjazenzliste gespeichert, da von jedem Knoten nur wenige Kanten wegführen. Der vorbehandelte Verkehrsgraph hingegen muß als Adjazenzmatrix gespeichert sein, so daß mit einem Zugriff der Zeitabstand von einem Knotenpaar bestimmt werden kann. Die Auf- und Abfahrtslisten AU(u), AB(u) werden nur erstellt, wenn es eine Person gibt, deren Wohn- oder Arbeitsort dem Knoten u zugeordnet ist. Dabei werden werden Daten aus dem Verkehrsgraphen und dem vorbehandelten Verkahrsgraphen benötigt, was in Abb. 24 durch Pfeile dargestellt ist. Das Verkehrsinterface stellt für alle Knoten u, v des Verkehrsgraphen folgende Operationen bereit: d_{z}(u, v), d̃(u, v), d_{e}(u, v), d_{l}(u, v), γ(u, v), δ(u, v), K(v) Weiterhin muß folgendes möglich sein:

– Ändern, Einfügen und Löschen von Knoten und Kanten im Verkehrsgraphen

– Erstellen und Löschen von Auf- und Abfahrtslisten, sowie die Angabe das Verlängern oder Verkürzen der Listen

– Verändern des vorbehandelten Graphen bzgl. der Wahl der Knotenmenge und der Unterteilung der Ebene in Zellen

Man beachte, daß beispielsweise das Einfügen von Kanten im Verkehrsgraphen Veränderungen der Auf- und Abfahrtslisten und des vorbehandelten Graphen nötig machen können. Es sollte die Möglichkeit bestehen, daß dies automatisch berechnet wird.

• Personendaten Alle Personen werden samt allen Eigenschaftsinformationen und der Fahrgemeinschaft, der sie angehören, in einem Feld gespeichert und in den Grid Quad Baum eingetragen. Die Fahrgemeinschaften, die tatsächlich existieren, sind nochmals abgespeichert. Beim Löschen einer Person muß dies also in drei Datenmengen geschehen. Das Personeninterface ermöglicht die Operation Bereich(p, c) sowie folgende Berechnungen zum

– Angeben, Ändern, Löschen und Erweitern der bestehenden Fahrgemeinschaften

– Einfügen und Löschen von Personen; Ändern der Eigenschaften von Personen

Im Hintergrund sollte die Verwaltung der geometrischen Datenstrukturen (Grid Quad Baum o.ä.) ablaufen.

• Temporäre Daten Um die gleichen Berechnungen nicht ständig erneut durchzuführen, werden bestimmte Ergebnisse aufbewahrt. Dazu gehören Zeit-, Weg-, oder euklidischer Abstand eines Weges oder Knotenpaares, Umwege von Fahrgemeinschaften, Teilpartitionen mit Stabilität etc. Durch Speicherung dieser Daten kann im ständigen Betrieb des FGM-Systems unnötiger Rechenaufawnd vermieden werden. Das T-Dateninterface stellt nur das Einfügen, Löschen und Abfragen dieser Daten zur Verfügung.

• Fahrgemeinschaftssysteminterface (FGM-I) Das FGM-I umfasst alle Operationen der genannten Interfaces und einige komplexere Operationen. Das Einfügen einer Person im FGM-System verlangt das Einfügen in die Personendaten wie auch die Berechnung einer Auf- und einer Abfahrtsliste. Das Löschen einer Person verlangt das Löschen in den Personendaten und das Löschen der Auf- und Abfahrtslisten dieser Person. Ebenso verhält es sich, wenn Kanten im Verkehrsgraph verändert werden. Es müssen dann eventuell die Umwege von Fahrgemeinschaften, die in den temporären Daten gespeichert sind, gelöscht oder verändert werden. Weiterhin werden die bereits in Abschnitt 5.1 vorgestellten Operationen zur Verfügung gestellt, wobei ein Maximal- und ein Bewertungsparameter gegeben sei. P artner(P), fgm(p, F), partition(P), partitionMonMaxST (P)

– Berechnung des Umweges einer Fahrgemeinschaft

– Berechnung aller möglichen Partner von einer Person. p : {p′| C({p, p′}) ≤ M}

6 Ausblick

Aufbauend auf dieser Arbeit ist eine Implementierung eines FGM-Systems durchzuführen. Mit diesem System sollten dann empirische Untersuchungen die Güte der geometrischen Suche mittels Grid-Quad-Bäumen, des vorbehandelten Verkehrsgraphen und über die Berechnungen von monoton steigenden und streng monoton steigenden Partitionenfolgen gemacht werden, d.h. eine Bewertung der eingesetzten Strategien. Grid-Quad-Bäume sind eine effiziente dynamische Datenstruktur, die unabhängig von der Reihenfolge des Einfügens und des Löschens ist. Aus diesem Grund sollten sich weitere Aufwandsuntersuchungen zur Berechnung von c-Paare (s. Kapitel 5.1) und beispielsweise der Suche nach dem nächsten Nachbarn anschließen. Wir haben ein Gütemaß, die Stabilität für Fahrgemeinschaften, in Kapitel 3.4 entworfen und gezeigt, wie dieses eingesetzt werden kann, um zu einer günstigeren Partitionierung zu gelangen. Über die Länge von monotonen Partitionenfolgen sind theoretische Untersuchungen durchzuführen. Bei der Modellierung eines realen Straßennetzes als Verkehrsgraph haben wir kaum Einschränkungen bzgl. der Kantengewichte gemacht, um keine Speziallösung anzubieten. Besonders bei der Überwindung von kleinen Entfernungen in einem Verkehrsnetz gibt es sehr große Abweichungen der Zeitabstände. Dies trifft für größere Entfernungen nicht mehr zu. Wir hatten die Knotenpaare durch einen Grenzparameter in Äquivalenzklassen bzgl. der euklidischen Abstände eingeteilt. Hierzu sind praktische Untersuchungen durchzuführen, die das Konzept rechtfertigen und die Wahl des Grenzparameters bewerten. Eine genauere Modellierung eines realen Verkehrsnetzes, so daß Ampeln, Vorfahrtstraßen usw. noch berücksichtigt werden, ist der entgegengesetzte Ansatz und führt eher zur Verkehrssimulation. Zur effizienteren Berechnung des vorbehandelten Verkehrsgraphen sowie zum On-Line Einfügen von Kanten und der Veränderung der Kantengewichte im Verkehrsgraphen sind ebenfalls weitere Untersuchungen durchzuführen (s. Literaturangaben im Anhang A.5). Bei der Erstellung der Auf- und Abfahrtslisten für jede Person betreiben wir die kürzeste Wegsuche im Verkehrsgraphen nur in einem sehr kleinen Teil des Graphen. Aus diesem Grund lassen sich diese Berechnungen für eine Menge von Personen gut parallelisieren. Für die Berechnungen der Operationen: partner(P), fgm(p,F), partition(P) und partition-MonMaxST(P) (Kapitel 5) lassen sich ebenfalls parallele Konzepte einsetzen. Wie dies im einzelnen realisiert werden soll, welche Zugriffskonflikte auftreten können und wie diese aufzulösen sind, muß festgelegt werden. Es gibt bereits einige Informationssysteme, die Zusammenstellung von Fahrgemeinschaften ermöglichen (z.B. am Regionalen Rechenzentrum der Universität Stuttgart RUS: ’Känguruh - Uni Mitfahrzentrale’). Diese Systeme benutzen keinen Verkehrsgraphen, und Gütemaße für Fahrgemeinschaften sind nicht notwendig, da Fahrgemeinschaften selbst nicht abgebildet werden. Die Systeme funktionieren lediglich als ’schwarze Bretter’, d.h. Personen können Angebote und Gesuche stellen und die vorhandenen Angebote und Gesuche lesen. Ein interaktives Back-End auf das FGM-System kann diese Dienste ebenfalls zur Verfügung stellen. Jede Person kann sich außerdem eine Vorauswahl von ’passenden’ Personen oder Fahrgemeinschaften anzeigen lassen oder den günstigsten Verkehrsweg wählen. Auch in Zukunft wird die Verkehrsvermeidung zur Befriedigung der Mobilitätsbedürfnisse eine wichtige Rolle spielen. Leider scheint man zur Zeit die Prioritäten auf Verbesserung des Verkehrsflusses durch seine Verteilung auf noch mehr Verkehrswege gesetzt zu haben. Nicht nur unter Gesichtspunkten des Umweltschutzes ist dies ein fataler Irrweg, wenn sich Studien, die eine Erhöhung des Verkehrsaufkommens bis zum Jahr 2010 um 40% - 70% prognostizieren, auch nur zum Teil bewahrheiten [Taxistop 94].

A Quellenangaben

A.1 Mobilitätszentrale

Im Rahmen des EG-Forschungsprojektes Carpooling System Management (DRIVE Forschungsprogramm [DRIVE(1) 90], [DRIVE(2) 90]) wurden Möglichkeiten der differenzierten Verkehrserschließung am Beispiel der Region Hameln praktisch untersucht. Es wurde eine Mobilitätszentrale realisiert, die sowohl Fahrgemeinschaften vermittelt als auch über öffentliche Verkehrsleistungen informiert. Am Lehrstuhl für Öffentliche Verkehrsund Transportsysteme der Bergischen Universität GH Wuppertal führten Prof. Dr. Fiedler und Dr. Reinkober insbesondere soziologische Untersuchungen (Akzeptanz, …) durch, währendessen die informationstechnische Unterstützung dem belgischen Partner, der Firma Taxistopp oblag ([Reinkober 94], s. A.4).

A.2 Verkehrssysteme

TSM Ein erster Versuch die anstehenden Verkehrsprobleme mit Hilfe eines Gesamtverkehrssystems zu lösen, wurde 1975 in den USA unter dem Begriff ’Transportation System Management’ (TSM) gestartet. Transportation System Management definiert sich wie folgt: Automobile, öffentliche Verkehrsmittel, Taxis, Fußgänger und Fahrräder sollen als Elemente eines einzigen städtischen Transportsystems angesehen werden. Die Zielsetzung des städtischen Verkehrsmanagements ist, diese individuellen Elemente durch operative, regulierende und produktive Praktiken zu koordinieren, um für das Gesamtsystem ein Maximum an Effizienz und Produktivität zu erreichen [TSM 86].

VSM Aufbauend auf den amerikanischen Erfahrungen wurde 1989 in Deutschland unter anderen Voraussetzungen ein Konzept zur direkten Beeinflußung von Angebot und Nachfrage entwickelt: das Verkehrs-System-Management (VSM). Sein Ziel ist, mit Hilfe von technischen und organisatorisch-betrieblichen Maßnahmen eine bessere Nutzung der Verkehrsmittel zu erreichen und diese in einem Gesamtverkehrssystem zum Einsatz zu bringen. Die Strategien zur Erreichung der Ziele umfaßen sowohl Maßnahmen zur Beeinflußung des motorisierten Individualverkehrs als auch des öffentlichen Verkehrs [FGSV 89] [FGSV 90].

Mobilitätsmanagement Neuere Forschungsarbeiten an der Bergischen Universität GH Wuppertal führen zur Konzeption des Mobilitätsmanagements. Im Gegensatz zum Verkehr-System-Management stehen beim Mobilitätsmanagement die persönlichen Anliegen des einzelnen Verkehrsteilnehmers und daraus abgeleitet gesamtverkehrliche und städteplanerische Ziele im Vordergrund der Aktivitäten. Durch eine individuelle Information jedes einzelnen und die Koordination aller Betriebsformen soll eine intelligente, umweltgerechte Verkehrsmittelwahl und damit eine Verkehrsreduzierung erreicht werden. Bezogen auf die Verkehrsmittelwahl wird angestrebt, die objektiv vorhandenen Vorteile der zu bevorzugenden Verkehrssysteme so zu vermitteln, daß sie der subjektiven Beurteilung der Nutzer gerecht werden. Dazu bedarf es u.a. eines gezielten politischen Marketings und einer offensiven Öffentlichkeitsarbeit [Reinkober 94].

A.3 Digitale Karten

Verkehrsministerium Das Bundesverkehrsministerium sowie die Länder haben 1968 Aufbau und Einsatzmöglichkeiten einer elektronisch geführten Straßendatenbank untersucht. Es entstand die Anweisung für eine Straßendatenbank (ASB), die festlegt welche Informationen (Straßenbreite, Baumaterial, Straßentyp (Kreisstraße, Landstraße, Bundesstraße, Bundesautobahn, …), etc.) in welcher Genauigkeit zu speichern sind. Vorrangiges Ziel war die statistische Erfassung aller Straßendaten. Die ASB wurde 1992 aktualisiert und dient bis heute als Grundlage für die Erfassung der Daten. Leider sind die Daten zum einen fehlerhaft eingegeben worden und aus finanziellen Gründen in verschiedenen Bundesländern auch weniger vollständig erfaßt (siehe A.4). In Zukunft sollen zu den bisher erfaßten Straßennetzdaten außerdem noch Verkehrsdaten (Unfälle, Verkehrsstärke, etc.), Bestandsdaten (Bauwerke, etc.) und einige weitere Informationen in ein Straßeninformationssystem (SIB) aufgenommen werden. Ein Nachteil für Fahrgemeinschaftensysteme ergibt sich in der Bundesrepublik Deutschland aus den Zuständigkeitsbereichen von Bund und Ländern. Der kleinste Straßentyp, der verzeichnet wird, ist die Kreisstraße. Innerhalb der Stadtgrenzen größerer Städte werden keine Straßen verzeichnet.

Vermessungsbehörden Die Landesvermessungsbehörden der Bundesrepublik Deutschland haben 1991 beschlossen, das digitale Amtliche Topographisch-Kartographische Informationssystem ATKIS nach einem einheitlichen Konzept zu entwickeln und aufzubauen. ATKIS besteht aus drei digitalen Landschaftsmodellen (DLM), welche die Landschaft in geometrischer Qualität beschreiben [ATKIS 91].

• DLM 25 entspricht der Topographischen Karte 1 : 250 000

• DLM 200 entspricht der Topographischen Übersichtskarte 1 : 200 000

• DLM 1000 entspricht der Internationalen Weltkarte 1 : 1 000 000

Die Landschaft wird nach vornehmlich topographischen Gesichtspunkten gegliedert, die topographischen Erscheinungsformen und Sachverhalte werden klassifiziert, und somit der Inhalt der Digitalen Landschaftsmodelle (DLM) festgelgt. In den Jahren 1991 - 1996 soll das DLM 25/1 als eine erste Realisierungsstufe des DLM 25 erfaßt werden. Grundlage sind neben den topographischen Karten auch Orthophotos im Maßstab 1:10 000 und die Informationssysteme TOPIS des Amtes für militärisches Geowesen und STABIS des statistischen Bundesamtes. Eine einheitliche Schnittstelle verschiedener digitaler Kartenmodelle ist durch das EDBS Format gegeben [Stöppler 91] [DVW 92] (ATKIS, ALK (Automatisierte Liegenschaftskarte), DHM (Digitales Höhenmodell), ALB (Automatisiertes Liegenschaftsbuch) [Karten 93]).

Bosch Die Firma Bosch erarbeitet mit anderen Firmen ein Pilot-Travel Projekt, mit Hilfe dessen es möglich sein soll, ein Fahrzeug durch unbekannte Städte zu leiten. Dabei wurde ein recht feines, digitales Straßennetz von allen größeren Städten in Deutschland angelegt. Dies soll in den nächsten Jahren kommerziell genutzt werden. Bosch hat der Universität Stuttgart Daten für den Großraum Stuttgart kostenlos zur Verfügung gestellt mit der Auflage, daß die Daten zu einem bestimmten Zeitpunkt vernichtet werden müssen und eben nicht kommerziell genutzt werden dürfen (siehe A.4).

A.4 Anschriften

Taxistopp Centrum voor positieve Aanwending, Onderbergen 51, Belgien-9000 Gent, Tel.:(32) 9 223 23 10, Fax.:(32) 9 224 31 44, Carpoolsoftware: ’SMARTPOOL the clever way to carpool’, Software basierend auf realen geographischen Daten, die Fahrgemeinschaften unterstützt.

Bergische Universität GH Wuppertal Öffentliche Verkehrs- und Transportsysteme, Prof. Dr. Fiedler, Assistent: Herr Paletta, Tel.: 0202 / 439 - 3091 (3186)

Mobilitätszentrale Hameln Tel.: 05151 / 19419 Es wird die im Rahmen des EG-Projektes erstellte Software (Carpoling System Management) zur Zusammenstellung von Fahrgemeinschaften benutzt. Es sind ca. 800 - 900 Personen gespeichert und pro Monat melden sich ca. 2-3 neue Interessenten. Eine Rückmeldung, ob sich Fahrgemeinschaften gebildet haben, ist nicht vorgesehen.

Robert Bosch GmbH Geschäftsbereich Mobile Kommunikation, Produktabteilung Digitale Karte, Marketing und Vertrieb Postfach 77 77 77, D-31132 Hildesheim (Herr Schultheiß)

Bundesministerium für Verkehr Referat StB 10, Postfach 200 100, 53170 Bonn Das Ministerium stellt die Anweisung für eine Straßendatenbank (ASB) zur Verfügung.

Ämter Staatliche Vermessungsämter, Städtische Vermessungsämter und Landesvermessungsbehörden siehe [Karten 93]

Reinkober Kreisverwaltung Reinsieg, Siegburg, Tel.: 02241 \ 132 395

A.5 Ergebnisse aus der Graphentheorie

Da wir zu Beginn unserer Arbeit einige Ergebnisse aus der Graphentheorie recherchiert haben, geben wir hier noch die Literaturangaben mit kurzen Erläuterungen an. Um die kürzeste Wegsuche in Verkehrsgraphen zu modifizieren, sind diese Ergebnisse hilfreich.

Die Aussagen beziehen sich auf Graphen mit n Knoten und m Kanten.

APSP = All Pairs Shortest Paths SSSP = Single Source Shortest Paths

• Dijkstra entwickelte 1959 einen Algorithmus zur Lösung von SSSP für Graphen mit positiven Kantengewichten, der O(n^{2}) Operationen benötigt. Alle Knoten werden dabei in drei Knotenmengen S, R, und U eingeteilt. Es sei SSSP für den Knoten s zu lösen, dann enthält S alle Knoten, zu denen die minimale Entfernung von s schon bestimmt ist. Die Knotenmenge R (Rand) ist über einen Knoten aus S erreichbar, und die Knoten aus U haben wir noch nicht untersucht. Wir führen höchstens n Iterationsschritte durch, indem wir jedesmal den nächsten Knoten zu s aus R nehmen und die Menge R entsprechend aktualisieren, da nun neue Knoten erreichbar sein können oder andere Knoten auf billigerem Weg erreicht werden können. Welche Datenstruktur für die Menge R verwendet wird, ist entscheidend für den Aufwand. Es werden auf der Datenstruktur nur die Operationen der Minimumbildung, der Aktualisierung der vorhandenen Elemente und Einfügen von neuen Elementen ausgeführt. Wenn wir für R einen Heap benutzen, benötigen wir höchstens O((m+n) log n) Operationen für SSSP, da die grundlegenden Operationen für Heaps höchstens O(log n) Operationen benötigen [Dijkstra 59].

• Floyd entwickelte 1962 den Tripel-Algorithmus, der zur Lösung von APSP Mittel aus der dynamischen Programmierung einsetzt, die zusichern, daß höchstens O(n^{3}) Operationen benötigt werden. Dabei werden sukzessive alle kürzesten Pfade über Knoten i von i = 1 bis i = |V | berechnet [Floyd 62].

• Fredman stellt 1976 eine Lösung für APSP von O(n^{3}(\frac{log log n}{log n})^{1/3}) vor [Fredman 76].

• Johnson adaptiert Dijkstra’s Algorithmus und Fibonacci Heaps 1977 zur Lösung von APSP in O(mn + n^{2} log n) Schritten, indem er parallel von allen Knoten aus sucht [Johnson 77].

• Fredman und Tarjan zeigen 1987 mittels Fibonacci Heaps eine Lösung für SSSP von O(n log n + m) [Fredman 87].

• Guibas, Hershberger, Leven, Sharir und Tarjan zeigen 1987 einen Algorithmus, der für triangulierte Polygone das SSSP Problem in O(n) Schritten löst [Guibas 87]. Melissaratos und Souvanne benutzen 1992 diese Resultate zur Lösung geometrischer Probleme in planaren Regionen [Melissaratos 92].

• Ahuja, Mehlhorn, Orlin und Tarjan modifizieren 1990 Dijkstras Algorithmus für positive Kantengewichte, die kleiner als C sind, indem sie Radix heaps und Fibonacci heaps einsetzen. Sie erreichen für SSSP eine worst case Laufzeit von O(m+n\sqrt{log C}) [Ahuja 90].

• 1991 wird von Karger, Koller und Phillips ein sogenannter ’hidden path algorithm’ zur Lösung von APSP in der Laufzeit O(m^{∗}n + n^{2} log n) entwickelt. Hierbei bezeichnet m^{∗} die Anzahl der verschiedenen Kante in allen Pfaden minimaler Länge [Karger 91]. Unabhängig davon zeigen McGeoch und Jakobsson das selbe Resultat [Jakobsson 91] [McGeoch 91].

• Alon, Galil und Margalit zeigen 1991, daß APSP ∈ O(n^{v} log^{3} n) gilt, wenn die Kantengewichte in {−1, 0, 1} liegen (v < 2.688). Sie benutzen dabei Resultate der schnellen Matrixmultiplikation. Wenn die Kantengewichte Integer Werte mit einem maximalen Gewicht von M sind, dann gilt die Schranke von O((Mn)^{v} log^{3} n) [Alon 91].

• Allison Dix und Yee stellen 1991 einen Algorithmus der Ordnung O(nb^{2} + n^{2}b) zur Lösung von APSP für zusammenhängende Matrizen vor (b ist die maximale Bandbreite der Matrizen). Sie orientieren sich an Floyd’s Tripelalgorithmus und modifizieren diesen zu einem inkrementierenden Algorithmus [Allison 91].

• Frederickson entwickelt 1991 einen Algorithmus für APSP in planaren Graphen mit positiven Kantengewichten von der Laufzeit O(np). p ist dabei die minimale Anzahl der Gebiete, so daß alle Knoten in der planaren Einbettung überdeckt werden (1 ≤ p ≤ n). Er setzt Mittel der dynamischen Programmierung ein, sogenannte ’compact routing tables’ [Frederickson 91].

• Hong C.F. entwickelt 1992 einen Algorithmus, der mit Hilfe von Minimalspannenden Bäumen in planaren Graphen einen minimalen Pfad zwischen zwei Knoten in linearer Zeit (O(n)) löst [Hong 92].

• Zufallsgraphen

– Spira arbeitet 1973 mit Kantengewichten, die unabhängig identisch verteilte Zufallsvariablen sind, und erhält eine erwartete Laufzeit für APSP von O(n^{2} log^{2} n) [Spira 73].

– Bloniarz verbessert 1980 das Ergebnis von Spira auf eine erwartete Laufzeit von O(n^{2} log n log^{∗} n) [Bloniarz 80].

– Frieze und Grimmet verbessern 1985 wiederum dieses Ergebnis für Zufallsgraphen auf eine Laufzeit von O(n^{2} log n) [Frieze 85].

– Für gerichtete Graphen mit positiven Kantengewichten stellen Moffat und Takaoka 1987 einen Algorithmus für APSP vor, der eine erwartete Laufzeit von O(n^{2} log n) hat [Moffat 87].

• On-Line Anfragen und Einfügen auf gerichteten Graphen.

– Italiano entwickelte 1986 eine Datenstruktur, die höchstens O(n) Operationen benötigt, um eine neue Kante einzufügen oder zu testen, ob ein Pfad zwischen zwei Knoten existiert. Dazu ist ein Speicheraufwand von O(n^{2}) notwendig [Italiano 86].

– Ausiello, Italiano, Spaccamela und Nanni stellen 1991 eine Datenstruktur und einen Algorithmus zur Bestimmung des Gewichts eines minimalen Pfades und der Länge dieses Pfades vor. Die Kantengewichte liegen dabei in {1, 2 …, C}. Die Betimmung der Länge des minimalen Pfades benötigt nur konstante Zeit, während die Bestimmung der Kosten O(k) Operationen benötigt, wenn k die Länge des minimalen Pfades ist. Für eine Folge von O(Cn^{2}) Einfügeoperationen von Kanten oder Verminderungen der Kantengewichte werden O(Cn^{3} log(Cn)) Berechnungsschritte und ein Speicheraufwand von O(n^{2}) benötigt [Ausiello 91] [Ausiello 92].

• Parallelität auf Graphen

– Pantziiou, Spirakis und Zaroliagis stellen 1990 einen parallelen Algorithmus vor, der mit O(np) Prozessoren das Problem APSP für gerichtete planare Graphen mit positiven Kantengewichten in der Zeit O(log^{2} n + log^{3} p) löst. Sie bauen im wesentlichen auf der ’Hammock-Dekomposition’ von Frederickson [Frederickson 87] auf. p ist dabei wieder die Anzahl der Gebiete in der planaren Einbettung des Graphen, so daß alle Knoten überdeckt werden. Als paralleles Rechnermodell wird die CREW PRAM benutzt (CREW PRAM - Alle Prozessoren haben Zugriff auf einen globalen Speicher, in dem sie simultan lesen, aber nicht simultan schreiben können [Wyllie 79].) [Pantziou 90].

– 1991 entwickeln Djidjev, Pantziou und Zaroliagis eine Datenstruktur und einen Algorithmus, der die On-Line Berechnung des kürzesten Pfades bzw. der Länge des kürzesten Pfades für planare gerichtete Graphen mit positiven Kantengewichten in O(k + log n) bzw. O(log n) Berechnungsschritten durchführt. Dazu ist ein Voraufwand von O(n log n + p^{2}) mit einem Speicheraufwand von O(n log n+p^{2}) notwendig, wobei p wieder die Anzahl der Gebiete in der planaren Einbettung des Graphen ist, so daß alle Knoten überdeckt werden. Außerdem wird gezeigt, daß dieses Verfahren auf einem parallelen Maschinenmodell lauffähig ist (CREW PRAM). Mit einem Speicher von O(n log n + p^{2}) und O(n + M(p)) Prozessoren ist dann der Voraufwand in O(log^{2} n) Berechnungsschritten erledigt. M(p) ist dabei die Anzahl von Prozessoren, die notwendig ist, um zwei p×p Matrizen in O(log p) Zeiteinheiten zu multiplizieren [Djidjev 91].

• Lengauer und Theune untersuchen 1991 allgemeinere Kostenfunktionen für Pfade in Graphen. Die Kostenfunktionen werden definiert und die Algorithmen von Ford [Ford 62] und Dijkstra [Dijkstra 59] adaptiert [Lengauer 91].

Literatur

[Ahuja 90] Ahuja K.K., Mehlhorn K., Orlin J.B. und Tarjan R.E., ’Faster algorithms for the shortest path problem’, Journal of the ACM 37, (1990), 213 - 223

[Albert 91] Albert J.L., ’Automata, languages and programming’, Proc. of the 18th international colloquium (Madrid, Spain, 8-12. July 1991), [Lecture notes in comp. sci. no. 510], Springer Verlag, New York, 1991, ISBN 0-387-54233-7

[Allison 91] Allison L., Dix T.I. und Yee C.N., ’Shortest path and closure algorithms for bounded matrices’, Inf. Process. Lett. 40, 6, (Dec. 30. 1991), 317 - 322

[Alon 91] Alon N., Gabil Z. und Margalit O., ’On the exponent of the all pairs shortest path problem’, 569 - 575, in [?]

[Ausiello 91] Ausiello G., Italiano G.F., Spaccamela A.M. und Nanni U., ’Incremental Algorithms for minimal length paths’, Journal of algorithms, 12, 4, Dec. 1991, 615 - 638

[Ausiello 92] Ausiello G., Italiano G.F., Spaccamela A.M. und Nanni U., ’On-line computation of minimal and maximal length paths’, Theor. comp. sci. 95, 2, (March 30. 1992), 245 - 261

[ATKIS 91] ATKIS-Objektartenkatalog (Amtliches Topographisch-Kartographisches Informationssystem), Innenministerium Baden Württemberg, 1991

[Bentley 74] J.L. Bentley and R.A. Finkel, ’Quad trees, A data structure for retrieval on composite keys’, AA, Acta Informatica 4 (1974), 1-9

[Bloniarz 80] Bloniarz P.A., ’A shortest path algorithm with expected time O(n^{2} log n log^{∗} n)’, Technical Report 80-3, Department of Computer Science, State University of New York at Albany, 1980

[Buchholz 94] Buchholz F., ’Komplexität des Fahrgemeinschaften-Problems’, Studienarbeit Nr. 1327, Institut für Informatik Universität Stuttgart, 1994

[Dijkstra 59] Dijkstra E.W., ’A note on two problems in connection with graphs’, Numerical Mathematics, 1, 1959

[Djidjev 91] Djidjev H.N., Pantziou G.E. und Zaroliagis C.D., ’Computing shortest paths and distances in planar graphs’, 327 - 338, in [Albert 91]

[DRIVE(1) 90] N. Reinkober und P. Vansevenant, Literature Evaluation, Deliverable 1, DRIVE Forschungsprojekt 5 1069, Carpooling System Management, Wuppertal, Leuven (1990)

[DRIVE(2) 90] R. Hoppe, N. Reinkober und P. Vansevenant, Road-User-Demand-Study, Deliverable 2, DRIVE-Projekt 5 1069, Carpoolin System Management, Wuppertal, Leuven (1990)

[DVW 92] Deutscher Verein für Vermessungswesen (DVW), Landesverein Baden-Würt-temberg e.v., November 1992, 39. Jahrgang, Heft 2, ISSN 0940-2942

[Edelsbrunner 87] Herbert Edelsbrunner, ’Algorithms in combinatorial geometry’, EAT-CS monographs on theoretical computer science, Springer, 1987, ISBN 3-540-13722-X

[FGSV 89] Forschungsgesellschaft für Straßen und Verkehrswesen (FGSV)), ’Erhaltung und Förderung der Mobilität unter Berücksichtigung der Bevölkerungsentwicklung sowie des technologischen und gesellschaftlichen Wandels’, FGSV Arbeitspapier Nr. 20 der Kommission ’Stadt und Verkehr’, Köln 1989

[FGSV 90] Forschungsgesellschaft für Straßen und Verkehrswesen (FGSV), ’öffentlicher Personen-Nahverkehr Empfehlungen zur Verbesserung der Akzeptanz des ÖPNV’, Arbeitsausschuß’Öffentlicher Verkehr’, FGSV 123, Köln 1990

[Floyd 62] Floyd R.W., ’Algorithm 97: Shortest path’, Communications of the ACM, 5, 1962

[Ford 62] Ford L.R. und Fulkerson D.R, ’Flows in networks’, Princeton University Press, N.J., 1962

[Fredman 76] Fredman M.L., ’New bounds on the comlexity of the shortest path problem’, SIAM Journal of Computing, 5, 1976

[Fredman 87] Fredman M.L. und Tarjan R.E., ’Fibonacci Heaps and their uses in improved network optimization algorithms’, Journal of ACM 34, (1987), 596 - 615

[Frederickson 87] Frederickson G.N., ’Fast algorithms for shortest paths in planar graphs, with applications’, SIAM Journal of computing, Vol. 16, No. 6, (1987), 1004 - 1022

[Frederickson 90] Frederickson G.N., ’A distributed shortest path algorithm for a planar network’, Information and Computation, Vol. 86, (1990), S. 140

[Frederickson 91] Frederickson G.N., ’Planar graph decomposition and all pairs shortest paths’, Journal of ACM 38, 1, Jan. 1991, 162 - 204

[Frederickson 92] Frederickson G.N., Hambrusch S.E. und Tu H., ’Shortest path computations in source-deplanarized graphs’, Information Processing Letters 47 (1993), 71 - 75

[Floyd 62] Floyd R.W., ’Algorithm 97: Shortest Path’, Communications of the ACM, 5, 1962

[Frieze 85] Frieze A.M. and Grimmet G.R., ’The shortest path problem for graphs with random arc lengths’ , Discrete applied Mathematics, 10, 1985

[Guibas 87] Guibas L., Hershberger J., Leven D., Sharir M. und Tarjan R.E., ’Lineartime algorithms for visibility and shortest path problems inside triangulated simple polygons’, Algorithmica (1987) 2, 209 -233

[Harary 74] Harary F., ’Graphentheorie’, München-Wien, Oldenbourg, 1974

[Hong 92] Hong C.F., ’O(n) planar network shortest path algorithm’, Georgia Institute of technology, Atlanta, Atlanta GA, UMI Order No. DA 9223778, 1992

[Italiano 86] Italiano G.F., ’Amortized efficieny of a path retrieval data structure’, Theoretical Computer Science 48 (1986), 273 - 281

[Jakobsson 91] Jakobsson H., ’Mixed-approach algorithms for transitive closure’, Proceedings of the 10th ACM Symposium on Principles of Database Systems, 1991

[Johnson 77] Johnson D.B., ’Efficient algorithms for shortest paths in sparse networks’, Journal of ACM, Vol. 24, No. 1, (1977), 1 - 13

[Kapoor 88] Kapoor S. und Maheshwari S.N., ’Efficient algorithms for euclidean shortest path and visibility problems with polygonal obstacles’, Proceedings of the 4th annual ACM, symposium on computational geometry, New York, (1988), Urabana Champaign June 6-8, 172 - 182 [Karger 91] Karger D.R., Koller D. und Phillips S.J., ’Finding the hidden path, time

bounds for all pairs shortest paths’, 560 - 568, in [?]

[Lengauer 91] Lengauer T. und Theune D., ’Efficient algorithm for path problems with general cost criteria’, 314 - 326, in [Albert 91]

[Karten 93] Kartenverzeichnis 1993, Landesvermessungsamt Baden-Württemberg, Postfach 10 29 62, 7000 Stuttgart 10

[Larson 83] Per-Ake Larson, ’Dynamische Hashverfahren’, Informatik Spektrum (1983), 6, 7-19

[Lee 77] D.T.Lee and C.K.Wong, ’Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Trees’, Acta Informatica 9, 23-29 (1977)

[McGeoch 91] McGeoch C.C., ’A new all-pairs shortest path algorithm’, Technical Report 91-30, DIMACS, 1991

[Mehlhorn(2) 84] Kurt Mehlhorn, ’Data structures and algorithms - 2. Graph algorithms and NP-completeness’, Springer, 1984, ISBN 3-540-13641-X

[Mehlhorn(3) 84] Kurt Mehlhorn, ’Data structures and algorithms - 3. Multi-dimensional searching and computational geometry’, Springer, 1984, ISBN 3-540-13642-8

[Mendelson 82] Haim Mendelson, ’Analysis of extendible hashing’, IEEE Transactions on software engineering, Vol. SE-8, No. 6, Nov. 1982

[Melissaratos 92] Melissaratos E.A. und Souvanne D.L., ’Shortest path help solve geometric optimization problems in planar regions’, SIAM Journal on computing 21, 4, (Aug. 1992), 601 - 638

[Moffat 87] Moffat A.M. und Takaoka T., ’An all pairs shortest path algorithm with expected time O(n^{2} log n)’, SIAM Journal on computing 6, (1987), 1023 - 1031

[Neumann] Neumann Klaus, ’Operations Research Verfahren’, Band 3, Graphentheorie und Netzplantechnik, Carl Hanser Verlag München Wien, 1975, ISBN 3-446-11992-2

[Nievergelt 84] J. Nievergelt, H. Hinterberger und K.C. Sevcik, ’The Grid File: an adaptable, symmetric multikey file structure’, ACM Transactions on Database Systems, Vol. 9, No. 1, March 1984, 38-71

[Claus 93] V. Claus, J. Risau und M. Papenbrock, ’Projekt Fahrgemeinschaften’ , Oldenburger Forschungs- und Entwicklungsinstitut für Informatik-Werkzeuge und - Systeme, 1993

[Ottmann 93] T. Ottmann und P. Widmayer, ’Algorithmen und Datenstrukturen’, Reihe Informatik Band 70, ISBN 3-411-16602-9

[Pantziou 90] Pantziou G.E., Spirakis P.G. und Zaroliagis C.D, ’Efficient parallel algorithms for shortest paths in planar graphs’, in [SWAT 90]

[Preparata 85] Franco P. Preparata and Michael Ian Shamos, ’Computational geometry: an introduction’, Springer, 1985, ISBN 0-387-96131-3

[Regnier 84] Mireille Regnier, ’Analysis of Grid File algorithms’, BIT 25 (1985), 335-357

[Reinkober 94] Reinkober N., ’Fahrgemeinschaften und Mobilitätszentrale’, Bestandteile eines zukunftsorientierten Öffentlichen Personennahverkehrs, Schriftenreihe für Verkehr und Technik Band 81, Erich Schmidt Verlag, 1994 [Richbourg 87] Richbourg R.F, Row N.C., Zyda M.J. und McGhee R.B., ’Solving global

two-dimensional routing problems using Snell’s law and A^{∗} search’, Proceedings International conference on robotics and automation, (Raleigh N.C., February), New York IEEE (1987), 1631 - 1636

[Spira 73] Spira P.M., ’A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n^{2} log^{2} n)’ , SIAM Journal of Computing, 2, 1973

[Stöppler 91] H.W. Stöppler, ’Die einheitliche Datenbankschittstelle (EDBS) im fachlichen Überblick’, aus [DVW 92]

[SWAT 90] Proceedings of the second scandinavian workshop, ’Alorithm theory’ (SWAT), (Bergen, Sweden, July 11-14, 1990), [Lecture Notes in comp. sci. no. 447], Gilbert J.R., Karlson R., Springer Verlag New York 1990, ISBN 0-387-52846-6

[Tamminen 82] Markku Tamminen, ’The extendible cell method for closest point problems’, BIT 22 (1982), 27-41

[Taxistop 94] Klüssendorf J., ’SMARTPOOL - The clever way to carpool’, Centrum voor Positieve Aanwending, Onderbergen 51, B-9000 Gent, 1994

[TSM 86] Transportation System Management, ’A practitioner’s experience’, Transportation Research Record no. 1081, Washington D.C. 1986

[Wyllie 79] Wyllie J.C., ’The complexity of parallel computation’, PhD Thesis, TR 79-387, Dept of computer Science, Cornell University, Ithaca, NY, 1979