)$ time.  Consider a quadtree search from $q$ on a cube $G$ of side length $D_{\text{rough}}$. By lemma \[depthCube\], our algorithm will not expand cells with all side lengths smaller than $\frac{  {\varepsilon}D(q, \text{nn}_q)}{0 \mu \sqrt{d}}$. But since the side length reduces by at least 