ICS Theory Group

ICS 269, Winter 2005: Theory Seminar

14 Jan 2005:
Skip Quadtree and Its Applications

Speaker: Jonathan Sun

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in 2-D) or the skip octree (for point data in R^d, with d>2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined ``box''-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. We provide efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location queries, approximate range queries, and approximate nearest neighbor queries.

This is a joint work of David Eppstein, Michael Goodrich and Jonathan Sun.