Hallo Welt für Fortgeschrittene

Hallo Welt für Fortgeschrittene
Geometrie II
Benjamin Zenke
Informatik 2  Programmiersysteme  Martensstraße 3  91058 Erlangen
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 2
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 3
Closest Pair
 In gegebener Menge von Punkten die beiden finden
mit dem geringsten Abstand zueinander
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 4
Closest Pair – Lösungsansätze
 Naiver Ansatz:
□ BruteForce
□ Für jeden Punkt Abstand zu den anderen berechnen
□ O(n²)
 Alternative:
□ Divide & Conquer
□ O(n log n)
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 5
Closest Pair – Divide & Conquer
 Vorgehensweise:
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 6
Closest Pair – Divide & Conquer
 Vorgehensweise:
□ Punktemenge aufteilen
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 7
Closest Pair – Divide & Conquer
 Vorgehensweise:
□ Punktemenge aufteilen
□ Closest Pair für beide Seiten
bestimmen (Rekursiv)
 Problem: Gesuchte Punkte liegen
nicht auf der gleichen Seite
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 8
Closest Pair – Divide & Conquer
 Vorgehensweise:
□ Punktemenge aufteilen
□ Closest Pair für beide Seiten
bestimmen (Rekursiv)
 Problem: Gesuchte Punkte liegen
nicht auf der gleichen Seite
 Lösung: Vergleich der Punkte deren
maximaler Abstand zur Trennlinie
kleiner als dRight ist (max. 3
Vergleiche pro Punkt)
 Laufzeit: O(n log n)
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 9
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 10
Bereichssuche
 Gegeben:
□ Menge von Punkten P
□ Bereich/Intervall B
 Gesucht:
□ Alle Punkte aus P die in B liegen
 Beispiele:
□ Datenbankabfragen
□ Geographische Informationssysteme
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 11
Bereichssuche - Lösungansätze
 Naiver Lösungsansatz:
□ Jeden Punkt einzeln testen
□ O(n)
 Alternative:
□ Gitterverfahren
□ Verwendung von k-D-Trees
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 12
Bereichssuche - Gitterverfahren
 Idee
□ Ebene wird mithilfe eines Gitters aufgeteilt
□ Punkte werden in die jeweiligen Flächen einsortiert
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 13
Bereichssuche - Gitterverfahren
 Query: Es müssen nur die relevanten Flächen überprüft
werden
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 14
Bereichssuche - Gitterverfahren
 Vorteile
□ Leicht zu
implementieren
□ Verbesserung der
Laufzeit
 Nachteile
□ Gittergröße muss
vorher bekannt sein
 zu klein: viele leere
Felder
 zu groß: viele Punkte
pro Feld
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 15
k-D-Tree
 Definition
□ k-D-Tree ist ein k-dimensionaler binärer Suchbaum mit
der Besonderheit das in jeder Tiefe nach einer anderen
Dimension aufgeteilt wird
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 16
k-D-Tree - Konstruktion
P := Punktemenge
d := Aktuelle Höhe im Baum
BUILDTREE(P, d) {
IF(P enthält nur einen Punkt)
Return Blatt, das diesen Punkt enthält
ELSE IF (d ist eine gerade Zahl)
Splitte P via vertikalen Median in P1 (links) und P2 (rechts) auf
ELSE
Splitte P via horizontalen Median in P1 (oben) und P2 (unten) auf
vLeft = BUILDTREE(P1, d+1)
vRight = BUILDTREE(P2, d+1)
Erzeuge Knoten v mit den Kindern vLeft und vRight
Return v
}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 17
k-D-Tree – Beispiel
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 18
k-D-Tree – Beispiel
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 19
k-D-Tree – Beispiel
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 20
k-D-Tree – Beispiel - Bereichssuche
v := Startknoten
R := Bereich indem gesucht wird
d := Aktuelle Höhe im Baum
List RANGEQUERY(v, R, d) {
IF(v == NULL)
return leere Liste
liste = leere Liste
IF(v ist im Bereich R)
Füge v zu liste hinzu
IF(v ist größer als linker/unterer Rand von R) // abhängig von d
vLeft ist linkes Kind von v
Füge RANGEQUERY(vLeft, R, d+1) zu liste hinzu
IF(v ist kleiner gleich rechter/oberer Rand von R) // abhängig von d
vRight ist rechtes Kind von v
Füge RANGEQUERY(vRight, R, d+1) zu liste hinzu
return liste
}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 21
k-D-Tree – Beispiel - Bereichssuche
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 22
k-D-Tree – Vorteile & Nachteile
 Vorteile
□ Laufzeit:
□ Aufbau: O(n log n)
□ Anfrage: O(log n + x)
 Nachteile
□ Aufwendig zu
implementieren
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 23
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 24
Sweep-Line-Algorithmen
 Ziel: k-dimensionales statisches Problem in
k-1-dimensionales dynamisches Problem umwandeln
 Idee: Eine Sweep-Line die diskret über die sortierten Punkte
wandert und sie verarbeitet
 Beispiel: HEISENBERG aus dem Online-Judge
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 25
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
S{1}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 26
Schnitte: 0
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
S{1,2}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 27
Schnitte: 0
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
S{1,2}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 28
Schnitte: 1
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
S{1}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 29
Schnitte: 3
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
S{}
Schnitte: 4
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 30
Sweep-Line-Algorithmen - Heisenberg
 Sweep-Line trifft
Streckenbeginn:
□ Füge Strecke zu S hinzu
 Sweep-Line trifft auf
Streckenende:
□ Entferne Strecke aus S
 Sweep-Line trifft auf vertikale
