Quadtree balancing - Githubissues

hovey commented 2 days ago

For a quadtree with a cell that contains two points, the maximum level $h$ of the quadtree is known. (See proof: https://youtu.be/Ac47eHdSZuE?si=rM5Zie3K_07I4hmO&t=750)

let $c$ be the distance between those two points,
let $s$ be the side length distance of the root cell, level $h = 0$,
let the maximum distance in the smallest cell (the smallest cell's diagonal) be $c_{\max} = \sqrt{2} \left( s / 2^h \right) $

Then, $c \leq c_{\max}$, thus

$c \leq \sqrt{2} \left( s / 2^h \right) $

$\frac{c}{s \sqrt{2}} \leq 0.5^h $

let $L = \frac{c}{s \sqrt{2}}$

$\ln(L) \leq h \ln(0.5)$

$h \leq \frac{\ln(L)}{\ln(0.5)}$

Example, let $s = 1$ and $c = \sqrt{2}/4$, then $L = \frac{1}{4}$ and

$h \leq \frac{\ln(0.25)}{\ln(0.5)}$

$h \leq 2$

hovey commented 2 days ago

Finding neighbors: