0^d$ multiplicative factor. This time complexity of this quadtree phase(number of cells explored) of our algorithm dominates the time complexity of the ring-tree search phase of our algorithm, and hence is our overall time complexity for finding a $(0+ {\varepsilon})$ ANN to $q$. For space and pre-construction time, we note that compressed Euclidean quadtrees can be built in $O(n \log n)$ time and require $O(n)$ space [@snotes], which matches our bound for the ring-tree construction phase of our algorithm requiring $O(n \log n)$ time and $O(n)$ space.  