Costs of performing approx. nearest neighbor search in a skip quadtree NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?



Quadtrees are efficient spatial indices. I have a puzzle with the implementation of a nearest neighbour search in a compressed quadtree structure as described in [2]. (Without going into details, the search is going top-down along so-called equidistant squares, ending in the tail node of an equidistant path. In the attached image this might be any of the nodes in the southeast filled with points.)

For their algorithm to work, one must maintain for each node -- a square with at least two non-empty quadrants -- pointers for each lowest (closest in the hierarchy) ancestor node in each of the four directions (north, west, south, east). These are indicated by the green arrows for the nodes' westward ancestor (the arrow points at the ancestor square's centre).

The paper claims these pointers can be updated in O(1) during point insertions and deletions. However when looking at the insertion of the green point, it seems I need to update any arbitrary number of pointers, in this case six of them.

I am hoping for a trick to do this pointer update in constant time. Maybe there is a form of indirection that can be exploited?



EDIT:

The relevant section from the paper is 6.3, where it reads: "if the path has bends, then in addition to the $log(c/ε)$ lowest ancestors of $q$, we should also consider for each of the $2^d$ directions the lowest ancestor of $q$ that goes towards that direction [...] Finding these squares from $q$ can be done in $O(1)$ time per square if we associate additional $2^d$ pointers to each square in $Q_0$ pointing to its closest ancestors for each direction. These pointers can also be updated in $O(1)$ time during an insertion or deletion of a point."

[2]: Eppstein, D. and Goodrich, M.T. and Sun, J.Z., “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data,” in Proceedings of the twenty-first annual symposium on Computational geometry, pp. 296—305, 2005.
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.