Costs of performing approx. nearest neighbor search in a skip quadtree
Like David, I don't know why Jonathan put in that remark about the 2^d pointers. They are not needed. As David mentioned above, the essential property is that when we are doing a point location to a leaf v in Q_0, it is sufficient to remember the sibling nodes (and their boxes) in the skip quadtree. When we process a box from P, we do a point location for the leaf box closest to our query point, inserting the sibling boxes as we go down. It sounds like this would be more or less the same as your answer. In addition, this procedure is very similar, for instance, to how approximate point location is done in the following paper:
Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y., "An optimal algorithm for approximate nearest neighbor searching fixed dimensions", JACM, 1998.
Indeed, the skip quadtree (without those extra pointers) satisfies their conditions (a)-(e) that allow for fast approximate nearest-neighbor searching.