4.3 $k$d-Bäume

Das ist der Inhalt von Praktikumsaufgabe 3. Im Folgenden $k=2$ (2d-Baum). Höhere Dimensionen gehen genauso.

Idee (Folie 10)

• Die Ebene so aufteilen wie ein binärer Suchbaum eine Zahlengerade aufteilt.
• Als Schlüssel abwechselnd die $x$- und die $y$-Koordinate verwenden.
• Jeder Knoten entspricht einem der $n$ Punkte. Der Punkt teilt die Zelle des Knotens durch eine achsenparallele Gerade in zwei Hälften.

Welche Koordinate zuerst?

Die Folien zählen Ebenen ab 1 (level = depth + 1) und nehmen auf geraden Ebenen $x$, auf ungeraden $y$. Die Wurzel (Ebene 1) teilt also nach $y$. Das passt zu Algorithmus 1 und 2, die mit vertical (= $y$ vergleichen) starten. De Berg et al. beginnen mit $x$. Für Laufzeit und Korrektheit ist das egal, man sollte es nur konsistent machen. In der Demo unten kann man beides umschalten.

Eigenschaften (Folie 12)

Für einen Knoten $v_x$ mit Punkt $p_x$, der nach $x$ teilt:

• linker Teilbaum = Punkte links von $p_x$,
• rechter Teilbaum = Punkte rechts von $p_x$,
• die Kinder teilen dann nach $y$.

Für einen Knoten $v_y$ mit Punkt $p_y$, der nach $y$ teilt:

• linker Teilbaum = Punkte unterhalb von $p_y$,
• rechter Teilbaum = Punkte oberhalb von $p_y$,
• die Kinder teilen dann nach $x$.

Jeder Knoten gehört also zu einem achsenparallelen Rechteck (seiner Zelle / Region), und die Zellen der Kinder zerlegen die Zelle des Elternknotens.

Interaktiv: Aufbau und Bereichssuche

Die farbigen Linien sind die Teilungsgeraden, je dicker, desto näher an der Wurzel. Darunter steht der Baum. Ziehe die blauen Ecken des Anfragebereichs $D$ und gehe die Suche Schritt für Schritt durch.

Schritt 1/12: RangeSearch(Wurzel, D) mit D = [4, 10] × [2, 6].

langsamnormalschnellsehr schnell

Wurzel teilt nachBlaue Punkte = Ecken von D (ziehen). Klick setzt Punkt, Rechtsklick löscht.

Anfragebereich Daktueller Knotenbesuchtin Dabgeschnittener Teilbaum

Bereichssuche (Folien 13–14)

Wie die Suche im binären Suchbaum, mit zwei Unterschieden:

1. In jedem Knoten wird je nach Ebene die $x$- oder die $y$-Koordinate verglichen.
2. Bei einer Bereichssuche muss man oft beide Teilbäume besuchen: links, wenn $D$ in der Teilungskoordinate unter den Schlüssel reicht, rechts, wenn $D$ darüber reicht.

Algorithmus 1: RangeSearch(Knoten k, Richtung d, Bereich D)
 1: if (k ≠ NULL) {
 2:   if (d == vertical) {        // y vergleichen
 3:     (l, r) = (D.y1, D.y2);
 4:     coord  = k.y;
 5:     dNew   = horizontal;
 6:   } else {                    // x vergleichen
 7:     (l, r) = (D.x1, D.x2);
 8:     coord  = k.x;
 9:     dNew   = vertical;
10:   }
11:   if (k ∈ D)     Füge k zur Ausgabe hinzu;
12:   if (l < coord) RangeSearch(k.left,  dNew, D);
13:   if (r > coord) RangeSearch(k.right, dNew, D);
14: }
Aufruf: RangeSearch(root, vertical, D)

Gleichheit

Mit den strikten Vergleichen in Zeilen 12–13 gehen Punkte verloren, wenn ein Punkt im linken Teilbaum dieselbe Koordinate hat wie der Knoten und genau auf dem Rand von $D$ liegt. Die Folien schließen das durch die Annahme verschiedener Koordinaten aus. In der Implementierung (Abgabe 3) sicherer: l <= coord und r >= coord. Die Demo macht es so.

Balancierter Aufbau am Median (Folien 16–19)

Problem: Ist der Baum unbalanciert, kann ein Pfad zur linearen Liste entarten, und die Suche wird linear.

Lösung: Immer am Median teilen. Dann haben beide Teilbäume (fast) gleich viele Punkte, und die Höhe ist $\lceil\log_2(n+1)\rceil$.

Vorgehen:

1. Alle Punkte einmal nach $x$ und nach $y$ sortieren: zwei Folgen $X$ und $Y$.
2. $Y$ am Median teilen, der Median wird die Wurzel. Das ergibt $Y_1$ (darunter) und $Y_2$ (darüber).
3. $X$ so in $X_1$, $X_2$ aufteilen, dass $X_1$ dieselben Punkte wie $Y_1$ enthält und $X_2$ dieselben wie $Y_2$ (stabil, die $x$-Sortierung bleibt erhalten).
4. Rekursiv weiter, jetzt am Median von $X_1$ bzw. $X_2$, usw., bis nur noch ein Punkt übrig ist (Blätter).

