5

One can think about skip quadtree as a skip-list implementation of a data-structure storing the points according to their z-order. It is (arguably) at least conceptually simpler... See chapter 2 here: http://goo.gl/pLiEO . And yes, assuming you can perform some basic z-order operations in constant time, you can definitely do ANN in logarithmic time. The ...


Only top voted, non community-wiki answers of a minimum length are eligible