Orthogonale Bereichssuche mit kd-Baeumen ======================================== Wolfgang Mulzer Gegeben: eine n-Punktmenge P im k-dimensionalen Raum. Gesucht: eine Datenstruktur fuer die folgende Anfrage. Sei R = [a1, b1] x [a2, b2] x ... x [ak, bk] ein achsenparalleler k-dimensionaler Quader, finde alle Punkte aus P, die in R enthalten sind. Diese Art von Anfrage nennt man "Bereichssuche". Im Folgenden werden wir annehmen, dass fuer die Punkte in P jeweils alle x1-Koordinaten und jeweils alle x2-Koordinaten usw verschieden sind. Ausserdem werden wir uns auf den zweidimensionalen Fall konzentrieren. Konstruktion ------------ Ein kd-Baum fuer P ist ein binaerer Suchbaum, der folgendermassen rekursiv konstruiert wird: Wenn P nur einen Punkt p enthaelt, erzeuge einen Baum, der nur aus einem Knoten besteht, der p speichert. Ansonsten bestimme denjenigen Punkt pm in P, dessen x- oder y-Koordinate den Median unter den x- bzw. y-Koordinaten der Punkte in P bildet. Dabei wechseln wir von Ebene zu Ebene zwischen x- und y-Koordinate. Sei P1 die Menge aller Punkte in P mit x- bzw. y-Koordinate kleiner oder gleich pm.x bzw. pm.y, und P2 die Menge aller Punkte mit x- bzw. y-Koordinate groesser als pm.x bzw. pm.y. Erzeuge rekursiv je einen kd-Baum fuer P1 und P2 (wobei im naechsten Schritt nach der y- bzw. x-Koordinate geteilt wird). Erzeuge einen neuen Wurzelknoten v. Setze den Baum fuer P1 als den linken Teilbaum von v und den Baum fuer P2 als rechten Teilbaum fuer v, und speichere pm.x bzw. pm.y in r. Der Platzbedarf des kd-Baums ist O(n), da es sich um einen binaeren Baum mit n Blaettern handelt. Die Hoehe des kd-Baums ist log n, da sich die Groesse der Punktmenge in jedem Rekursionsschritt halbiert. Der Zeitbedarf zum Aufbau der kd-Baumes ist O(n log n). Der Median laesst sich jeweils in linearer Zeit finden (entweder durch den entsprechenden Algorithmus, oder durch Vorsortieren nach x- und y-Koordinate). Daher ist die Gesamtzeit pro Ebene O(n). Es gibt log n viele Ebenen, und die Behauptung folgt. Die Konstruktion und Analyse lassen sich direkt auf k Dimensionen verallgemeinern. Bereichssuche ------------- Jedem Knoten v kann man eine rechteckige Region R(v) in der Ebene zuordnen. * Der Wurzel ordnen wir die ganze Ebene R^2 zu. * Sei nun v ein Knoten im kd-Baum mit Elternknoten w. Nimm an, w ist ein x-Knoten, d.h., w entspricht einen Split entlang der x-Koordinate. Der Knoten w speichert einen Wert p.x, der dem Median der entsprechenden x-Koordinaten entspricht. Wir definieren nun R(v) wie folgt: Wenn v das linke Kind von w ist, so ist R(v) der Schnitt von R(w) mit der *geschlossenen* linken Halbebene, die durch die senkrechte Gerade y = p.x definiert ist. Wenn v das rechte Kind von w ist, so ist R(v) der Schnitt von R(w) mit der *offenen* rechten Halbebene, die durch die senkrechte Gerade y = p.x definiert ist. Man geht analog vor, wenn w ein y-Knoten ist. Mit Hilfe der R(v) kann man nun unmittelbar den Suchalgorithmus formulieren: Wenn v ein Blatt ist, so ueberpruefe, ob der in v gespeicherte Punkt in R enthalten ist. Wenn ja, so gib ihn aus. Ansonsten, ueberpruefe fuer beide Kinder x, y von v, ob der Schnitt von R mit R(x) bzw. R(y) nicht leer ist (dazu muss man nur R mit der Splitgeraden von v vergleichen). Wenn ja, dann besuche rekursiv x oder y oder beide. Die Korrektheit des Algorithmus folgt unmittelbar. Laufzeitanalyse --------------- Zwei Parameter: n : Die Anzahl der Punkte in P z : Die Anzahl der Punkte aus P, die in R enthalten sind. Da die Arbeit fuer jeden besuchten Knoten konstant ist, genuegt es, die Anzahl der besuchten Knoten zu zaehlen. Dazu unterscheiden wir vier Faelle: R(v) und R sind disjunkt: Diese Knoten werden nicht besucht und muessen nicht gezaehlt werden. R(v) enthaelt R: Da die R(v)'s fuer alle Knoten auf einer Ebene des Baumes die Ebene R^2 partitionieren, kann dieser Fall fuer hoechstens einen Knoten auf jeder Ebene des Baumes eintreten. Also kann es insgesamt hoechstens log n Knoten dieser Art geben. R enthaelt R(v): Betrachte die Menge X aller Knoten, fuer die dieser Fall eintritt. Da die Regionen der Kindknoten in der Region des Elternknotens enthalten sind, bildet X eine Menge von vollstaendigen Teilbauemen des kd-Baums. Da diese Teilbaeume binaer sind, ist die Anzahl der inneren Knoten in X proportional zur Anzahl der Blaetter in X. Fuer jeden Blattknoten von X wird der entsprechende Punkt ausgegeben. Daher kann es hoechstens O(z) viele Knoten dieser Art geben. Der Rand von R schneidet R(v): Dies ist der interessanteste Fall. Der Rand von R besteht aus vier Kanten. Wir betrachten zunaechst die linke Kante von R, Rl. Wie sieht die Menge X der Knoten aus, deren Region Rl schneidet? X enthaelt die Wurzel des kd-Baums. Da die Wurzelregion durch eine senkrechte Strecke geteilt wird, kann nur ein Kind der Wurzel Rl schneiden. Dieses Kind wird aber durch eine horizontale Strecke geteilt, so dass zwei Enkel der Wurzel Rl schneiden koennen. Diese Urenkel werden aber wieder senkrecht geteilt, so dass wieder zwei Urenkel der Wurzel Rl schneiden koennen. Dann verdoppelt sich eventuell aber wieder die Anzahl der Ururenkel, usw. Insgesamt kann sich die Anzahl der Knoten nur auf jeder zweiten Ebene des Baumes verdoppeln. Daher ist sie beschraenkt durch 2*2^{(1/2)log n} = O(sqrt{n}). Analog untersucht man die rechte, obere und untere Kante von R, mit dem gleichen Ergebnis. Folglich ist die Gesamtlaufzeit fuer eine orthogonale Bereichssuche in einem kd-Baum O(sqrt{n} + z). In k Dimensionen verallgemeinert sich diese Laufzeit zu O(n^{1-1/k} + z).