Algorithmus 2: ConstructBalanced2DTree(l, r, k, d)
   // global vorsortierte Folgen X und Y
 1: if (l ≤ r) {
 2:   m = ⌊(l + r) / 2⌋;
 3:   if (d == vertical) {
 4:     k.value = Y[m];
 5:     PartitionField(X, l, r, m);   // X[l..r] passend zu Y[l..m-1], Y[m+1..r] aufteilen
 6:   } else {
 7:     k.value = X[m];
 8:     PartitionField(Y, l, r, m);
 9:   }
10:   ConstructBalanced2DTree(l,   m-1, k.left,  !d);
11:   ConstructBalanced2DTree(m+1, r,   k.right, !d);
12: }
Aufruf: ConstructBalanced2DTree(1, n, root, vertical)

PartitionField ist ein stabiles Aufteilen in $O(r-l)$: Man läuft durch $X[l..r]$ und schreibt jeden Punkt nach links oder rechts, je nachdem, auf welcher Seite des Medians er in der anderen Koordinate liegt.

Einfacher in C++

Statt zwei vorsortierter Listen kann man in jedem Schritt std::nth_element nach der aktuellen Koordinate verwenden. Das findet den Median in erwartet $O(n)$, Gesamtaufwand dann ebenfalls $O(n\log n)$.

Laufzeit (Folien 20–21)

Aufbau

Teil	Aufwand
Sortieren von $X$ und $Y$	$O(n\log n)$
Aufteilen pro Rekursionsebene	$O(n)$
Rekursion	$T(n)=2\,T\big(\tfrac{n-1}{2}\big)+O(n)$
Lösung (Master-Theorem, Fall 2)	$O(n\log n)$

Speicher: $O(n)$, ein Knoten pro Punkt.

Bereichssuche: $O(\sqrt n + R)$

Auf den Folien „Beweis: Tafel“. Hier ausgeführt (nach de Berg et al.):

1. Zerlegung der Kosten. Besuchte Knoten sind von drei Arten:

• Knoten, deren Zelle ganz in $D$ liegt: Ihr ganzer Teilbaum wird ausgegeben. Kosten zusammen $O(R)$.
• Knoten, deren Zelle $D$ gar nicht schneidet: werden nicht besucht (der Elternknoten schneidet sie weg).
• Knoten, deren Zelle vom Rand von $D$ geschnitten wird. Nur diese sind „teuer“.

2. Wie viele Zellen schneidet eine senkrechte Gerade? Sei $Q(n)$ die Zahl der Zellen, die eine senkrechte Gerade $g$ in einem 2d-Baum mit $n$ Punkten schneidet. Nach zwei Ebenen (einmal $x$, einmal $y$) ist die Zelle in vier Teile mit je etwa $n/4$ Punkten zerlegt. Die $x$-Teilung trennt sie in links und rechts, $g$ liegt nur auf einer Seite. Die $y$-Teilung trennt oben und unten, $g$ schneidet beide. Also trifft $g$ höchstens zwei der vier Enkel:

$Q(n) = 2 + 2\,Q(n/4),\qquad Q(1)=O(1).$

Master-Theorem mit $a=2$, $b=4$: $\log_4 2 = \tfrac12$, also $Q(n)=O(n^{1/2})=O(\sqrt n)$.

3. Der Rand von $D$ besteht aus vier achsenparallelen Strecken, jede schneidet höchstens $O(\sqrt n)$ Zellen.

Ergebnis: $O(\sqrt n + R)$.

Für kleines $R$ ist das viel schneller als alle Punkte zu testen ($\sqrt{10^6}=1000$ statt $10^6$), aber deutlich langsamer als $O(\log n)$.

Höhere Dimensionen (Folie 21)

Derselbe Algorithmus: Beim Aufbau zyklisch durch die $k$ Dimensionen gehen ($x, y, z, x, y, z,\dots$), bei der Suche ebenso.

	$k$d-Baum
Aufbau	$O(k\cdot n\log n)$
Bereichssuche	$O(k\,n^{1-1/k} + R)$
Speicher	$O(n)$

Für $k=2$ ergibt $n^{1-1/2}=\sqrt n$. Für großes $k$ geht $n^{1-1/k}$ gegen $n$, der kd-Baum hilft dann kaum noch (Fluch der Dimensionen).

Nächster-Nachbar-Suche (Ergänzung)

Der häufigste praktische Einsatz von kd-Bäumen ist nicht die Rechteckanfrage, sondern die Nächste-Nachbarn-Suche (z.B. ICP, Punktwolken, k-NN in ML):

1. Absteigen wie bei der Punktsuche bis zum Blatt, das den Anfragepunkt $q$ enthalten würde. Der Punkt dort ist der erste Kandidat mit Abstand $d$.
2. Beim Rücklauf in jedem Knoten prüfen, ob der Kreis um $q$ mit Radius $d$ die andere Teilungsseite schneidet (Abstand zur Teilungsgeraden $<d$). Nur dann auch den anderen Teilbaum durchsuchen.

Bei gleichmäßig verteilten Punkten ist das im Mittel $O(\log n)$.