Strecke:
□ Berechne Schnittpunkte
mit Strecken aus S
 Laufzeit: O(n log n)
S{}
Schnitte: 4
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 31
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 32
Topcoder – Watchtower
 Gegeben:
□ Menge an Wachtürmen mit dazugehörigen Koordinaten
 Gesucht:
□ Größe der Fläche für die jeder Wachturm verantwortlich
ist
 Fläche der Polygone mit den Punkten die dem jeweiligen
Wachturm am nächsten sind
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 33
Topcoder – Watchtower - Lösungsansatz
 Naiver Lösungsansatz:
□ Berechne für jeden Punkt Geraden
□ Schnittpunkte der Geraden bestimmen
□ O(n⁴)
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 34
Voronoi-Diagramm - Definition
 Das Voronoi-Diagramm für eine Punktmenge P ist die
Einteilung der Ebene in Gebiete gleicher nächster Nachbarn
 Für den Punkt p ϵ P ist die Voronoi Region V(p) die Menge
aller Punkte die näher zu p sind als zu irgend einem andern
Punkt aus der Menge P
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 35
Voronoi-Diagramm – Fortune's Algorithmus
 Beach-Line:
□ Besteht aus zusammenhängenden Parabeln
□ Punkte auf der Beach-Line haben den gleichen Abstand
zur Sweep-Line, wie zu ihrem nähesten Punkt
□ Wird durch binären Suchbaum realisiert
 Sweep-Line:
□ diskret „wandernde“ Linie
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 36
Voronoi-Diagramm – Fortune‘s Algorithmus
 Site-Event:
□ Sweep-Line passiert nächsten Punkt
□ Knoten zu binärem Suchbaum hinzugefügt
 Circle-Event:
□ neuer Punkt für das fertige Diagramm bestimmbar
□ Punkt wird aus Suchbaum entfernt
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 37
Voronoi-Diagramm – Fortune's Algorithmus
P
K
Q
B
:=
:=
:=
:=
Menge der gegebenen Punkte
doppelt verkettete Liste der Kanten
Prioritätswarteschlange mit Events (sortiert nach y-Koordinate)
Binärer Suchbaum für Beach-Line
FOR ALL p aus P {
Erstelle ein Site-Event für p und füge es zu Q hinzu;
}
WHILE(!q.empty) {
e = Das erste Element von der Warteschlange;
IF(e ist Site-Event) {
Erstelle zu e zugehöriges Circle-Event
Füge dieses Event zu B hinzu
if(Event schneidet anderes Event) {
Entferne beide Events aus Q
Berechne neues Circle-Event und speichere es in Q
}
} ELSE {
Entferne alle Nachbarn von e aus Q
Berechne daraus die neue Kante und speichere sie in K
Aktualisiere die Circle-Events der neuen Nachbarn in Q
}
}
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 38
Voronoi-Diagramm – Fortune's Algorithmus
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 39
Voronoi-Diagramm – Fortune's Algorithmus
 Laufzeit O(n log n)
 Speicher O(n)
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 40
Inhalt
 Closest Pair
□ Divide & Conquer
 Bereichssuche
□ Gitterverfahren
□ k-D-Tree
 Sweep-Line-Algorithmen
 Voronoi-Diagramme
□ Fortune‘s Algorithmus
 Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 41
Koordinatenkompression
 Gegeben:
□ Großer Raum mit wenig Objekten
 Ziel:
□ Lücken entfernen
 Beispiel:
□ SafeJourney
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 42
Topcoder - SafeJourney
 Gegeben:
□ „Stadtplan“ mit horizontalen und vertikalen Straßen
 Gesucht:
□ Minimale Anzahl an zu überquerenden Straßen um von
Punkt A zu einem Punkt B zu gelangen
 Problem:
□ Sehr große Fläche der Ebene
□ Nur wenige relevante Punkte
 Lösung: Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 43
Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 44
Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 45
Koordinatenkompression
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 46
Koordinatenkompression
 Danach:
□ Dijkstra
□ Breitensuche
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 47
Fragen?
?
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 48
Quellen
 „Hallo Welt“-Vorträge zu Geometrie 2 von 2010, 2012, 2013
 http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf
 Closest Pair
□ https://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
□ https://en.wikipedia.org/wiki/Closest_pair_of_points_proble
m
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 49
Quellen
 Bereichssuche, k-D-Tree
□ http://ls11-www.cs.unidortmund.de/people/gutweng/AD08/VO23_26_QuadTre
esWS08.pdf
□ http://algo.informatik.unifreiburg.de/bibliothek/books/ad-buch/k7/slides/05.pdf
□ https://www.cise.ufl.edu/class/cot5520fa09/CG_RangeK
Dtrees.pdf
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 50
Quellen
 Voronoi-Diagramme
□ http://blog.ivank.net/fortunes-algorithm-andimplementation.html
□ http://www.ams.org/samplings/feature-column/fcarcvoronoi
□ http://community.topcoder.com/tc?module=Static&d1=m
atch_editorials&d2=sr176
□ http://mapviewer.skynet.ie/java/Algorithm.html
□ http://community.topcoder.com/i/srm/srm176_2.gif
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 51
Quellen
 Koordinatenkompression
□ http://www.quora.com/What-is-coordinate-compression
□ http://community.topcoder.com/stat?c=problem_statement
&pm=5918&rd=8074
□ https://community.topcoder.com/tc?module=Static&d1=mat
ch_editorials&d2=srm277
Hallo Welt für Fortgeschrittene  Geometrie II  Benjamin Zenke  Folie 52

Download Report