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 . (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?
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."
: 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.