Das Maßproblem von Klee

Das Maßproblem von Klee

Jörg Bruder Benjamin DrayerJoachim KrempelDaniel Schüssele

Übersicht

● Problem 1-dimensional● Problem 2-dimensional● Scanline (Bentley)● Naive Lösung● Segmentbaum Lösung● Problem d-dimensional

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Gesucht: Länge der Vereinigung über alle n Intervalle

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Gesucht: Länge der Vereinigung über alle n Intervalle

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Gesucht: Länge der Vereinigung über alle n Intervalle

Platzbedarf: O(n)

Das eindimensionale Maßproblem

Gegeben: n Intervalle auf einer Geraden.

Gesucht: Länge der Vereinigung über alle n Intervalle

Platzbedarf: O(n)

Zeitkomplexität: O(n log(n))

Das zweidimensionale Maßproblem

Das zweidimensionale Maßproblem

Gegeben: n Rechtecke

Das zweidimensionale Maßproblem

Gegeben: n Rechtecke

Gesucht: Die von den Rechtecken überdeckte Fläche

Scanline

● Speicherung der Rechtecke● Scanline● Berechnung der Fläche

Speicherung der Rechtecke

q = (x-low, x-high, y-low, y-high)

Scanline

● Sortiere x-Werte aufsteigend● Verschmelze gleiche x-Werte

u1 u2 ... uk

● Analog y-Werte

v1 v2 ... v l

● Speichere die v als Listen bei den u

Scanline

Scanline

Scanline

Scanline

Berechnung der Fläche

Berechnung der Fläche

● m(i)=Maß der aktiven Segmente

i 1

k 1

u i ui 1 m i

Naiver Ansatz

● Verwende die Scanline● Berechne m(i) als eindimensionales Maßproblem● Achtung: Worstcaselaufzeit O n2

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

Idee

● Speichere nicht die Fragmente aus denen ein Segment besteht sondern markiere bestimmte Knoten. ● Der Unterbaum, der von jedem Knoten ausgeht überdeckt gewisse Segmente. ● Das Maß der aktiven Segmente soll in den Knoten gespeichert werden. ● Wenn dies realisiert ist, dann kann man an der Wurzel des Baumes das Gesammtmaß für die gerade aktiven Segmente ablesen.

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtlgorithmus

Blätter

Speichere alle y-Werte v i bis auf v1 v lund doppelt,da sie einmal als Anfang und einmal als Ende eines Segments auftreten.

q v i , v j

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtlgorithmus

q-voll, q-partiellKnoten A ist q-voll, wenn das Segment von A ganz in q liegt

q-voll, q-partiellKnoten A ist q-partiell, wenn A nicht q-voll ist aber einen Sohn hat, der q-voll oder q-partiell ist.

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

- high-line, low-line, high-tip, low-tip

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

- high-line, low-line, high-tip, low-tip

- q-volle Knoten an der high- oder low-line

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

- high-line, low-line, high-tip, low-tip

- q-volle Knoten an der high- oder low-line

Analyse:

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

- high-line, low-line, high-tip, low-tip

- q-volle Knoten an der high- oder low-line

Analyse:

- O(log(n)) Knoten

1-UmbrellaKonstrukt um Infomationen effizient in den Knoten zu halten

1-Umbrella für Segment q:

-Tip t

- high-line, low-line, high-tip, low-tip

- q-volle Knoten an der high- oder low-line

Analyse:

- O(log(n)) Knoten

- O(log(n)) Zeit

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

count(x)

● Idee war das Maß in den Knoten zu speichern nicht die Umbellas

● Gefahr: Das Maß soll sich nur erhöhen, wenn ein noch nicht ganz enthaltenes Segment eingefügt wird

● Gefahr: Beim Löschen muß berücksichtigt werden ob es noch andere Segmente gibt, die das gelöschte Intervall überdecken

● Lösung: Zusatzinformation in den Knoten

count(x)

● Informationen in den Knoten● Speichere im Knoten x das aktuelle Maß val(x)● Speichere im Knoten x, wie oft x als q-voller

Knoten in einem 1-Umbrella vorkommt als count(x)

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

Delta(x)Aktualisiert val(x) und count(x) im Knoten x, wenn ein Segment eingefügt wird und gibt Änderung zurück

Fall 1:

- count(x)++- Änderung=0- val(x) bleibt

Fall 2:

- count(x)++- Änderung=Segmentgröße - val(x)- val(x)=Segmentgröße

Delta(x)Algorithmus:

if(val(x)=Segmentgröße){count(x)++;return 0;}

else{count(x)++;f=Segmetgröße-val(x);val(x)=Segmentgröße;return f;}

Laufzeit: O(1)

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtlgorithmus

Einfügen

● Berechnen des 1-Umbrellas● Von low- und high-tip bis t mit Delta(x) updaten● Bei t Informationen verschmelzen● Information zur Wurzel propagieren

EinfügenAlgorithmus:incr=Delta(low-tip);x=father(low-tip);

Einfügen

Einfügen

EinfügenAlgorithmus:incr=Delta(low-tip);x=father(low-tip);while(x!=t){

f=0;if(x hat einen q-vollen Sohn y){

f=Delta(y);}

Einfügen

EinfügenAlgorithmus:incr=Delta(low-tip);x=father(low-tip);while(x!=t){

f=0;if(x hat einen q-vollen Sohn y){

f=Delta(y);}if(val(x)=Wert des gesammten von x aufgespannten Segments){

incr=0;}else{

incr=incr+f;val(x)=val(x)+incr;}

x=father(x);}

Einfügen

EinfügenAlgorithmus:incr=Delta(low-tip);x=father(low-tip);while(x!=t){

f=0;if(x hat einen q-vollen Sohn y){

f=Delta(y);}if(val(x)=Wert des gesammten von x aufgespannten Segments){

incr=0;}else{

incr=incr+f;val(x)=val(x)+incr;}

x=father(x);}

Einfügen●Die Hilfsfunktion Delta(x) wird in konstanter Zeit abgearbeitet. ●Die Berechnung des 1-Umbrellas O(log(n)). ●Die Schleifendurchläufe der while-Schleife O(log(n))●Propagieren ebenfalls in O(log(n))

●=> Einfügen in O(log(n))

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

Löschen

● Analog zum Einfügen

Segmentbaum● Idee● Blätter● q-voll, q-partiell● 1-Umbrella● count(x)● Delta(x)● Einfügen● Löschen● Gesamtalgorithmus

Gesamtalgorithmus

Analyse:

Scanline ist an u i

Lese aktive Segmente m(i) an der Wurzel ab,berechne Fläche mit Hilfe von ui u i 1 m i

Lösche Segmente die inaktiv werden

Füge Segmente ein, die aktiv werden

- Scanline O(n)

- Löschen/Einfügen O(log(n))

- m(i) berechnen O(1)

=> Gesamtlaufzeit O(n log(n))

Beispiel

Beispielx-Werte: 2<4<7<8<9<10

y-Werte: 2<3<4<5<8

Beispiel

BeispielFüge Segement a=[4,8] ein

Beispiel

BeispielFläche=4(4-2)=8

Füge Segement b=[3,5] ein

Beispiel

BeispielFläche=5(7-4)+8=23

Entferne a=[4,8]

Beispiel

BeispielFläche=2(8-7)+23=25

Entferne b=[3,5]

Beispiel

BeispielFläche=0(9-8)+25=25

Füge c=[2,3] ein

Beispiel

BeispielFläche=1(10-9)+25=26

Entferne c=[2,3]

Das mehrdimensionale Maßproblem

● d-Dimensionen● Scanlineansatz● Kosten: O nd 1 log n