Prüfungsfrage 10 – minimaler Abstand von Punkten im QuadTree

 

Im Einheitsquadrat \left( {0;1} \right) \times \left( {0;1} \right) werden n Punkte zufällig erzeugt. Das Einheitsquadrat wird rekursiv in jeweils vier gleich große Quadranten zerlegt, die Aufteilung in einem Quadtree gespeichert. Dieser Quadtree erreicht bei der gegebenen Punktwolke eine Tiefe k. Geben Sie an, in welcher Größenordnung der minimale gegenseitige Abstand zweier Punkte der gegebenen Punktwolke liegt!

Lösung

inginf-quadtree

S: Seitenlänge
h: Höhe
c: Diagonale
k: Tiefe

Gesucht: c

\frac{S}{{{2^k}}} = h = \frac{c}{{\sqrt 2 }}\quad \Rightarrow \quad \frac{{S\sqrt 2 }}{c} = {2^k}\quad \Rightarrow \quad {\log _2}\left( {\frac{{S\sqrt 2 }}{c}} \right) = k

Wenn man die Tiefe nicht bei 0, sondern bei 1 beginnen lässt, so kommet man auf:

k = 1 + {\log _2}\left( {\frac{{S\sqrt 2 }}{c}} \right) = 1 + \underbrace {{{\log }_2}\left( {\sqrt 2 } \right)}_{\frac{1}{2}} + {\log _2}\left( {\frac{S}{c}} \right) = \frac{3}{2} + {\log _2}\left( {\frac{S}{c}} \right)

Anzahl der Knoten des Baums: O(n)

Tiefe: O\left( {\log \frac{S}{c}} \right)

Gesamtaufwand: O\left( {n \cdot \log \frac{S}{c}} \right)