Before revision:  In both cases our updates take 2^{O(d\log d )} time, except for the point location part in the second version which has a lower bound of \Theta (\log n)---but if a pointer (  finger ) to the correct quadtree cell is given, the rest of the updates take worst-case constant time.
After revision:  In both cases our updates take 2^{O(d\log d )} time, except for the point location part in the second version which has a lower bound of \Theta (\log n)---but if a pointer (  finger ) to the correct quadtree cell is given, the rest of the updates take worst-case constant time.