Prüfungsfrage 01 – Quadtree, iterativer Algorithmus

 

Es soll ein Quadtree konstruiert werden, der in jedem inneren Knoten und in jedem Blatt je einen Punkt \left( {{x_i},{y_i}} \right),\:\:i \in \mathbb{N} einer Punktwolke mit n paarweise verschiedenen Knoten speichert. Der Punkt, der in dem Knoten gespeichert ist, soll die weitere rekursive Aufteilung der zweidimensionalen Ebene vorgeben. Der Quadtree soll erzeugt werden, indem die n gegebenen Punkte zufällig permutiert und dann nacheinander (inkrementell) in den Quadtree eingefügt werden. Geben Sie (in einer objektorientierten Programmiersprache oder in Pseudocode) die Definition der Klasse QuadTree (Knoten des QuadTrees) sowie die Funktion Insert dieser Klasse an. Welche Tiefe kann der Baum im ungünstigsten Fall erreichen? Für welche Art der Eingabe erreicht der Baum diese maximale Tiefe?

Lösung

Ein QuadTree dient in diesem Zusammenhang zur Zerlegung eines zweidimensionalen Gebietes in nichtüberlappende, quadratische Zellen. Der QuadTree muss dazu den folgenden Aufbau haben:

inf-quadtree-datenstruktur

Definition des herkömmlichen QuadTrees

Gegeben ist die Menge P an Punkten und das Quadrat Q, das die Punkte enthält. Wenn in der Menge P weniger als zwei Punkte enthalten sind, ist der QuadTree definiert als ein einzelnes Blatt, das den Punkt und das Quadrat speichert. Ansonsten werden die vier Quadranten von Q nach ihrer Position benannt: QNW, QNO, QSW, QSO. Die Unterteilung des Quadrates erfolgt genau in der Mitte, dementsprechend entstehen vier neue Punktmengen:

  • {P_{NW}} = \left\{ {p \in P:{p_x} \leq {x_{mid}}\quad \wedge \quad {p_y} > {y_{mid}}} \right\}
  • {P_{NO}} = \left\{ {p \in P:{p_x} > {x_{mid}}\quad \wedge \quad {p_y} > {y_{mid}}} \right\}
  • {P_{SW}} = \left\{ {p \in P:{p_x} \leq {x_{mid}}\quad \wedge \quad {p_y} \leq {y_{mid}}} \right\}
  • {P_{SO}} = \left\{ {p \in P:{p_x} > {x_{mid}}\quad \wedge \quad {p_y} \leq {y_{mid}}} \right\}

Der QuadTree enthält dann einen Wurzelknoten v, in dem das Quadrat s gespeichert ist. Außerdem enthält er untergeordnet vier neue QuadTrees, die jeweils aus einer der oben beschriebenen neuen Punktmengen gebildet werden.

Definition eines der Aufgabenstellung entsprechenden QuadTrees

Die Punkte werden nacheinander eingefügt. Beim Einfügen eines neuen Punktes wird geprüft, ob der neue Knoten einfach als Blatt an einen bestehenden Knoten angefügt werden kann, oder ob der entsprechende Platz schon belegt ist und daher eine neue Unterteilung durchgeführt werden muss. Der QuadTree ist also definiert als ein Punkt mit den Koordinaten (x, y), der bis zu vier Nachfolger haben kann. Die Unterteilung des Rechtecks erfolgt nicht wie bei dem herkömmlichen QuadTree in der Mitte, sondern genau bei den Koordinaten des Punktes. Der Algorithmus funktioniert also nicht rekursiv (wie oben beschrieben), sondern iterativ.

inf-quadtree-algorithmus

Die Funktion insert funktioniert wie im der Abbildung oben dargestellt: 

für r = 1 bis n
	Finde das Rechteck, das p_r enthält.
	wenn das Rechteck nun genau einen Punkt enthält
		dann füge den neuen Punkt p_r als Blatt an den QuadTree an,
		der das Rechteck begrenzt
	sonst // es befinden sich schon Punkt p_m im Rechteck
		unterteile das Rechteck bei den Koordinaten von p_m und füge
		den neuen Punkt p_r als Blatt an den QuadTree an, der den
		Punkt p_m_ enthält.

Maximale Tiefe

Im Gegensatz zum herkömmlichen Quadtree (vergleiche Aufgabe 10) ist die Tiefe des Baumes hier nicht von dem geometrischen Abstand der Punkte abhängig, sondern von ihrer Anordnung und ihrer Anzahl.

inf-quadtree-worst-case

Im ungünstigsten Fall sieht der QuadTree so aus wie oben abgebildet. Die Tiefe des Baumes ist dann gleich n, da für jeden Knoten eine Unterteilung durchgeführt werden muss.

Damit der dargestellte Fall eintritt, müssen die Punkte allerdings nicht nur die entsprechende Anordnung haben, sondern sie müssen auch genau in der Reihenfolge von p1 nach oben links in den Graphen eingefügt werden. Eine zufällige Permutation vor dem Einfügen verhindert so etwas und kann daher die Tiefe des Baumes reduzieren (im dargestellten Fall um 50%).