Vorlesung Algorithmische Kartografie Randbeschriftung
Transcrição
Vorlesung Algorithmische Kartografie Randbeschriftung
Vorlesung Algorithmische Kartografie Randbeschriftung LEHRSTUHL FÜR ALGORITHMIK I · INSTITUT FÜR THEORETISCHE INFORMATIK · FAKULTÄT FÜR INFORMATIK Benjamin Niedermann/Martin Nöllenburg 16.06.2015 1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen Ibis Hotel Main Station Kulturspeicher Hauptbahnhof Hauptbahnhof West Hotel Poppular Juliuspromenade Escalera Ulmer Hof Hotel Urlaub Barbarossaplatz Nachteile von internen Beschriftungen funktioniert nur für dünne“ Punktmengen gut ” Label verdecken unterliegende Topographie manche Label müssen ausgeblendet werden visuelles cluttering 2-1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen Ibis Hotel Kulturspeicher Escalera Ulmer Hof Hotel Urlaub Main Station Hauptbahnhof Hauptbahnhof West Hotel Poppular Juliuspromenade Barbarossaplatz Vorteile von Randbeschriftungen dichte Punktmengen lassen sich beschriften weniger Überdeckungen der Karte schnelleres Finden Name → Ort besser geeignet für Label mit viel Text 2-2 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen 3-1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen Schleswig-Holstein Mecklenburg-Vorpommern Hamburg Bremen Niedersachsen Berlin Brandenburg Sachsen-Anhalt Nordrhein-Westfalen Sachsen Thüringen Hessen Rheinland-Pfalz Saarland Bayern Baden-Württemberg 3-2 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen Schleswig-Holstein Mecklenburg-Vorpommern Hamburg Bremen Niedersachsen Berlin Brandenburg Sachsen-Anhalt Sachsen Nordrhein-Westfalen Thüringen Hessen Saarland Rheinland-Pfalz Baden-Württemberg Bayern 3-3 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Randbeschriftungen Schleswig-Holstein Mecklenburg-Vorpommern Lederhaut Hamburg Bremen Niedersachsen Berlin Brandenburg Sachsen-Anhalt Sachsen Nordrhein-Westfalen Thüringen Hessen Saarland Sehnerv Rheinland-Pfalz Baden-WürttembergNetzhaut Bayern 3-4 Vorlesung Algorithmische Kartografie Aderhaut Schlemm-Kanal Irisfortsätze Hornhaut Zonulafasern Iris Pupille vordereAugenkammer Augenkammerhintere Ziliarkörper Linse Glaskörper http://commons.wikimedia.org/wiki/File:Eye scheme.svg Punktbeschriftung in Landkarten Arten von Randbeschriftungen 4-1 Einseitiger Fall Zweiseitiger Fall Dreiseitiger Fall Vierseitiger Fall Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Arten von Randbeschriftungen 4-2 Einseitiger Fall Zweiseitiger Fall Dreiseitiger Fall Vierseitiger Fall Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. R Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-1 Vorlesung Algorithmische Kartografie p1 p3 Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Annahme: Jedes Label ist groß genug, sodass die Beschreibung eines jeden Punkts hinein passt. Es sind genauso viele Label wie Punkte vorhanden. R Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-2 Vorlesung Algorithmische Kartografie p1 p3 Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Definition: Eine Menge L = {λ1 , . . . , λn } an Kurven in R heißt Zuordnung von L und P , wenn jede Kurve einen Punkt pi ∈ P mit einem Label `j ∈ L verbindet und jeder Punkt und jedes Label genau von einer Kurve angebunden wird. R Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-3 Vorlesung Algorithmische Kartografie p1 p3 Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven in L schneiden sich nicht gegenseitig. R Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-4 Vorlesung Algorithmische Kartografie p1 p3 Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven in L schneiden sich nicht gegenseitig. Label `1 Label `2 p2 p5 p4 R Begriffe: Kurve λi heißt Leader. Verbindungspunkt von Leader und Label heißt Port. Label `3 Label `4 Label `5 5-5 Vorlesung Algorithmische Kartografie p1 p3 Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven in L schneiden sich nicht gegenseitig. Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-6 Vorlesung Algorithmische Kartografie p1 p3 R Begriffe: Kurve λi heißt Leader. Verbindungspunkt von Leader und Label heißt Port. Zwei Varianten: 1. Ports fest vorgegeben. 2. Port auf rechter Seite von Label frei wählbar. Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label. Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven in L schneiden sich nicht gegenseitig. Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-7 Vorlesung Algorithmische Kartografie p1 p3 R Begriffe: Kurve λi heißt Leader. Verbindungspunkt von Leader und Label heißt Port. Zwei Varianten: 1. Ports fest vorgegeben. 2. Port auf rechter Seite von Label frei wählbar. Punktbeschriftung in Landkarten Problemstellung Gegeben: Punkte P = {p1 , . . . , pn } in einem Rechteck R. Annahme: Allgemeine Lage der Punkte in P und der Label in L. Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit Keine zweiauf Punkte P liegen aufRechtecke einer gemeinsamen rechter Seite linker in Seite von R. aus L heißen Label. vertikalen oder horizontalen Geraden. Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven Kein Punkt in P liegt auf einer horizontalen Geraden, welche in L schneiden sich nicht gegenseitig. die obere oder untere Seite eines Labels in L verlängert. Label `1 Label `2 p2 p5 p4 Label `3 Label `4 Label `5 5-8 Vorlesung Algorithmische Kartografie p1 p3 R Begriffe: Kurve λi heißt Leader. Verbindungspunkt von Leader und Label heißt Port. Zwei Varianten: 1. Ports fest vorgegeben. 2. Port auf rechter Seite von Label frei wählbar. Punktbeschriftung in Landkarten Typen von Leadern Üblich: Leader werden aus Sequenz von Strecken zusammengesetzt. parallel Typische Beispiele: orthogonal orthogonal orthogonal po-Leader 6-1 Vorlesung Algorithmische Kartografie α orthogonal go na l opo-Leader di a parallel s-Leader do-Leader Punktbeschriftung in Landkarten Typen von Leadern Üblich: Leader werden aus Sequenz von Strecken zusammengesetzt. parallel Typische Beispiele: orthogonal orthogonal orthogonal po-Leader 6-2 Vorlesung Algorithmische Kartografie α orthogonal go na l opo-Leader di a parallel s-Leader do-Leader Punktbeschriftung in Landkarten Zielfunktion Bewertungsfunktion: bad : L × P → R Bewertet Zuordnung von Labeln L und Punkten P . Optimierungsproblem: Finde für gegebene Instanz (R, P, L) eine kreuzungsfreie Zuordnung L, sodass X bad(`(λ), p(λ)) λ∈L unter allen kreuzeungsfreien Zuordnungen minimiert wird. Notation: `(λ): Label aus L, das von Leader λ angebunden wird. p(λ): Punkt aus p, der von Leader λ angebunden wird. 7-1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Zielfunktion Bewertungsfunktion: bad : L × P → R Bewertet Zuordnung von Labeln L und Punkten P . Optimierungsproblem: Finde für gegebene Instanz (R, P, L) eine kreuzungsfreie Zuordnung L, sodass X bad(`(λ), p(λ)) λ∈L unter allen kreuzeungsfreien Zuordnungen minimiert wird. Notation: `(λ): Label aus L, das von Leader λ angebunden wird. p(λ): Punkt aus p, der von Leader λ angebunden wird. Beispiele für Bewertungsfunktionen? 7-2 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Beispiele für Bewertungsfunktionen Längenminimierung: Knickminimierung: Interferenzminimierung mit Karte 8-1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Beispiele für Bewertungsfunktionen Längenminimierung: Knickminimierung: Interferenzminimierung mit Karte 8-2 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Beispiele für Bewertungsfunktionen Längenminimierung: Begriffe: Länge einer Zuordnung L: Die Summe der Leader-Längen. λ(p, `) bezeichnet po-Leader der von p nach ` führt. Arm p 8-3 Hand ` Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Beispiele für Bewertungsfunktionen Längenminimierung: Begriffe: Länge einer Zuordnung L: Die Summe der Leader-Längen. λ(p, `) bezeichnet po-Leader der von p nach ` führt. p Hand ` Arm p ` aufsteigender Leader ` 8-4 Vorlesung Algorithmische Kartografie ` p direkter Leader absteigender Leader p Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) 9-1 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. 9-2 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. Annahme es gäbe solche Leader: p0 ` `0 p 9-3 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. Annahme es gäbe solche Leader: p0 p0 ` Neuverdrahtung ` `0 `0 p p Kürzere Gesamtlänge der Leader nach Neuverdrahtung Minimalität von L∗ 9-4 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch einen aufsteigenden Leader schneiden. 9-5 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch einen aufsteigenden Leader schneiden. Annahme es gäbe einen solchen Leader: `0 p00 ` `00 9-6 p0 Vorlesung Algorithmische Kartografie p Einziger Fall, denn wegen A) können sich λ(p0 , `0 ) und λ(p00 , `00 ) nicht schneiden. Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch einen aufsteigenden Leader schneiden. Annahme es gäbe einen solchen Leader: `0 `0 p00 ` p0 p Neuverdrahtung p00 ` `00 `00 Kürzere Gesamtlänge der Leader nach Neuverdrahtung p0 p Minimalität von L∗ 9-7 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch einen aufsteigenden Leader schneiden. Absteigende Kreuzung : Beteiligung eines absteigenden Leader. Aufsteigende Kreuzung : Beteiligung eines aufsteigenden Leader. Menge absteigender Kreuzungen und Menge aufsteigender Kreuzungen sind somit disjunkt. 9-8 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Beweis: A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht. B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch einen aufsteigenden Leader schneiden. Idee: Entferne alle aufsteigenden Kreuzungen L∗ , sodass die Gesamtlänge der Leader unverändert bleibt und keine absteigenden Kreuzungen entstehen. Selbes Vorgehen für absteigende Kreuzungen durch Spiegeln der Instanz. Kreuzungsfreie Zuordnung L mit gleicher Länge wie L∗ . 9-9 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Fortsetzung Beweis: Algorithmus zur Entferung aller aufsteigenden Kreuzungen: Sortiere Label von unten nach oben: `1 , . . . , `n für i = 1 . . . n tue Sei λ(p, `i ) Leader in L∗ . wenn λ(p, `i ) aufsteigender Leader ist dann Bestimme leader λ(q, `j ) mit linkester Kreuzung mit λ(p, `i ). Neuverdrahtung: λ(q, `i ) und λ(p, `j ). `j `i `j `i q q p 10 Vorlesung Algorithmische Kartografie p Punktbeschriftung in Landkarten Neuverdrahtung Fortsetzung Beweis: Algorithmus zur Entferung aller aufsteigenden Kreuzungen: Sortiere Label von unten nach oben: `1 , . . . , `n für i = 1 . . . n tue Sei λ(p, `i ) Leader in L∗ . wenn λ(p, `i ) aufsteigender Leader ist dann Bestimme leader λ(q, `j ) mit linkester Kreuzung mit λ(p, `i ). Neuverdrahtung: λ(q, `i ) und λ(p, `j ). Zeige für Schritt i: 1. Gesamtlänge der Leader bleibt erhalten. 2. Aufsteigende Kreuzungen entstehen nur oberhalb von Arm von λ(p, `i ). 3. Es entstehen keine absteigenden Kreuzungen. 4. Laufzeit beträgt O(n) Zeit. Beweis durch Induktion über i: siehe Tafel. 10 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Neuverdrahtung Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert werden. (Bekos et al. ’07 und Benkert et al. ’09) Satz kann auch auf do-Leader angepasst werden. 11 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Jetzt: Verfahren für Minimierung der Leader-Längen in O(n log n) Zeit. Vorgehen in zwei Phasen: 1. Teile Instanz in unabhängige Teilinstanzen auf. 2. Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. 12 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Jetzt: Verfahren für Minimierung der Leader-Längen in O(n log n) Zeit. Vorgehen in zwei Phasen: 1. Teile Instanz in unabhängige Teilinstanzen auf. 2. Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Unterteile hierzu Instanz in Streifen induziert durch Punkte in P und horizontale Seiten der Label. 12 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 1. Phase: Teile Instanz in unabhängige Teilinstanzen auf. Traversiere Streifen von unten nach oben und bestimme folgende Anzahlen für jeden Streifen σ: paσ =#Punkte oberhalb von σ inkl. Punkte auf oberer Kante von σ. `aσ =#Label oberhalb von σ inkl. Label die σ schneiden. pbσ =#Punkte unterhalb von σ inkl. Punkte auf unterer Kante von σ. `bσ =#Label unterhalb von σ inkl. Label die σ schneiden. Ein Streifen σ heißt: absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ neutral, in allen anderen Fällen. 13 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. } } absteigende Instanz: inklusive der Grenzen } } } neutrale Instanz: exklusive der Grenzen } aufsteigende Instanz: inklusive der Grenzen } 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren 2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens. Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke. Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben. Sweep-Line stoppt bei unterer Kante der Label und bei Punkten: Punkt-Event p: Füge p zu einer nach x-Koordinanten sortierten Warteliste W hinzu. Label-Event `: Entferne Punkt p aus W , der am weitesten links liegt. Verbinde p mit ` mittels kürzesten Leader. Analoges Vorgehen für absteigende Instanz. 14 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten 15 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Beweis: Sei paσ = `aσ . (Analog pbσ = `bσ ) Angenommen es gibt Leader λ, der neutralen Steifen σ kreuzt. 1. Fall: λ ist mit Label ` verbunden, das σ kreuzt. 2. Fall: λ verbindet Punkt p oberhalb von σ mit Label ` unterhalb von σ 3. Fall: λ verbindet Punkt p unterhalb von σ mit Label ` oberhalb von σ 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Beweis: Sei paσ = `aσ . (Analog pbσ = `bσ ) Angenommen es gibt Leader λ, der neutralen Steifen σ kreuzt. 1. Fall: λ ist mit Label ` verbunden, das σ kreuzt. ` kürze Leader um mind. Höhe von σ ` 2. Fall: λ verbindet Punkt p oberhalb von σ mit Label ` unterhalb von σ 3. Fall: λ verbindet Punkt p unterhalb von σ mit Label ` oberhalb von σ 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Beweis: Sei paσ = `aσ . (Analog pbσ = `bσ ) Angenommen es gibt Leader λ, der neutralen Steifen σ kreuzt. 1. Fall: λ ist mit Label ` verbunden, das σ kreuzt. ` kürze Leader um mind. Höhe von σ ` 2. Fall: λ verbindet Punkt p oberhalb von σ mit Label ` unterhalb von σ p p Wegen paσ = `aσ : 0 ∃ Punkt p unterhalb von σ, der mit 0 0 ` ` 0 Label ` verbunden, sodass 0 0 p p 0 ` schneidet σ, oder ` ` `0 liegt oberhalb von σ. Kürzere Leader Vertausche Leader 3. Fall: λ verbindet Punkt p unterhalb von σ mit Label ` oberhalb von σ 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ 16 Vorlesung Algorithmische Kartografie paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ Warum? 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ paσ↓ − `aσ↓ ≥ 1 paσ↑ − `aσ↑ < 0 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ paσ↓ − `aσ↓ ≥ 1 paσ↑ − `aσ↑ < 0 16 Vorlesung Algorithmische Kartografie paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ |(paσ↓ − `aσ↓ ) − (paσ↑ − `aσ↑ )| ≥ 2 Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ paσ↓ − `aσ↓ ≥ 1 paσ↑ − `aσ↑ < 0 paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ |(paσ↓ − `aσ↓ ) − (paσ↑ − `aσ↑ )| ≥ 2 Da Punkte und Label in allgemeiner Lage gilt aber für zwei benachbarte Streifen σ und σ 0 : |(paσ − `aσ ) − (paσ0 − `aσ0 )| ≤ 1 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. absteigend, falls paσ > `aσ aufsteigend, falls pbσ > `bσ paσ↓ − `aσ↓ ≥ 1 paσ↑ − `aσ↑ < 0 paσ − `aσ ≥ 1 und pbσ < `bσ pbσ − `bσ ≥ 1 und paσ < `aσ |(paσ↓ − `aσ↓ ) − (paσ↑ − `aσ↑ )| ≥ 2 Da Punkte und Label in allgemeiner Lage gilt aber für zwei benachbarte Streifen σ und σ 0 : |(paσ − `aσ ) − (paσ0 − `aσ0 )| ≤ 1 σ ↓ und σ ↑ sind nicht benachbart. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. Wegen Lemma 1: In jeder optimalen Lösung werden die Punkte einer aufsteigenden/absteigenden Instanz S von Leadern angebunden, die vollständig in S liegen. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. Wegen Lemma 1: In jeder optimalen Lösung werden die Punkte einer aufsteigenden/absteigenden Instanz S von Leadern angebunden, die vollständig in S liegen. 2. Sei σ unterster Streifen einer aufsteigenden Instanz S. In jeder optimalen Lösung werden ausschließlich Label oberhalb von σ zur Beschriftung der Punkte in S verwendet (siehe Tafel). Analog: Absteigende Instanz. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Beweis: 1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑ befindet sich immer ein neutraler Streifen. Wegen Lemma 1: In jeder optimalen Lösung werden die Punkte einer aufsteigenden/absteigenden Instanz S von Leadern angebunden, die vollständig in S liegen. 2. Sei σ unterster Streifen einer aufsteigenden Instanz S. In jeder optimalen Lösung werden ausschließlich Label oberhalb von σ zur Beschriftung der Punkte in S verwendet (siehe Tafel). Analog: Absteigende Instanz. 3. Der Algorithmus berechnet eine solche Zuordnung und diese ist optimal und kreuzungsfrei (siehe Tafel). 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten Sweep-Line-Verfahren Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt, dass kein Leader einen neutralen Streifen kreuzt (Übung). Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie Zuordnung minimaler Länge mithilfe von po-Leadern in O(n log n) Zeit und O(n) Speicher berechnet werden. Satz 2: Die Berechnung einer kreuzungsfreien Zuordnung minimaler Länge einer Instanz (P, L, R) mit po-Leadern benötigt Laufzeit O(n log n) Zeit und O(n) Speicher. 16 Vorlesung Algorithmische Kartografie Punktbeschriftung in Landkarten